Vértice (teoria dos grafos): diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
m fim de tradução
Xqbot (discussão | contribs)
m Bot: Modificando: sv:Hörn (grafteori); mudanças triviais
Linha 1: Linha 1:
{{nota:|Para outros usos veja [[Vértice]]}}
{{nota:|Para outros usos veja [[Vértice]]}}


[[Image:6n-graf.svg|thumb|Um grafo com 6 vértices e 7 arestas onde o vértice da extrema-direita é um '''vértice-folha''' ou um '''vértice-pendente'''.]]
[[Ficheiro:6n-graf.svg|thumb|Um grafo com 6 vértices e 7 arestas onde o vértice da extrema-direita é um '''vértice-folha''' ou um '''vértice-pendente'''.]]


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.
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''.
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 />.
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|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 borda 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 [[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 borda 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 é [[vértice-transitivo]] se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da [[enumaeração (teoria dos grafos)|enumeração de grafos]] e [[isomorfismo (teoria dos grafos)|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.
Um grafo é [[vértice-transitivo]] se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da [[enumaeração (teoria dos grafos)|enumeração de grafos]] e [[isomorfismo (teoria dos grafos)|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.
Linha 47: Linha 47:
* {{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=}}
* {{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ém}}==
== {{Ver Também}} ==
[[Teoria dos grafos]]
[[Teoria dos grafos]]


Linha 53: Linha 53:


[[ar:رأس (نظرية المخططات)]]
[[ar:رأس (نظرية المخططات)]]
[[en:Vertex (graph_theory)]]
[[en:Vertex (graph theory)]]
[[es:Vértice (teoría de grafos)]]
[[eo:Vertico (grafeteorio)]]
[[eo:Vertico (grafeteorio)]]
[[es:Vértice (teoría de grafos)]]
[[fa:رأس (نظریه گراف)]]
[[fa:رأس (نظریه گراف)]]
[[it:Vertice (teoria dei grafi)]]
[[it:Vertice (teoria dei grafi)]]
[[no:Nod]]
[[no:Nod]]
[[pl:Wierzchołek izolowany]]
[[pl:Wierzchołek izolowany]]
[[sv:Nod (grafteori)]]
[[sv:Hörn (grafteori)]]

Revisão das 20h50min de 5 de agosto de 2010

Nota: Para outros usos veja Vértice
Um grafo com 6 vértices e 7 arestas onde o vértice da extrema-direita é um vértice-folha ou um vértice-pendente.

Em teoria dos grafos, um vértice (plural vértices) ou nodo é a unidade fundamental da qual os grafos são formados: um 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 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[1]. Um vértice w é dito ser adjacente a outro vértice v se o grafo contém uma aresta (v,w)[2]. A adjacência de um vértice v é um subgrafo induzido do grafo, formado por todos os vértices adjacentes a v.

O grau de um vértice em um grafo é o número de arestas incidentes a ele[3]. 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[2].

Um 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[4]; Um separador é uma coleção de vértices cuja remoção desconecta o grafo restante em pedaços pequenos[5]. 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 é um conjunto de vértices, que inclui o ponto de extremidade de cada borda 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 é vértice-transitivo se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da 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értices de poliedros: 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 dígrafo, estrela frontal de um nodo é definida como a suas arestas de saída. Em um grafo com um conjunto de vértices e um conjunto de arestas , a estrela frontal de pode ser descrita como

[6]


Referências

  1. Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. 249 páginas. ISBN 0-914894-21-8 
  2. a b Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8 
  3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2002). Algoritmos. Teoria e Prática 2ª ed. Rio de Janeiro: Campus. 916 páginas. ISBN 85-352-0926-3 
  4. Grafos - UFSC
  5. Algoritmos em Grafos - IME
  6. Gallo, Giorgio; Pallotino, Stefano (December 1988). «Shortest Path Algorithms» (PDF). Annals of Operations Research. 13 (1). Netherlands: Springer. pp. 1–79. doi:10.1007/BF02288320. Consultado em 18 de junho de 2008  Verifique data em: |data= (ajuda)
  • 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)
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9 
  • Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. [S.l.]: New York, Academic Press. ISBN 0-12-324245-2 

Ver também

Teoria dos grafos