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

11 bytes adicionados ,  15h39min de 28 de janeiro de 2012
m
Checkwiki + ajustes
m (Checkwiki + ajustes)
Em [[teoria dos grafos]], um '''vértice''' (plural '''vértices''') ou '''nodo''' é 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 a 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=|id=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 a 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=|id=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 a 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=|id=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.
 
Um grafo é [[grafo vértice-transitivo|vértice-transitivo]] se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da [[enumeração (teoria dos grafos)|enumeração de grafos]] e [[isomorfismo de grafos]], é importante fazer a distinção entre '''vértices rotulados''' e '''vértices sem rótulo'''. Um vértice rotulado é um vértice que está associado com informação extra que possa o distinguir de outros vértices rotulados; dois grafos podem ser considerados isomórficos somente se a correspondência entre seus vértices emparelham vértices com rótulos iguais. Um vértice não marcado é aquele que pode ser substituído por qualquer outro vértice com base apenas em suas adjacências no gráfico e não baseado em quaisquer informações adicionais.
 
Vértices em grafos são análogos, mas não o mesmo que, [[Vértice|vérticesvértice]]s de [[Poliedro|poliedrospoliedro]]s: o esqueleto de um [[poliedro]] forma um grafo, os vértices do qual são vértices do poliedro, mas os vértices do poliedro tem uma estrutura adicional (sua localização geométrica) que não se presume estar presente na teoria dos grafos. A [[Figura de vértice]] de um vértice de um [[poliedro]] é análoga à vizinhança de um vértice em um grafo.
 
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
| authorlink = Giorgio Gallo
| coauthors = [[Stefano Pallottino|Pallotino, Stefano]]
| title = Shortest Path Algorithms
| journal = Annals of Operations Research
| volume = 13
| accessdate = 2008-06-18
| doi = 10.1007/BF02288320 }}</ref>
 
 
{{Referências}}
 
* [[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 book | last=Chartrand | first=Gary | authorlink=Gary Chartrand | coauthors= | title=Introductory graph theory | date=1985 | publisher=Dover | location=New York | isbn=0-486-24775-9 | pages=}}
 
* {{Cite book | author=Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. | authorlink= | coauthors= | title=Graph theory, 1736-1936 | date=1986 | publisher=Clarendon Press | location=Oxford [Oxfordshire] | isbn=0-19-853916-9 | pages=}}
 
* {{Cite book | last=Harary | first=Frank | authorlink=Frank Harary | coauthors= | title=Graph theory | date=1969 | publisher=Addison-Wesley Publishing | location=Reading, Mass. | isbn=0-201-41033-8 | pages=}}
 
* {{Cite book | author=Harary, Frank; Palmer, Edgar M. | authorlink= | coauthors= | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | location= | isbn=0-12-324245-2 | pages=}}
 
== {{Ver Tambémtambém}} ==
* [[Teoria dos grafos]]
 
{{DEFAULTSORT:Vertice (Teoria Grafos)}}
[[Categoria:Teoria dos grafos]]
 
718 366

edições