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 nombre d'[[Aresta (teoria de grafs)|arestes]] que hi incideixen, amb els [[bucles]] comptats dues vegades.<ref>{{Ref-llibre | cognom=Diestel | nom=Reinhard | títol=Graph Theory | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | editorial=Springer-Verlag | lloc=Berlin, New York | pàgines = p.5| edició=3rd3a ed.| isbn=978-3-540-26183-4 | any=2005 | llengua=anglès}}</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.