Saltar para o conteúdo

Diferenças entre edições de "Vértice (teoria dos grafos)"

88 bytes removidos ,  23h49min de 15 de julho de 2017
m
traduzindo nome/parâmetro, ajustes gerais nas citações, outros ajustes usando script
(Legenda da Imagem, O vértice pendente é o da estrema esquerda e não direita (Vértice pendente é o vértice de numero 6 ))
m (traduzindo nome/parâmetro, ajustes gerais nas citações, outros ajustes usando script)
Em [[teoria dos grafos]], um '''vértice''' (plural '''vértices''') ou '''nó''' é a unidade fundamental da qual os grafos são formados: um [[Grafo|grafo não dirigido]] consiste de um conjunto de vértices e um conjunto de arestas (pares de vértices não ordenados), enquanto um [[Quiver|digrafo]] é constituído por um conjunto de vértices e um conjunto de arcos (pares ordenados de vértices). Do ponto de vista da teoria dos grafos, vértices são tratados como objetos inexpressivos e indivisíveis, embora possam ter uma estrutura adicional, dependendo da aplicação a partir da qual surge o grafo; por exemplo, uma [[rede semântica]] é um grafo no qual os vértices representam conceitos ou classes de objetos.
 
Os dois vértices formando uma aresta são ditos suas extremidades e a aresta é dita que é incidente para com os vértices.<ref name=even>{{Referência acitar livro|autor=Even, Shimon|título=Graph Algorithms|subtítulo=|idioma=|edição=|local=Rockville, Maryland|editora=Computer Science Press|ano=1979|páginas=249|volumes=|volume=|idisbn=ISBN 0-914894-21-8}}</ref> Um vértice ''w'' é dito ser adjacente a outro vértice ''v'' se o grafo contém uma aresta (''v'',''w'').<ref name=szwarcfiter>{{Referência acitar livro|autor=Szwarcfiter, Jayme Luiz|título=Grafos e algoritmos computacionais|subtítulo=|idioma=|edição=|local=Rio de Janeiro|editora=Campus|ano=1988|páginas=|volumes=|volume=|idisbn=ISBN 85-7001-341-8}}</ref> A [[adjacência (teoria dos grafos)|adjacência]] de um vértice ''v'' é um [[subgrafo induzido]] do grafo, formado por todos os vértices adjacentes a ''v''.
 
O [[grau (teoria dos grafos)|grau]] de um vértice em um grafo é o número de arestas incidentes a ele.<ref name=cormen>{{Referência acitar livro|autor=Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford|título=Algoritmos|subtítulo=Teoria e Prática|idioma=|edição=2ª|local=Rio de Janeiro|editora=Campus|ano=2002|páginas=916|volumes=|volume=|idisbn=ISBN 85-352-0926-3}}</ref> Um '''vértice isolado''' é um vértice com grau zero, isto é, um vértice que não é um ponto final de toda a aresta. Um '''vértice folha''' (também '''vértice pendente''') é um vértice de grau um. Em um grafo direcionado, pode-se distinguir o grau de saída (número de arestas divergentes) do grau de entrada (número de arestas convergentes); uma '''fonte''' é um vértice com grau de entrada zero, enquanto um '''sumidouro''' (ou poço) é um vértice com grau de saída nulo.<ref name=szwarcfiter /> .
 
Um [[Vértice de corte (teoria dos grafos)|vértice de corte]] é um vértice cuja remoção (juntamente com as arestas a ele conectadas) provoca um redução na conexidade do grafo;<ref>[http://www.inf.ufsc.br/grafos/definicoes/definicao.html Grafos - UFSC]</ref> Um separador é uma coleção de vértices cuja remoção desconecta o grafo restante em pedaços pequenos.<ref>[http://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/two-flow.html Algoritmos em Grafos - IME]</ref> Um grafo k-conexo é um gráfico em que a remoção de menos de ''k'' vértices sempre deixa o grafo ainda conectado. Um [[conjunto independente]] é um conjunto de vértices tal que não existem dois vértices adjacentes contido neste conjunto, e uma [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]] é um conjunto de vértices, que inclui o ponto de extremidade de cada aresta do grafo. O [[espaço de vértices]] de um grafo é um espaço vetorial com um conjunto de vetores de base correspondente aos vértices do gráfico.
Em um [[Teoria dos grafos|dígrafo]], estrela frontal de um nodo <math>u</math> é definida como a suas arestas de saída. Em um grafo <math>G</math> com um conjunto de vértices <math>V</math> e um conjunto de arestas <math>E</math>, a estrela frontal de <math>u</math> pode ser descrita como
:<math>\{(u, v) \in E\}.\ </math><ref>{{citar jornal
| lastúltimo = Gallo
| firstprimeiro = Giorgio
| authorlinkautorlink = Giorgio Gallo
| coauthors coautor= [[Stefano Pallottino|Pallotino, Stefano]]
| title título= Shortest Path Algorithms
| journal periódico= Annals of Operations Research
| volume = 13
| issue número= 1
| pages páginas= 1–79
| publisher publicado= [[Springer Science+Business Media|Springer]]
| location local= Netherlands
| date data= [[December 1988]]
| url = http://www.springerlink.com/content/awn535w405321948/
| format formato= [[PDF]]
| accessdate acessodata= 2008-06-18
| doi = 10.1007/BF02288320 }}</ref>
 
 
* [[Claude Berge|Berge, Claude]], ''Théorie des graphes et ses applications''. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
* {{Cite bookcitar livro|último last=Chartrand |primeiro first=Gary |autorlink authorlink=Gary Chartrand | coauthorscoautor= | titletítulo=Introductory graph theory | datedata=1985 | publisherpublicado=Dover | locationlocal=New York | isbn=0-486-24775-9 | pagespáginas=}}
* {{Cite bookcitar livro|autor author=Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. |autorlink authorlink= | coauthorscoautor= | titletítulo=Graph theory, 1736-1936 | datedata=1986 | publisherpublicado=Clarendon Press | locationlocal=Oxford [Oxfordshire] | isbn=0-19-853916-9 | pagespáginas=}}
* {{Cite bookcitar livro|último last=Harary |primeiro first=Frank |autorlink authorlink=Frank Harary | coauthorscoautor= | titletítulo=Graph theory | datedata=1969 | publisherpublicado=Addison-Wesley Publishing | locationlocal=Reading, Mass. | isbn=0-201-41033-8 | pagespáginas=}}
* {{Cite bookcitar livro|autor author=Harary, Frank; Palmer, Edgar M. |autorlink authorlink= | coauthorscoautor= | titletítulo=Graphical enumeration | datedata=1973 | publisherpublicado=New York, Academic Press | locationlocal= | isbn=0-12-324245-2 | pagespáginas=}}
 
== {{Ver também}} ==
* [[Teoria dos grafos]]