Průnikový graf - Intersection graph - Wikipedia

Příklad toho, jak protínající množiny definuje graf.

v teorie grafů, an průsečíkový graf je graf že představuje vzor křižovatky rodiny sady. Libovolný graf lze reprezentovat jako průsečíkový graf, ale některé důležité speciální třídy grafů lze definovat pomocí typů množin, které se používají k vytvoření jejich průsečíkové reprezentace.

Formální definice

Formálně průsečíkový graf G je neorientovaný graf vytvořený z rodiny množin

S_i, i = 0, 1, 2, ...

vytvořením jednoho vrcholu proti_i pro každou sadu S_ia spojením dvou vrcholů proti_i a proti_j o hranu, kdykoli mají odpovídající dvě množiny neprázdnou křižovatku, tj.

E(G) = {{proti_i, proti_j} | S_i ∩ S_j ≠ ∅}.

Všechny grafy jsou průsečíky

Jakýkoli neorientovaný graf G mohou být reprezentovány jako průsečíkový graf: pro každý vrchol proti_i z G, tvoří sadu S_i skládající se z hran dopadajících na proti_i; pak dvě takové sady mají neprázdnou křižovatku právě tehdy, pokud odpovídající vrcholy sdílejí hranu. Erdős, Goodman & Pósa (1966) poskytnout konstrukci, která je efektivnější (což znamená, že vyžaduje menší celkový počet prvků ve všech sadách S_i kombinovaný), ve kterém je celkový počet nastavených prvků maximálně n²/ 4 kde n je počet vrcholů v grafu. Přisuzují pozorování, že všechny grafy jsou křižovatkovými grafy Szpilrajn-Marczewski (1945), ale řekněte, že také Čulík (1964). The číslo křižovatky grafu je minimální celkový počet prvků v libovolné křižovatkové reprezentaci grafu.

Třídy křižovatkových grafů

Mnoho důležitých rodin grafů lze popsat jako průsečíkové grafy omezenějších typů množin rodin, například množiny odvozené z nějakého druhu geometrické konfigurace:

An intervalový graf je definován jako průsečíkový graf intervalů na reálné ose nebo spojených podgrafů a graf cesty.
An indiferenční graf lze definovat jako průsečíkový graf jednotkových intervalů na reálné přímce
A kruhový obloukový graf je definován jako průsečík grafu oblouky na kruhu.
A polygonový kruhový graf je definován jako průnik mnohoúhelníků s rohy v kruhu.
Jedna charakteristika a chordální graf je jako průsečíkový graf připojených podgrafů a strom.
A lichoběžníkový graf je definován jako průsečík grafu lichoběžníků vytvořeného ze dvou rovnoběžných čar. Jsou zobecněním pojmu permutační graf, podle pořadí, oni jsou zvláštní případ rodiny doplňků srovnatelné grafy známé jako grafy srovnatelnosti.
A graf jednotkového disku je definován jako průsečík grafu jednotkové disky v letadle.
A kruhový graf je průsečíkový graf množiny akordů kruhu.
The věta o kruhu tvrdí, že rovinné grafy jsou přesně průsečíkové grafy rodin uzavřených disků v rovině ohraničené nepřekračujícími se kruhy.
Scheinermanova domněnka (nyní věta) říká, že každý rovinný graf může být také reprezentován jako průsečík grafu úsečky v letadle. Průsečíkové grafy úsečkových segmentů však mohou být také neplanární a rozpoznávání průsečíkových grafů úsečkových segmentů je kompletní pro existenciální teorie skutečností (Schaefer 2010 ).
The hranový graf grafu G je definován jako průsečík grafů hran G, kde reprezentujeme každou hranu jako množinu jejích dvou koncových bodů.
A řetězcový graf je průsečík grafu křivky v rovině.
Graf má boxicita k pokud je to průsečíkový graf vícerozměrného krabice dimenze k, ale nikoliv menšího rozměru.
A klikový graf je průsečík grafu maximální kliky jiného grafu
A blokový graf klikacího stromu je průsečík grafu vzájemně propojené komponenty jiného grafu

Scheinerman (1985) charakterizoval průnikové třídy grafů, rodiny konečných grafů, které lze popsat jako průnikové grafy množin čerpaných z dané rodiny množin. Je nutné a dostačující, aby rodina měla následující vlastnosti:

Každý indukovaný podgraf grafu v rodině musí být také v rodině.
Každý graf vytvořený z grafu v rodině nahrazením vrcholu a klika musí také patřit do rodiny.
V rodině existuje nekonečná sekvence grafů, z nichž každý je indukovaným podgrafem dalšího grafu v sekvenci, s vlastností, že každý graf v rodině je indukovaným podgrafem grafu v sekvenci.

Pokud reprezentace grafu průsečíku mají další požadavek, že různé vrcholy musí být reprezentovány různými sadami, pak lze vlastnost roztažení kliky vynechat.

Související pojmy

An teoretický řád analogické křižovatkovým grafům jsou objednávky na zařazení. Stejným způsobem, že křižovatková reprezentace grafu označí každý vrchol sadou tak, že vrcholy sousedí právě tehdy, když jejich množiny mají neprázdnou křižovatku, takže inkluzní reprezentace F a poset označí každý prvek sadou tak, aby pro jakýkoli X a y v posetu, X ≤ y kdyby a jen kdyby F(X) ⊆ F(y).

Viz také

Kontaktní graf

Reference

Čulík, K. (1964), „Aplikace teorie grafů na matematickou logiku a lingvistiku“, Teorie grafů a její aplikace (Proc. Sympos. Smolenice, 1963), Praha: Publ. Dům československý akadem. Sci., S. 13–20, PAN 0176940.
Erdős, Paul; Goodman, A. W .; Pósa, Louis (1966), "Reprezentace grafu podle nastavených průsečíků" (PDF), Kanadský žurnál matematiky, 18 (1): 106–112, doi:10.4153 / CJM-1966-014-3, PAN 0186575.
Golumbic, Martin Charles (1980), Algoritmická teorie grafů a dokonalé grafyAkademický tisk, ISBN 0-12-289260-7.
McKee, Terry A .; McMorris, F. R. (1999), Témata v teorii křižovatkových grafůMonografie SIAM o diskrétní matematice a aplikacích, 2, Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku, ISBN 0-89871-430-3, PAN 1672910.
Szpilrajn-Marczewski, E. (1945), „Sur deux propriétés des classes d'ensembles“, Fond. Matematika., 33: 303–307, PAN 0015448.
Schaefer, Marcus (2010), „Složitost některých geometrických a topologických problémů“ (PDF), Grafická kresba, 17. mezinárodní sympozium, GS 2009, Chicago, IL, USA, září 2009, revidované práce, Přednášky v informatice, 5849, Springer-Verlag, str. 334–344, doi:10.1007/978-3-642-11805-0_32, ISBN 978-3-642-11804-3.
Scheinerman, Edward R. (1985), „Charakterizující průsečíkové třídy grafů“, Diskrétní matematika, 55 (2): 185–193, doi:10.1016 / 0012-365X (85) 90047-0, PAN 0798535.

Další čtení

Přehled teorie průsečíkových grafů a důležitých speciálních tříd průsečíkových grafů viz McKee & McMorris (1999).

externí odkazy

Jan Kratochvíl, Video přednáška o křižovatkových grafech (červen 2007)
E. Prisner, Cesta přes křižovatku Graph County