Metszésponti grafikon

A gráfelméletben a metszéspont gráf egy olyan gráf , amely egy halmazcsalád metszésponti sémáját reprezentálja [ . Bármely gráf ábrázolható metszésponti gráfként, de néhány fontos speciális osztály meghatározható a metszethalmazként való ábrázoláshoz használt halmaztípusok szempontjából.

A metszésgráfok elméletének és a metszésgráfok fontos speciális osztályainak áttekintését lásd McKee és McMorris [1] cikkében .

Formális definíció

A metszésgráf egy halmazcsaládból kialakított irányítatlan gráf

S_{i},i=0,1,2,...

úgy, hogy minden halmazhoz létrehozunk egy csúcsot , és összekötünk két csúcsot és egy élt, ha a megfelelő két halmaznak van egy nem üres metszéspontja, azaz. $v_{i}$ $S_{i}$ $v_{i}$ $v_{j}$

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

Minden grafikon metszésponti grafikon

Bármely irányítatlan G gráf ábrázolható metszésgráfként - a G gráf bármely csúcsára egy halmazt alkotunk, amely a -vel beeső élekből áll . Két ilyen halmaznak akkor és csak akkor van nem üres metszéspontja, ha a megfelelő csúcsok ugyanahhoz az élhez tartoznak. Erdős, Goodman és Poza [2] egy hatékonyabb konstrukciót mutatott be (amihez minden halmazban kevesebb elemre van szükség ), amelyben a halmazok összes elemének száma nem haladja meg a -t , ahol n a gráf csúcsainak száma. Azt az állításukat, hogy minden gráf metszésponti gráf, Marchevsky [3] feljegyezte , de javasolták Chulik munkájának [4] megtekintését is . Egy gráf metszéspontszáma az elemek minimális száma a gráf metszésgráfként való ábrázolásában. $v_{i}$ $S_{i}$ $v_{i}$ $S_{i}$ $n^{2}/4$

A metszetgráfok osztályai

Számos fontos gráfcsalád leírható korlátozott halmaztípusok metszésponti gráfjaként, például bizonyos geometriai konfigurációkból származó halmazokként:

Az intervallumgráf egy vonalon lévő intervallumok metszéspontjainak grafikonja vagy összekapcsolt útvonal - részgráfok grafikonja .
A körív gráfot körív metszésponti grafikonként határozzuk meg .
A körön lévő sokszögek grafikonja a körön fekvő sokszögek és csúcsok metszéspontjainak grafikonja.
Az akkordgráfok egyik jellemzője, hogy egy fa összefüggő részgráfjainak metszésponti gráfjai .
A trapézgráf a két párhuzamos egyenes által alkotott trapézmetszéspontok grafikonja. Ezek a permutációs gráf fogalmának általánosításai , amelyek viszont az összehasonlíthatósági gráfok komplementer családjának speciális esetei, amelyeket összehasonlíthatósági gráfoknak neveznek.
Az egységkör gráf a síkban lévő egységkörök metszéspontja.
A körcsomagolási tétel kimondja, hogy a síkgráfok pontosan a síkban lévő zárt diszjunkt (megengedett) lemezcsaládok metszésponti gráfjai.
Scheinerman sejtése (ma egy tétel) kimondja, hogy bármely sík gráf ábrázolható egy síkban lévő szakaszok metszéspontjainak gráfjaként. Az egyenes szakaszainak metszéspontjainak grafikonjai azonban lehetnek nem síkbeliek, és az egyenes szakaszainak metszéspontjainak grafikonjainak felismerése teljes a valós számok létezésének elméletéhez [5] .
A G gráf vonalgráfját úgy definiáljuk, mint a G gráf éleinek metszésponti gráfját , ahol minden élet két végcsúcsának halmazának tekintünk.
A string gráf egy síkban lévő görbék metszéspontjainak grafikonja .
Egy gráfnak van k kerete , ha többdimenziós k méretű téglalapok metszéspontja , de nem kisebb.

Változatok és általánosítások

A metszetgráfok sorrendjének elméleti analógjai a beágyazó sorrendek . Ugyanúgy, ahogy a metszéspont gráfábrázolása minden csúcsot a rájuk eső élek halmazával jelöl meg, amelyeknek nem üres metszéspontja van, a részlegesen rendezett halmaz f beágyazási sorrendű reprezentációja minden elemet egy halmazzal jelöl meg úgy, hogy bármely x és y benne akkor és csak akkor . $x\leq y$ $f(x)\subseteq f(y)$
Idegbevonat

Irodalom

K. Culik. A gráfok elmélete és alkalmazásai (Proc. Sympos. Smolenice, 1963). — Prága: Publ. Ház Csehszlovák Akad. Sci., 13-20. (1964).
Erdős Paul, A.W. Goodman, Louis Posa. Grafikon ábrázolása meghatározott metszéspontokkal // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Algoritmikus gráfelmélet és tökéletes gráfok. - Academic Press, 1980. - ISBN 0-12-289260-7 .
A metszetgráf elmélet témái. - Philadelphia: Society for Industrial and Applied Mathematics, 1999. - Vol. 2. - (SIAM Monographs on Discrete Mathematics and Applications). — ISBN 0-89871-430-3 .
E. Szpilrain-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Math. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schäfer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, 2009 szeptember, Revised Papers . - Springer-Verlag, 2010. - 20. évf. 5849. - S. 334-344. — (Számítástechnikai előadásjegyzetek). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .

Linkek

Jan Kratochvíl, Videóelőadás a metszésponti gráfokról (2007. június) Archiválva : 2020. február 17. a Wayback Machine -nél
E. Prisner, A Journey through Intersection Graph County archiválva 2021. április 24-én a Wayback Machine -nél