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

[[Fitxer:UndirectedDegrees.svg|thumb|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 nusaltre vèrtex.]]

En [[teoria de grafs]], el '''grau''' o '''valència''' d'un [[Vèrtex (teoria de grafs)|vèrtex]] és el número 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 '''xv''' vees donat perdenota '''grau(xv)''', '''g(xv)''' o '''gr(xv)''' (tot i que també es fa servir '''δ(xv)''', i de l'[[anglès]] '''d(xv)''' i '''deg(xv)'''). El grau màxim d'un graf ''G'', vedenotat donat percom '''Δ(G)''', i el grau mínim d'un graf ''G'', vedenotat donat percom '''δ(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.