Vértice (teoría de grafos)

Neste grafo, os vértices 4 e 5 son veciños mentres que os vértices 3 e 5 son independentes. O grao do vértice 4 é igual a 3. O vértice 6 é unha folla.

Na teoría de grafos, un vértice, tamén chamado nó e máis raramente nodo, é a unidade fundamental dun grafo.

Dous vértices son veciños se están unidos por unha aresta. Dous vértices son independentes se non son veciños.

Tipos de vértices

Rede de oito vértices (incluíndo un illado) e 10 arestas.

O grao dun vértice v, denotado 𝛿(v), é o número de arestas incidentes a este vértice ou o número de veciños de v.

Un vértice illado é un vértice cuxo grao é cero, é dicir, un vértice que non está ligado a ningún outro vértice. Chamámoslle unha folla a un vértice cuxo grao é un.

Nun grafo dirixido, distinguimos o grao entrante, denotado 𝛿 ⁻ (v), do grao saínte, denotado 𝛿 ⁺ (v). Un vértice de orixe é un vértice cuxo grao de entrada é cero mentres que un vértice de fluxo é un vértice con grao exterior cero.

Véxase tamén

Bibliografía

• Uma Introdução Sucinta à Teoria dos Grafos

Outros artigos

• Léxico da teoría de grafos
• Teoría de grafos
• Aresta

Ligazóns externas

• Dr. Milton Teoría dos grafos.
• Graph Theory (LibreTexts).