Vértice (teoria dos grafos) - Vertex (graph theory)

Um gráfico com 6 vértices e 7 arestas onde o vértice número 6 na extrema esquerda é um vértice de folha ou um vértice pendente

Na matemática , e mais especificamente na teoria dos grafos , um vértice ( vértices plurais ) ou é a unidade fundamental da qual os gráficos são formados: um grafo não direcionado consiste em um conjunto de vértices e um conjunto de arestas (pares não ordenados de vértices), enquanto um grafo direcionado consiste em um conjunto de vértices e um conjunto de arcos (pares ordenados de vértices). Em um diagrama de um gráfico, um vértice é geralmente representado por um círculo com um rótulo, e uma aresta é representada por uma linha ou seta que se estende de um vértice a outro.

Do ponto de vista da teoria dos grafos, os vértices são tratados como objetos indissociáveis ​​e indivisíveis , embora possam ter estrutura adicional dependendo da aplicação da qual o gráfico surge; por exemplo, uma rede semântica é um grafo no qual os vértices representam conceitos ou classes de objetos.

Os dois vértices que formam uma aresta são considerados os pontos finais dessa aresta, e a aresta é considerada incidente com os vértices. Diz-se que um vértice w é adjacente a outro vértice v se o gráfico contém uma aresta ( v , w ). A vizinhança de um vértice v é um subgrafo induzido do gráfico, formado por todos os vértices adjacentes a  v .

Tipos de vértices

Um pequeno exemplo de rede com 8 vértices e 10 arestas.
Exemplo de rede com 8 vértices (dos quais um é isolado) e 10 arestas.

O grau de um vértice, denotado por 𝛿 (v) em um gráfico, é o número de arestas incidentes nele. Um vértice isolado é um vértice com grau zero; ou seja, um vértice que não é um ponto final de nenhuma aresta (a imagem de exemplo ilustra um vértice isolado). Um vértice de folha (também vértice pendente ) é um vértice com grau um. Em um grafo direcionado, pode-se distinguir o outdegree (número de arestas de saída), denotado 𝛿 + (v), do indegree (número de arestas de entrada), denotado por 𝛿 - (v); um vértice de origem é um vértice com zero indegree, enquanto um vértice sink é um vértice com outdegree zero. Um vértice simplicial é aquele cujos vizinhos formam um clique : cada dois vizinhos são adjacentes. Um vértice universal é um vértice adjacente a todos os outros vértices do gráfico.

Um vértice de corte é um vértice cuja remoção desconectaria o gráfico restante; um separador de vértices é uma coleção de vértices cuja remoção desconectaria o gráfico restante em pequenos pedaços. Um grafo conectado ao vértice k é um grafo no qual a remoção de menos de k vértices sempre deixa o grafo restante conectado. Um conjunto independente é um conjunto de vértices nenhum dos quais são adjacentes, e uma cobertura de vértices é um conjunto de vértices que inclui pelo menos um ponto final de cada aresta no gráfico. O espaço de vértices de um gráfico é um espaço vetorial que possui um conjunto de vetores de base correspondentes aos vértices do gráfico.

Um gráfico é transitivo de vértice se tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto de enumeração e isomorfismo de gráfico , é importante distinguir entre vértices rotulados e vértices não rotulados . Um vértice rotulado é um vértice associado a informações extras que permitem que ele seja diferenciado de outros vértices rotulados; dois gráficos podem ser considerados isomórficos apenas se a correspondência entre seus vértices emparelha vértices com rótulos iguais. Um vértice não rotulado é aquele que pode ser substituído por qualquer outro vértice com base apenas em suas adjacências no grafo e não com base em nenhuma informação adicional.

Os vértices nos gráficos são análogos, mas não iguais aos vértices dos poliedros : o esqueleto de um poliedro forma um gráfico, cujos vértices são os vértices do poliedro, mas os vértices poliedros têm estrutura adicional (sua localização geométrica) que é não presume-se que esteja presente na teoria dos grafos. A figura do vértice de um vértice em um poliedro é análoga à vizinhança de um vértice em um gráfico.

Veja também

Referências

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Algoritmos do caminho mais curto". Annals of Operations Research . 13 (1): 1–79. doi : 10.1007 / BF02288320 .
  • Berge, Claude , Théorie des graphes et ses applications . Coleção Universitaire de Mathématiques, II Dunod, Paris 1958, viii + 277 pp. (Edição em inglês, Wiley 1961; Methuen & Co, Nova York 1962; Russo, Moscou 1961; Espanhol, México 1962; Romeno, Bucareste 1969; Chinês, Xangai 1963 ; Segunda impressão da primeira edição em inglês de 1962. Dover, New York 2001)
  • Chartrand, Gary (1985). Teoria introdutória dos grafos . Nova York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Teoria dos gráficos, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Teoria dos grafos . Reading, Mass .: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Harary, Frank; Palmer, Edgar M. (1973). Enumeração gráfica . New York, Academic Press. ISBN 0-12-324245-2.

links externos