Usuari:Habicht/proves/Veïnat (teoria de grafs)
|
Per a altres significats, vegeu «Veïnat». |
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.
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]- Hartsfeld, Nora & Ringel, Gerhard (1991), "Clean triangulations", Combinatorica 11 (2): 145–155, DOI 10.1007/BF01206358.
- Hell, Pavol (1978), "Graphs with given neighborhoods I", Problems Combinatories et theorie des graphes, vol. 260, Colloque internationaux C.N.R.S., pàg. 219–223.
- Larrión, F.; Neumann-Lara, V. & Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics 258: 123–135, doi:10.1016/S0012-365X(02)00266-2, <http://xamanek.izt.uam.mx/map/papers/cuello10_DM.ps>.
- Malnič, Aleksander & Mohar, Bojan (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B 56 (2): 147–164, DOI 10.1016/0095-8956(92)90015-P.
- Sedlacek, J. (1983), "On local properties of finite graphs", Graph Theory, Lagów, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pàg. 242–247, ISBN 978-3-540-12687-4, DOI 10.1007/BFb0071634.
- Seress, Ákos & Szabó, Tibor (1995), "Dense graphs with cycle neighborhoods", Journal of Combinatorial Theory, Series B 63 (2): 281–293, doi:10.1006/jctb.1995.1020, <http://www.inf.ethz.ch/personal/szabo/PS/kornyezetek.ps>.
- Wigderson, Avi (1983), "Improving the performance guarantee for approximate graph coloring", Journal of the ACM 30 (4): 729–735, DOI 10.1145/2157.2158.