Grao (teoría de grafos)

Un grafo $G$ non orientado onde se indicou o grao de cada vértice. Neste grafo, o grao máximo é $\Delta (G)=5$ e o grao mínimo é $\delta (G)=0$ .

En matemáticas, e máis concretamente na teoría de grafos, o grao (ou valencia) dun vértice dun grafo é o número de ligazóns (arestas ou arcos) que conectan este vértice, onde os bucles contan dúas veces. O grao dun vértice $s$ nótase $\deg(s)$.

Gráfico orientado

No caso dun grafo orientado, tamén se fala do grao de entrada dun vértice $d^{-}(s)$, é dicir, o número de arcos orientados cara ao vértice $s$, e o grao de saída do vértice $d^{+}(s)$, é dicir, o número de arcos que saen de $s$. Temos $\deg(s)=d^{+}(s)+d^{-}(s)$: o grao do vértice é a suma do grao saínte e o grao entrante.

Características

O grao máximo dun grafo $G$, denótase $\Delta (G)$, e o grao mínimo do grafo, denótase $\delta (G)$, son respectivamente o máximo e o mínimo dos graos dos seus vértices. Nun grafo regular, todos os vértices teñen o mesmo grao, polo que podemos falar do grao do grafo.

Véxase tamén

Bibliografía

• Alain Bretto; Alain Faisant; François Hennecart (2022). European Mathematical Society Press, ed. Elements of Graph Theory: From Basic Concepts to Modern Developments. ISBN 978-3-98547-017-4. 

Outros artigos

• Grafo