Grannskap (grafteori)

I grafteorin är en intilliggande vertex av en vertex v en vertex ansluten till v med en kant . En grannskap av en vertex v i en graf G är en genererad subgraf av grafen G , som består av alla hörn konjugerade till v och alla kanter som förbinder två sådana hörn. Till exempel visar figuren en graf med 6 hörn och 7 kanter. Vertex 5 ligger intill hörn 1, 2 och 4, men inte intill hörn 3 och 6. Området till vertex 5 är en graf med tre hörn 1, 2 och 4, och en kant som förbinder hörn 1 och 2.

En grannskap betecknas ofta som N G ( v ) eller (om du vet vilken graf det är fråga om) N ( v ). Samma grannskapsnotation kan användas för att referera till uppsättningen av intilliggande hörn snarare än till motsvarande genererade subgraf. Området som beskrivs ovan inkluderar inte v självt , och detta område kallas en öppen grannskap av v . Du kan definiera en stadsdel som inkluderar v . I det här fallet kallas grannskapet stängt och betecknas som N G [ v ]. Om inget uttryckligen anges, antas området vara öppet.

Grannskap kan användas för att representera grafer i datoralgoritmer via grannskapslista och närliggande matris . Grannskap används också i klustringskoefficienten i en graf, som mäter den genomsnittliga tätheten för dess grannskap. Dessutom kan många viktiga klasser av grafer definieras av egenskaperna hos dess grannskap eller av den inbördes symmetrin mellan grannskaperna.

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 till samma vertex. Om en sådan kant finns, tillhör vertex sitt eget grannskap.

Lokala egenskaper för en graf

Om alla hörn i en graf G har kvarter som är isomorfa till någon graf H , så sägs G lokalt vara en graf H , och om alla hörn i G har kvarter som tillhör någon familj av grafer F , sägs G vara lokalt en graf F [1] [2] . 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 4 .

Till exempel:

Varje komplett graf Kn är lokalt en graf Kn -1 . De enda graferna som är lokalt kompletta är den osammanhängande föreningen av kompletta grafer.
Turan-grafen T ( rs , r ) är lokalt ekvivalent med T (( r -1) s , r -1). Det vill säga, vilken Turan-graf som helst är lokalt en Turan-graf.
Alla plana grafer är lokalt ytterplanar . Dock är inte varje lokalt ytterplanär graf plan.
En graf är en triangelfri graf om och endast om den är lokalt oberoende .
Varje k - kromatisk graf är lokalt ( k -1)-kromatisk. Varje lokalt k -kromatisk graf har ett kromatiskt nummer [3] . $O({\sqrt {kn)))$
Om en familj av grafer F stängs under operationen att ta genererade subgrafer, så är varje graf i F också lokalt F . Till exempel är vilken ackordsgraf som helst lokalt ackordal, vilken perfekt graf som helst är lokalt perfekt, vilken jämförbarhetsgraf som helst är en jämförbarhetsgraf.
En graf är lokalt cyklisk om varje stadsdel är en cykel . Till exempel är oktaedergrafen den enda lokalt C 4 -grafen, icosahedron-grafen är den enda lokalt C 5 -grafen, och Paley-grafen av ordning 13 är lokalt C 6 . Andra lokalt cykliska grafer än K 4 är just de grafer som ligger bakom Whitney-trianguleringen , som bäddar in grafer i en yta på ett sådant sätt att inbäddningens ytor motsvarar grafens klick [4] [5] [6] . Lokalt cykliska grafer kan upp till kanter [7] . ${\displaystyle n^{2-o(1)))$
Grafer utan klor är grafer som är lokalt triangelfria . Det vill säga, för alla hörn innehåller komplementet till vertex grannskapsgrafen inte trianglar. En graf som lokalt är en graf H innehåller inte klor om och endast om oberoendetalet för H är högst två. Till exempel innehåller grafen för en vanlig ikosaeder inte klor eftersom det lokalt är C 5 och C 5 -oberoendetalet är två.

Många grannar

För en uppsättning A av hörn är grannskapet av A föreningen av kvarteren av hörn, så att den innehåller alla hörn konjugerat till minst en medlem av A .

En vertexuppsättning A i en graf sägs vara en modul om alla hörn av A har samma uppsättning grannskap utanför A . Varje graf har en unik rekursiv modularisering, kallad modularisering , som kan byggas från grafen i linjär tid . Den modulära nedbrytningsalgoritmen tillämpas på andra algoritmer för grafer, inklusive jämförbarhetsgrafigenkänning .

Se även

Moore grannskap
Kvarteret Von Neumann
Vertex figur , ett liknande koncept i polyedrarnas geometri.

Litteratur

Nora Hartsfeld, Gerhard Ringel. Rengör triangulering // Combinatorica . - 1991. - Vol. 11, nr. 2. - S. 145-155. - doi : 10.1007/BF01206358 .
Pavol helvete. . Grafer med givna stadsdelar I // Problemes Combinatoires et Théorie des Graphes. - Paris: Éditions du Centre national de la recherche scientifique, 1978. - xiv + 443 s. — (Colloques internationaux CNRS, vol. 260). — ISBN 2222020700 . - S. 219-223.
F. Larrión, V. Neumann-Lara, M. A. Pizaña. Whitney-triangulering, lokal omkrets och itererade klickgrafer // Diskret matematik . - 2002. - Vol. 258. - S. 123-135. - doi : 10.1016/S0012-365X(02)00266-2 .
Aleksander Malnic, Bojan Mohar. Generera lokalt cykliska trianguleringar av ytor // Journal of Combinatorial Theory, Series B . - 1992. - Vol. 56, nr. 2. - S. 147-164. - doi : 10.1016/0095-8956(92)90015-P .
J. Sedlacek. . Om lokala egenskaper hos finita grafer // Graph Theory, Lagow. - Springer-Verlag, 1983. - (Lecture Notes in Mathematics, vol. 1018). - ISBN 978-3-540-12687-4 . - doi : 10.1007/BFb0071634 . - S. 242-247.
Ákos Seress, Tibor Szabo. Täta grafer med cykelkvarter // Journal of Combinatorial Theory, Series B . - 1995. - Vol. 63, nr. 2. - s. 281-293. - doi : 10.1006/jctb.1995.1020 . Arkiverad från originalet den 30 augusti 2005.
Avi Wigderson. Förbättring av prestandagarantin för ungefärlig graffärgning // Journal of the ACM . - 1983. - Vol. 30, nej. 4. - P. 729-735. - doi : 10.1145/2157.2158 .