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

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 16h48min de 17 de maio de 2010

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.

Referências

↑ Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. 249 páginas. ISBN 0-914894-21-8
↑ ^a ^b Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8
↑ 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
↑ Grafos - UFSC
↑ Algoritmos em Grafos - IME

Predefinição:Ligações Externas

[even-1] Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. 249 páginas. ISBN 0-914894-21-8

[szwarcfiter-2] Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8

[cormen-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

[1]

[2]

[3]

[4]

[5]

@@ Linha 11: / Linha 11: @@
 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]] é 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]] é 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]] é 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.
 <!--