Sousedství (teorie grafů)

V teorii grafů je přilehlý vrchol vrcholu v vrchol spojený s v hranou . Okolí vrcholu v v grafu G je vygenerovaný podgraf grafu G , který se skládá ze všech vrcholů sdružených s v a všech hran spojujících dva takové vrcholy. Na obrázku je například znázorněn graf se 6 vrcholy a 7 hranami. Vrchol 5 sousedí s vrcholy 1, 2 a 4, ale nesousedí s vrcholy 3 a 6. Okolí vrcholu 5 je graf se třemi vrcholy 1, 2 a 4 a jednou hranou spojující vrcholy 1 a 2.

Okolí je často označováno jako N G ( v ) nebo (pokud víte, o který graf se jedná) N ( v ). Stejný zápis sousedství lze použít k odkazování na sadu sousedních vrcholů spíše než na odpovídající generovaný podgraf. Okolí popsané výše nezahrnuje v samotné a toto okolí je označováno jako otevřené sousedství v . Můžete definovat okolí, které zahrnuje v . V tomto případě se okolí nazývá uzavřené a označuje se jako N G [ v ]. Pokud to není výslovně uvedeno, předpokládá se, že okolí je otevřené.

Sousedství lze použít k reprezentaci grafů v počítačových algoritmech pomocí seznamu sousedství a matice sousedství . Sousedství se také používá v koeficientu shlukování grafu, který měří průměrnou hustotu jeho sousedství. Kromě toho lze mnoho důležitých tříd grafů definovat vlastnostmi jejich sousedství nebo vzájemnou symetrií sousedství.

Izolovaný vrchol nemá žádné sousední vrcholy. Stupeň vrcholu se rovná počtu sousedních vrcholů. Speciálním případem je smyčka spojující vrchol se stejným vrcholem. Pokud taková hrana existuje, vrchol patří do jeho vlastního okolí.

Lokální vlastnosti grafu

Jestliže všechny vrcholy grafu G mají sousedství izomorfní k nějakému grafu H , pak G je lokálně graf H , a jestliže všechny vrcholy G mají okolí patřící do nějaké rodiny grafů F , G je řekl, že je lokálně graf. F [1] [2] . Například v grafu oktaedru zobrazeném na obrázku má každý vrchol sousedství izomorfní s cyklem čtyř vrcholů, takže oktaedr je lokálně C 4 .

Například:

Jakýkoli úplný graf Kn je lokálně graf Kn -1 . Jediné grafy, které jsou lokálně úplné, jsou disjunktní spojení úplných grafů.
Turanův graf T ( rs , r ) je lokálně ekvivalentní T ( ( r -1) s , r -1). To znamená, že jakýkoli Turanův graf je lokálně Turanův graf.
Libovolný rovinný graf je lokálně vnější rovina . Ne každý lokálně vnější rovinný graf je však rovinný.
Graf je graf bez trojúhelníku právě tehdy, když je lokálně nezávislý .
Jakýkoli k - chromatický graf je lokálně ( k -1) - chromatický. Každý lokálně k -chromatický graf má chromatické číslo [3] . $O({\sqrt {kn)))$
Pokud je rodina grafů F uzavřena operací převzetí generovaných podgrafů, pak každý graf v F je také lokálně F . Například každý akordický graf je lokálně akordický, každý dokonalý graf je lokálně dokonalý, jakýkoli graf srovnatelnosti je graf srovnatelnosti.
Graf je lokálně cyklický, pokud je každé okolí cyklem . Například, osmistěnný graf je jediným lokálně C 4 grafem, ikosaedrový graf je jediným lokálně C 5 grafem a Paleyův graf řádu 13 je lokálně C 6 . Lokálně cyklické grafy jiné než K 4 jsou přesně ty grafy, které jsou základem Whitneyho triangulace , která vkládá grafy do povrchu takovým způsobem, že plochy vložení odpovídají klikám grafu [4] [5] [6] . Lokálně cyklické grafy mohou až do hran [7] . ${\displaystyle n^{2-o(1)))$
Grafy bez drápků jsou grafy, které jsou lokálně bez trojúhelníků . To znamená, že pro všechny vrcholy doplněk grafu okolí vrcholu neobsahuje trojúhelníky. Graf, který je lokálně grafem H , neobsahuje drápy právě tehdy, když číslo nezávislosti H je nejvýše dvě. Například graf pravidelného dvacetistěnu neobsahuje drápy, protože je lokálně C 5 a číslo nezávislosti C 5 je dvě.

Mnoho sousedů

Pro množinu A vrcholů je okolí A sjednocením okolí vrcholů, takže obsahuje všechny vrcholy konjugované s alespoň jedním členem A .

O množině vrcholu A grafu se říká, že je modulem, pokud všechny vrcholy A mají stejnou množinu sousedství mimo A . Každý graf má jedinečnou rekurzivní modularizaci, nazývanou modularizace , kterou lze z grafu sestavit v lineárním čase . Modulární dekompoziční algoritmus je aplikován na další algoritmy pro grafy, včetně rozpoznávání grafů srovnatelnosti .

Viz také

sousedství Moore
Okolí von Neumann
Vrcholový obrazec , podobný koncept v geometrii mnohostěnů.

Literatura

Nora Hartsfeld, Gerhard Ringel. Čisté triangulace // Combinatorica . - 1991. - Sv. 11, č. 2. - S. 145-155. - doi : 10.1007/BF01206358 .
Pavol Peklo. . Grafy s danými čtvrtěmi I // Problemes Combinatoires et Théorie des Graphes. - Paříž: Éditions du Centre national de la recherche scientifique, 1978. - xiv + 443 s. — (Colloques internationaux CNRS, sv. 260). — ISBN 2222020700 . - S. 219-223.
F. Larrión, V. Neumann-Lara, M. A. Pizaña. Whitneyho triangulace, místní obvod a iterované klikové grafy // Diskrétní matematika . - 2002. - Sv. 258. - S. 123-135. - doi : 10.1016/S0012-365X(02)00266-2 .
Aleksander Malnic, Bojan Mohar. Generování lokálně cyklických triangulací povrchů // Journal of Combinatorial Theory, Series B . - 1992. - Sv. 56, č.p. 2. - S. 147-164. - doi : 10.1016/0095-8956(92)90015-P .
J. Sedláček. . O lokálních vlastnostech konečných grafů // Teorie grafů, Lagow. - Springer-Verlag, 1983. - (Poznámky z přednášky z matematiky, sv. 1018). - ISBN 978-3-540-12687-4 . - doi : 10.1007/BFb0071634 . - S. 242-247.
Ákos Seress, Tibor Szabo. Husté grafy s okolím cyklu // Journal of Combinatorial Theory, Series B . - 1995. - Sv. 63, č.p. 2. - S. 281-293. - doi : 10.1006/jctb.1995.1020 . Archivováno z originálu 30. srpna 2005.
Avi Wigderson. Zlepšení záruky výkonu pro přibližné vybarvení grafu // Journal of the ACM . - 1983. - Sv. 30, č. 4. - S. 729-735. - doi : 10.1145/2157.2158 .