Em teoria dos grafos, um vértice (plural vértices) ou nó é 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 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 é 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 ${\displaystyle u}$ é definida como a suas arestas de saída. Em um grafo ${\displaystyle G}$ com um conjunto de vértices ${\displaystyle V}$ e um conjunto de arestas ${\displaystyle E}$, a estrela frontal de ${\displaystyle u}$ pode ser descrita como

${\displaystyle \{(u,v)\in E\}.\ }$^[6]

Referências

• 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)
• Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9 
• Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8 
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. [S.l.]: New York, Academic Press. ISBN 0-12-324245-2  !CS1 manut: Nomes múltiplos: lista de autores (link)

• Teoria dos grafos