Grannskap (grafteori)

I den här grafen är hörnen intill 5 1, 2 och 4. Området 5 är grafen som består av hörnen 1, 2, 4 och kanten som förbinder 1 och 2.

I grafteorin är en intilliggande hörn av en vertex $v$ i en graf en vertex som är ansluten till $v$ med en kant . Närheten till en vertex $v$ i en graf $G$ är subgrafen av $G$ inducerad av alla hörn intill $v$ , dvs grafen som består av hörnen intill $v$ och alla kanter som förbinder hörn intill $v$ .

Grannskapet betecknas ofta $N_{G}(v)$ eller (när grafen är entydig) $N(v)$ . Samma grannskapsnotation kan också användas för att referera till uppsättningar av intilliggande hörn snarare än motsvarande inducerade subgrafer. Grannskapet som beskrivs ovan inkluderar inte $v$ själv, och är mer specifikt den öppna grannskapet av $v$ ; det är också möjligt att definiera ett område där $v$ själv ingår, kallat det slutna området och betecknat med $N_{G}[v]$ . När det anges utan några förbehåll, antas en stadsdel vara öppen.

Grannskap kan användas för att representera grafer i datoralgoritmer, via grannlistan och närliggande matrisrepresentationer . Grannskap används också i klustringskoefficienten för en graf, som är ett mått på den genomsnittliga tätheten i dess grannskap. Dessutom kan många viktiga klasser av grafer definieras av egenskaperna i deras grannskap, eller av symmetrier som relaterar stadsdelar till varandra.

En isolerad vertex har inga angränsande hörn. Graden av en vertex är lika med antalet angränsande hörn . Ett specialfall är en slinga som förbinder en vertex med sig själv; om en sådan kant finns, hör vertex till sitt eget kvarter.

Lokala egenskaper i grafer

I oktaedergrafen är grannskapet till varje vertex en 4- cykel .

Om alla hörn i G har kvarter som är isomorfa till samma graf H , sägs G vara lokalt H, och om alla hörn i G har kvarter som tillhör någon graffamilj F , sägs G vara lokalt F ( Hell 1978 , Sedláček 1983 ). Till exempel, i oktaedergrafen , som visas i figuren, har varje vertex ett grannskap som är isomorft till en cykel av fyra hörn, så oktaedern är lokalt C ₄ .

Till exempel:

Varje komplett graf Kn är lokalt Kn _-1_. De enda graferna som är lokalt kompletta är osammanhängande sammanslutningar av kompletta grafer.
En Turán-graf T ( rs , r ) är lokalt T (( r -1) s , r -1). Mer generellt är alla Turán-grafer lokalt Turán.
Varje plan graf är lokalt ytterplanar . Dock är inte varje lokalt ytterplanär graf plan.
En graf är triangelfri om och endast om den är lokalt oberoende .
Varje k - kromatisk graf är lokalt ( k -1)-kromatisk. Varje lokalt k -kromatisk graf har kromatiskt nummer $O({\sqrt {kn}})$ ( Wigderson 1983 ).
Om en graffamilj F stängs under operationen att ta inducerade subgrafer, så är varje graf i F också lokalt F . Till exempel är varje ackordsgraf lokalt ackordal; varje perfekt graf är lokalt perfekt; varje jämförbarhetsgraf är lokalt jämförbar.
En graf är lokalt cyklisk om varje stadsdel är en cykel . Till exempel oktaedern den unika anslutna lokalt C ₄ -grafen, icosahedron är den unika anslutna lokalt C ₅ -grafen, och Paley-grafen av ordning 13 är lokalt C ₆ . Andra lokalt cykliska grafer än K ₄ är exakt de underliggande graferna för Whitney-trianguleringarna , inbäddningar av grafer på ytor på ett sådant sätt att inbäddningens ytor är grafens klick ( Hartsfeld & Ringel 1991; Larrión , Neumann-Lara & Pizaña 2002 ; Malnič & Mohar 1992 ). Lokalt cykliska grafer kan ha så många som $n^{2-o(1)}$ kanter ( Seress & Szabó 1995 ).
Klofria grafer är de grafer som är lokalt triangelfria ; det vill säga, för alla hörn komplementgrafen för området kring vertex inte en triangel. En graf som är lokalt H är klofri om och endast om oberoendetalet för H är högst två; till exempel är grafen för den vanliga ikosaedern klofri eftersom den lokalt är C ₅ och C ₅ har oberoende nummer två.
De lokalt linjära graferna är de grafer där varje stadsdel är en inducerad matchning ( Fronček 1989 ).

Grannskap till en uppsättning

För en uppsättning A av hörn är grannskapet av A föreningen av kvarteren av hörnen, och så är det mängden av alla hörn som gränsar till åtminstone en medlem av A .

En uppsättning A med hörn i en graf sägs vara en modul om varje vertex i A har samma uppsättning grannar utanför A . Varje graf har en unik rekursiv uppdelning i moduler, dess modulära uppdelning , som kan konstrueras från grafen i linjär tid ; modulära nedbrytningsalgoritmer har tillämpningar i andra grafalgoritmer inklusive igenkänning av jämförbarhetsgrafer .

Se även

Markov filt
Moore grannskap
Kvarteret Von Neumann
Andra grannskapsproblemet
Vertex figur , ett relaterat begrepp i polyedrar
Länka (enkelt komplex) , en genrealisering av grannskapet till enkla komplex.

Fronček, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz/136481 , MR 1016323
Hartsfeld, Nora; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica , 11 (2): 145–155, doi : 10.1007/BF01206358 , S2CID 28144260 .
Hell, Pavol (1978), "Graphs with given neighborhoods I", Problèmes combinatoires et théorie des graphes , Colloques internationaux CNRS, vol. 260, s. 219–223 .
Larrión, F.; Neumann-Lara, V .; Pizaña, MA (2002), "Whitney triangulations, local girth and iterated clique graphs" , Discrete Mathematics , 258 (1–3): 123–135, doi : 10.1016/S0012-365X(02)00266-2 .
Malnič, Aleksander; Mohar, Bojan (1992), "Generating locally cyclic triangulations of ytor", Journal of Combinatorial Theory, Series B , 56 (2): 147–164, doi : 10.1016/0095-8956(92)90015-P .
Sedláček, J. (1983), "Om lokala egenskaper hos finita grafer", Graph Theory, Lagów , Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, s. 242–247, doi : 10.1007/BFb0071634 , ISBN 978-3-540-12687-4 .
Seress, Ákos; Szabó, Tibor (1995), "Täta grafer med cykelkvarter", Journal of Combinatorial Theory, Series B , 63 (2): 281–293, doi : 10.1006/jctb.1995.1020 .
Wigderson, Avi (1983), "Improving the performance guarantee for approximate graph coloring", Journal of the ACM , 30 (4): 729–735, doi : 10.1145/2157.2158 , S2CID 32214512 .