Grau (teoria de grafs): diferència entre les revisions
Contingut suprimit Contingut afegit
m Corregit: el número d > el nombre d |
mCap resum de modificació |
||
Línia 1:
[[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 altre vèrtex.]]
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ó=3rd | 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.
== Lema de l'encaixada de mans ==
La '''fórmula de la suma de graus''' estableix que, donat un graf <math>G=(V, E)</math>,
Linha 12 ⟶ 10:
== Valors especials ==
* 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
<references />
{{esborrany de matemàtiques}}
| |||