Veïnat (teoria de grafs)

En teoria de grafs, el veïnat d'un vèrtex v en un graf G és el subgraf induït de G format per tots els vèrtexs adjacents de v (és a dir, vèrtexs connectats a v per una aresta) i per totes les arestes que connecten dos d'aquests vèrtexs. Per exemple, la imatge mostra un graf de 6 vèrtexs i 7 arestes. El vèrtex 5 és adjacent als vèrtexs 1, 2 i 4, però no és adjacent a 3 ni a 6. El veïnat del vèrtex 5 és el graf amb tres vèrtexs (1, 2 i 4) i una aresta que connecta els vèrtexs 1 i 2.

Un graf format per 6 vèrtexs i 7 arestes.

El veïnat es denota sovint com NG(v), o simplement N(v) quan el graf no és ambigu. De vegades també s'utilitza aquesta notació per referir-se al conjunt de vèrtexs adjacents en lloc del corresponent subgraf induït. El veïnat descrit anteriorment no inclou el propi v, i és més específicament el veïnat obert' de v; també és possible definir un veïnat en el qual s'inclogui v, anomenat el veïnat tancat i denotat per NG[v]. Quan es fa referència al veïnat sense cap qualificació, s'assumeix que es tracta d'un veïnat obert.

Els veïnats es poden utilitzar per representar grafs en algoritmes informàtics, a través de les representacions llista d'adjacència i matriu d'adjacència. Els veïnats també s'utilitzen en el coeficient d'agrupament d'un graf, que és una mesura de la densitat mitjana dels seus veïnats. A més, moltes classes importants de grafs es poden definir a través de les propietats dels seus veïnats, o per simetries que relacionen veïnats entre ells.

Un vèrtex aïllat no té vèrtexs adjacents. El grau d'un vèrtex és igual al nombre de vèrtexs adjacents. Un cas especial és un bucle que connecta un vèrtex amb si mateix; si existeix una aresta d'aquest tipus, llavors el vèrtex pertany al seu propi veïnat.

Bibliografia modifica