Grau (teoria de grafs)

De Viquipèdia
Dreceres ràpides: navegació, cerca
Per a altres significats vegeu «Grau».
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.

En teoria de grafs, el grau o valència d'un vèrtex és el número 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 5 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.

Lema de l'encaixada de mans[modifica | modifica el codi]

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

\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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

  1. Diestel p.5

Bibliografia[modifica | modifica el codi]