Naapuruus (graafiteoria)

Graafiteoriassa kärjen v viereinen kärki on kärki , joka on yhdistetty v :hen reunalla . Kuvaajan G kärjen v lähialue on graafin G generoitu aligraafi , joka koostuu kaikista v :ään konjugoiduista pisteistä ja kaikista kahta tällaista pistettä yhdistävistä reunoista. Esimerkiksi kuvassa on graafi, jossa on 6 kärkeä ja 7 reunaa. Vertex 5 on pisteiden 1, 2 ja 4 vieressä, mutta ei pisteiden 3 ja 6 vieressä. Huippupisteen 5 lähialue on graafi, jossa on kolme kärkeä 1, 2 ja 4 ja yksi kärkipisteitä 1 ja 2 yhdistävä reuna.

Naapurustoa merkitään usein nimellä N G ( v ) tai (jos tiedät, mikä graafi on kyseessä) N ( v ). Samaa naapurimerkintää voidaan käyttää viittaamaan vierekkäisten kärkien joukkoon vastaavan generoidun aligraafin sijaan. Yllä kuvattu naapurusto ei sisällä itse v : tä, ja tätä naapurustoa kutsutaan v : n avoimeksi lähialueeksi . Voit määrittää kaupunginosan, joka sisältää v . Tässä tapauksessa naapurustoa kutsutaan suljetuksi ja sitä merkitään N G [ v ]. Ellei nimenomaisesti ole määritelty, naapuruston oletetaan olevan avoin.

Naapurustoja voidaan käyttää kuvaajien esittämiseen tietokonealgoritmeissa viereisyysluettelon ja viereisyysmatriisin avulla . Naapurustoja käytetään myös graafin klusterointikertoimessa , joka mittaa sen lähialueiden keskimääräistä tiheyttä . Lisäksi monet tärkeät graafiluokat voidaan määritellä sen lähialueiden ominaisuuksien tai lähialueiden keskinäisen symmetrian perusteella.

Eristetyllä kärjellä ei ole vierekkäisiä kärkipisteitä. Huippupisteen aste on yhtä suuri kuin vierekkäisten pisteiden lukumäärä. Erikoistapaus on silmukka , joka yhdistää kärjen samaan kärkeen. Jos tällainen reuna on olemassa, huippu kuuluu omaan naapurustoonsa.

Kaavion paikalliset ominaisuudet

Jos kaikilla graafin G pisteillä on lähialueita , jotka ovat isomorfisia jonkin graafin H kanssa, niin G :n sanotaan olevan paikallisesti graafi H ja jos G :n kaikilla kärjeillä on lähialueita, jotka kuuluvat johonkin graafiperheeseen F , G :n sanotaan olevan paikallisesti graafi. F [1] [2] . Esimerkiksi kuvassa esitetyssä oktaedrigraafissa jokaisella kärjellä on isomorfinen naapuri neljän kärjen syklille , joten oktaedri on paikallisesti C 4 .

Esimerkiksi:

Mikä tahansa täydellinen graafi K n on paikallisesti graafi K n-1 . Ainoat paikallisesti täydelliset kaaviot ovat täydellisten kaavioiden disjunktoitu liitto.
Turan-graafi T ( rs , r ) on paikallisesti ekvivalentti T (( r - 1) s , r - 1). Eli mikä tahansa Turan-graafi on paikallisesti Turan-graafi.
Mikä tahansa tasograafi on paikallisesti ulompi . Jokainen paikallisesti ulkotasoinen kuvaaja ei kuitenkaan ole tasomainen.
Graafi on kolmioton graafi , jos ja vain jos se on paikallisesti riippumaton .
Mikä tahansa k - kromaattinen graafi on paikallisesti ( k -1) -kromaattinen. Jokaisella paikallisesti k -kromaattisella graafilla on kromaattinen luku [3] . $O({\sqrt {kn)))$
Jos graafien perhe F suljetaan generoitujen aligraafien ottamisen yhteydessä, niin mikä tahansa graafi F :ssä on myös paikallisesti F . Esimerkiksi mikä tahansa sointukuvaaja on paikallisesti sointu, mikä tahansa täydellinen graafi on paikallisesti täydellinen, mikä tahansa vertailukelpoinen graafi on vertailukelpoinen graafi.
Kaavio on paikallisesti syklinen, jos jokainen naapurusto on sykli . Esimerkiksi oktaedrigraafi on ainoa paikallisesti C4 - graafi, ikosaedrigraafi on ainoa paikallisesti C5 - graafi ja 13. kertaluvun Paley-graafi on paikallisesti C6 . Muut kuin K 4 paikallisesti sykliset graafit ovat juuri Whitneyn kolmiomittauksen taustalla olevia kaavioita , jotka upottavat graafit pintaan siten, että upotuksen pinnat vastaavat graafin klikkejä [4] [5] [6] . Paikallisesti sykliset graafit voivat olla jopa reunoja [7] . ${\displaystyle n^{2-o(1)))$
Graafit ilman kynsiä ovat kaavioita, jotka ovat paikallisesti kolmiottomia . Toisin sanoen kaikkien kärkien kohdalla vertex-naapurigraafin komplementti ei sisällä kolmioita. Graafi, joka on paikallisesti graafi H , ei sisällä kynsiä silloin ja vain, jos H : n riippumattomuusluku on enintään kaksi. Esimerkiksi säännöllisen ikosaedrin kuvaaja ei sisällä kynsiä, koska se on paikallisesti C 5 ja C 5 riippumattomuusluku on kaksi.

Monet naapurit

Piikkijoukolle A A : n naapurusto on kärkien lähialueiden liitto, joten se sisältää kaikki kärjet, jotka on konjugoitu ainakin yhteen A :n jäseneen .

Graafin kärkijoukon A sanotaan olevan moduuli, jos kaikilla A:n pisteillä on sama joukko A:n ulkopuolella olevia lähialueita . Jokaisella graafilla on ainutlaatuinen rekursiivinen modularisaatio, jota kutsutaan modularisaatioksi , joka voidaan rakentaa graafista lineaarisessa ajassa . Modulaarista hajottelualgoritmia sovelletaan muihin kaavioiden algoritmeihin, mukaan lukien vertailukelpoisuuskuvaajan tunnistus .

Katso myös

Mooren naapurustossa
Von Neumannin naapurustossa
Vertex figure , samanlainen käsite polyhedran geometriassa.

Kirjallisuus

Nora Hartsfeld, Gerhard Ringel. Puhtaat kolmiot // Combinatorica . - 1991. - Voi. 11, ei. 2. - s. 145-155. - doi : 10.1007/BF01206358 .
Pavol Helvetti. . Kuvaajat tietyillä lähiöillä I // Problemes Combinatoires et Théorie des Graphes. - Paris: Éditions du Centre national de la recherche scientifique, 1978. - xiv + 443 s. — (Colloques internationaux CNRS, osa 260). — ISBN 2222020700 . - s. 219-223.
F. Larrión, V. Neumann-Lara, M. A. Pizaña. Whitneyn kolmiomittaukset, paikallinen ympärysmitta ja iteroidut klikkauskaaviot // Discrete Mathematics . - 2002. - Voi. 258. - s. 123-135. - doi : 10.1016/S0012-365X(02)00266-2 .
Aleksander Malnic, Bojan Mohar. Pintojen paikallisesti syklisten kolmioiden muodostaminen // Journal of Combinatorial Theory, Series B . - 1992. - Voi. 56, nro. 2. - s. 147-164. - doi : 10.1016/0095-8956(92)90015-P .
J. Sedlacek. . Äärillisten graafien paikallisista ominaisuuksista // Graph Theory, Lagow. - Springer-Verlag, 1983. - (Matematiikan luentomuistiinpanot, osa 1018). - ISBN 978-3-540-12687-4 . - doi : 10.1007/BFb0071634 . - s. 242-247.
Ákos Seress, Tibor Szabo. Tiheät kaaviot jakson lähialueet // Journal of Combinatorial Theory, sarja B . - 1995. - Voi. 63, nro. 2. - s. 281-293. - doi : 10.1006/jctb.1995.1020 . Arkistoitu alkuperäisestä 30. elokuuta 2005.
Avi Wigderson. Suorituskykytakuun parantaminen likimääräiselle kuvaajan väritykselle // Journal of the ACM . - 1983. - Voi. 30, ei. 4. - P. 729-735. - doi : 10.1145/2157.2158 .