Simplexní graf - Simplex graph

v teorie grafů, pobočka matematika, simplexní graf κ (G) neorientovaného grafu G je sám o sobě grafem, s každým uzlem klika (sada vzájemně sousedících vrcholů) v G. Dva uzly κ (G) jsou spojeny hranou, kdykoli se odpovídající dvě kliky liší v přítomnosti nebo nepřítomnosti jediného vrcholu.
Prázdná sada je zahrnuta jako jedna z klik G které se používají k vytvoření klikového grafu, stejně jako každá sada jednoho vrcholu a každá sada dvou sousedních vrcholů. Proto simplexní graf obsahuje uvnitř a pododdělení z G sám. Simplexní graf a kompletní graf je hyperkrychlový graf a simplexní graf a graf cyklu délky čtyři nebo více je a převodový graf. Simplexní graf doplňkový graf a graf cesty je Fibonacciho kostka.
Kompletní podgrafy G může být dána struktura a střední algebra: medián tří klik A, B, a C je tvořen vrcholy, které patří do a většina ze tří klik.[1] Jakékoli dva vrcholy patřící k této mediánové sadě musí oba patřit alespoň jednomu z A, Bnebo C, a proto musí být spojeny hranou, takže medián tří klik je sama klikou. Simplexním grafem je střední graf odpovídající této střední struktuře algebry. Když G je doplňkový graf a bipartitní graf, kliky G lze získat silnější strukturu jako a distribuční mříž,[2] a v tomto případě je simplexní graf grafem mřížky. Jak obecně platí pro mediánové grafy, každý simplexní graf je sám o sobě bipartitní.
Simplexní graf má jeden vrchol pro každý simplex v klikový komplex X (G) z G, a dva vrcholy jsou spojeny hranou, když jeden ze dvou odpovídajících simplexů je aspektem druhého. Takže objekty (vrcholy v simplexním grafu, simplexy v X (G)) a vztahy mezi objekty (hrany v simplexním grafu, inkluzní vztahy mezi simplexy v X (G)) jsou v korespondenci jedna ku jedné mezi X (G) a κ (G).
Simplexní grafy představil Bandelt a van de Vel (1989),[3] který si všiml, že simplexní graf nemá žádné kostky právě tehdy, když je podkladový graf bez trojúhelníků, a ukázal, že chromatické číslo podkladového grafu se rovná minimálnímu počtu n tak, že simplexní graf lze izometricky vložit do a kartézský součin z n stromy. V důsledku existence grafy bez trojúhelníků s vysokým chromatickým číslem, ukázali, že existují dvourozměrné topologické střední algebry které nelze zabudovat do produktů konečně mnoha skutečné stromy. Imrich, Klavžar & Mulder (1999) také použijte simplexní grafy jako součást svého důkazu, že testování, zda je graf bez trojúhelníků nebo zda je to střední graf, může být provedeno stejně rychle.
Poznámky
- ^ Barthélemy, Leclerc a Monjardet (1986), strana 200.
- ^ Propp (1997).
- ^ Imrich, Klavžar & Mulder (1999) připočítat zavedení simplexních grafů k pozdějšímu článku, také Bandeltem a van de Velem, ale zdá se, že to byla chyba.
Reference
- Bandelt, H.-J .; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J.E.; Pach, J .; Pollack, R. (eds.), Průzkumy diskrétní a výpočetní geometrie: o dvacet let později, Contemp. Matematika., 453„Providence, RI: AMS, s. 49–86.
- Bandelt, H.-J .; van de Vel, M. (1989), „Vkládání topologických středních algeber do produktů dendronů“, Proceedings of the London Mathematical Society, s3-58 (3): 439–453, doi:10,1112 / plms / s3-58,3,439.
- Barthélemy, J.-P .; Leclerc, B .; Monjardet, B. (1986), „O použití uspořádaných množin v problémech srovnání a konsensu klasifikací“, Journal of Classification, 3 (2): 187–224, doi:10.1007 / BF01894188.
- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), „Mediánové grafy a grafy bez trojúhelníků“, SIAM Journal on Discrete Mathematics, 12 (1): 111–118, CiteSeerX 10.1.1.28.5906, doi:10.1137 / S0895480197323494, PAN 1666073.
- Propp, James (1997), „Generování náhodných prvků konečných distribučních mřížek“, Electronic Journal of Combinatorics, 4 (2): R15, arXiv:math.CO/9801066.