Grau (teoria de grafs): diferència entre les revisions

En [[teoria de grafs]], el '''grau''' o '''valència''' d'un [[Vèrtex (teoria de grafs)|vèrtex]] és el númeronombre d'[[Aresta (teoria de grafs)|arestes]] que hi incideixen, amb els [[bucles]] comptats dues vegades.<ref>Diestel p.5</ref> 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.