Grau (teoria de grafos)

Archiu:UndirectedDegrees.svg

Un grafo en vèrtiços etiquetats segons el seu grau. El vèrtiç aïllat s'etiqueta en 0, puix no és adjacent a cap nodo.

En Teoria de grafos, el grau o valència d'un vèrtiç és el número d'arestes incidents al vèrtiç. El grau d'un vèrtiç x és denotat per grau(x), g(x) o gr(x) (encara que també s'usa δ(x), i de l'anglés d(x) i deg(x)). El grau màxim d'un grafo G és denotat per Δ(G) i el grau mínim d'un grafo G és denotat per δ(G).

Un vèrtiç en grau 0 és un vèrtiç aïllat. Un grafo format exclusivament per vèrtiços aïllats és un grafo buit. Un grafo a on tots els vèrtiços tenen el mateix grau és un grafo regular, i un grafo no dirigit de n vèrtiços en que tots els vèrtiços té grau n-1 és un grafo complet.

Veïnat d'un vèrtiç

Artícul principal → Veïnat (teoria de grafos).

Una atra forma de definir el grau d'un vèrtiç és a través del seu veïnat. El veïnat d'un vèrtiç x , denotat com $N(x)$ està donat per tots els vèrtiços adjacents a x.

$N(x)=\{y\in V_G|\{x,y\}\in E_G\}$

de modo que el grau del vèrtiç x és el número de veïns que té: $g(x)=|N(x)|$.

Lema de la premuda de mans

El Lema de la premuda de mans determina que la suma dels graus d'un grafo simple (és dir, sense bucles) i no dirigit equival al doble del seu número d'arestes:

La seua demostració és una prova del doble conteo: com cada aresta té dos vèrtiços extrems, és contada dos voltes.

Algunes implicacions del Lema de la premuda de mans són:

• En un grafo simple no dirigit sempre hi ha un número par de vèrtiços de grau impar.
• En un grafo simple no dirigit no pot existir un grafo r-regular de s vèrtiços si r i s són impars.
• En un grafo simple no dirigit el número d'arestes d'un grafo k-regular és $\frac{nk}{2}$, i per això, el número d'arestes d'un grafo complet de n vèrtiços és $\frac{n(n-1)}{2}.$

Grau modal mig

Dau un grafo simple no dirigit $G(V,E)$, el grau promig o grau modal mig (que denotarem $\overline{g}$) és un estadístic definit com el grau promig dels nodos:

$\overline{g}=\frac{\sum _{v\in V}g(v)}{|V|}=\frac{2|E|}{|V|}$

Varianza dels graus

Donat un grafo simple no dirigit $G(V,E)$, la varianza dels graus, que denotarem $S_D^2$, medix la variabilitat dels graus dels nodos. Formalment es definix com:

$S_D^2=\frac{\sum _{v\in V}(g(v)-\overline{g}{)}^2}{|V|}$

Si el grafo és regular, és dir, els graus de tots els seus vèrtiços són iguals, llavors $S_D^2=0$.

Vore també

• Distribució de grau

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.