Grau (teoria de grafs)

En teoria de grafs, el grau o valència d'un vèrtex és el nombre d'arestes que hi incideixen, amb els bucles comptats dues vegades.^[1] El grau d'un vèrtex v es denota grau(v), g(v) o gr(v) (tot i que també es fa servir δ(v), i de l'anglès d(v) i deg(v)). El grau màxim d'un graf G, denotat com Δ(G), i el grau mínim d'un graf G, denotat com δ(G), són respectivament els graus màxim i mínim dels seus vèrtexs. Al graf de la dreta, el grau màxim és 3 i el grau mínim és 0. En un graf regular tots els graus són iguals, i per tant es pot parlar del grau del graf.

Un graf amb vèrtexs etiquetats segons el seu grau. El vèrtex aïllat s'etiqueta amb 0, ja que no és adjacent a cap altre vèrtex.

Lema de l'encaixada de mans

Article principal: Lema de l'encaixada de mans

La fórmula de la suma de graus estableix que, donat un graf ${\displaystyle G=(V,E)}$,

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.}$

La fórmula implica que en qualsevol graf el nombre de vèrtexs amb grau senar és parell. Aquesta proposició (així com la fórmula de la suma graus) es coneix com el lema de l'encaixada de mans. Aquest nom es deu a un problema matemàtic popular, en el qual cal demostrar que en qualsevol grup de persones el nombre de persones que s'han donat la mà amb un nombre senar d'altres persones del grup és parell.

Valors especials

• Un vèrtex de grau 0 s'anomena un vèrtex aïllat.
• Un vèrtex de grau 1 s'anomena un vèrtex fulla.
• Un vèrtex de grau n-1 en un graf amb n vèrtexs s'anomena un vèrtex dominant.

Referències

1. Diestel, Reinhard. Graph Theory (en anglès). 3a ed.. Berlin, New York: Springer-Verlag, 2005, p.5. ISBN 978-3-540-26183-4.

Viccionari