Zakázaná charakterizace grafu - Forbidden graph characterization

v teorie grafů, obor matematiky, lze mnoho důležitých rodin grafů popsat konečnou sadou jednotlivých grafů, které do rodiny nepatří, a dále z rodiny vyloučit všechny grafy, které obsahují některý z těchto zakázaných grafů jako (indukovaný) podgraf nebo vedlejší. Prototypovým příkladem tohoto jevu je Kuratowského věta, který uvádí, že graf je rovinný (lze nakreslit bez křížení v rovině) právě tehdy, pokud neobsahuje žádný ze dvou zakázaných grafů, kompletní graf K.₅ a kompletní bipartitní graf K._3,3. Pro Kuratowského teorém je pojem zadržení pojem graf homeomorfismus, ve kterém se dělení jednoho grafu jeví jako podgraf druhého. Každý graf tedy má buď rovinný výkres (v takovém případě patří do rodiny rovinných grafů), nebo má podoblast jednoho z těchto dvou grafů jako podgraf (v takovém případě nepatří do rovinných grafů).

Definice

Obecněji, a zakázaná charakterizace grafu je metoda upřesnění rodina graf nebo hypergraf, struktury, zadáním substruktur, u nichž je zakázáno existovat v jakémkoli grafu v rodině. Různé rodiny se liší v povaze toho, co je zakázáno. Obecně struktura G je členem rodiny ${displaystyle {mathcal {F}}}$ kdyby a jen kdyby zakázaná spodní konstrukce je ne obsaženo v G. The zakázaná spodní konstrukce může být jedním z:

• podgrafy, menší grafy získané z podmnožin vrcholů a hran většího grafu,
• indukované podgrafy, menší grafy získané výběrem podmnožiny vrcholů a použitím všech hran s oběma koncovými body v této podmnožině,
• homeomorfní podgrafy (nazývané také topologické nezletilé ), menší grafy získané z podgrafů sbalením cest vrcholů druhého stupně k jednotlivým okrajům, nebo
• nezletilí v grafu, menší grafy získané ze subgrafů libovolně kontrakce hran.

Soubor struktur, jejichž členství v dané rodině grafů je zakázáno, lze také nazvat an překážková sada pro tu rodinu.

Zakázané charakterizace grafů mohou být použity v algoritmy pro testování, zda graf patří do dané rodiny. V mnoha případech je možné testovat v polynomiální čas zda daný graf obsahuje některého z členů sady překážek, a tedy zda patří do rodiny definované touto sadou překážek.

Aby rodina mohla mít zakázanou charakterizaci grafu, musí být u konkrétního typu spodní stavby rodina uzavřena pod spodními konstrukcemi. To znamená, že každá spodní struktura (daného typu) grafu v rodině musí být jiným grafem v rodina. Ekvivalentně, pokud graf není součástí rodiny, musí být z rodiny vyloučeny také všechny větší grafy, které jej obsahují jako podstrukturu. Pokud je to pravda, vždy existuje sada překážek (sada grafů, které nejsou v rodině, ale jejichž menší podstruktury všechny patří do rodiny). Pro některé představy o tom, co je to spodní konstrukce, by však tato sada překážek mohla být nekonečná. The Věta Robertson – Seymour dokazuje, že pro konkrétní případ nezletilí v grafu Rodina uzavřená pod nezletilými má vždy omezenou překážku.

Seznam zakázaných charakterizací pro grafy a hypergrafy

Rodina	Překážky	Vztah	Odkaz
Lesy	smyčky, páry rovnoběžných hran a cykly všech délek	podgraf	Definice
	smyčka (pro multigrafy) nebo trojúhelník K.3 (pro jednoduché grafy)	graf minor	Definice
Grafy bez drápů	hvězda K.1,3	indukovaný podgraf	Definice
Srovnatelné grafy		indukovaný podgraf
Grafy bez trojúhelníků	trojúhelník K.3	indukovaný podgraf	Definice
Rovinné grafy	K.5 a K.3,3	homeomorfní podgraf	Kuratowského věta
	K.5 a K.3,3	graf minor	Wagnerova věta
Vnější rovinné grafy	K.4 a K.2,3	graf minor	Diestel (2000),[1] p. 107
Vnější 1-planární grafy	šest zakázaných nezletilých	graf minor	Auer a kol. (2013)[2]
Grafy pevné rod	konečná překážková sada	graf minor	Diestel (2000),[1] p. 275
Apexové grafy	konečná překážková sada	graf minor	[3]
Propojitelně integrovatelné grafy	The Petersenova rodina	graf minor	[4]
Bipartitní grafy	liché cykly	podgraf	[5]
Chordální grafy	cykly o délce 4 nebo více	indukovaný podgraf	[6]
Perfektní grafy	cykly liché délky 5 nebo více nebo jejich doplňuje	indukovaný podgraf	[7]
Čárový graf grafů	devět zakázaných podgrafů (vypsáno tady )	indukovaný podgraf	[8]
Odbory grafů z kaktusové grafy	čtyři vrcholy diamantový graf vytvořený odstraněním hrany z kompletní graf K.4	graf minor	[9]
Žebříkové grafy	K.2,3 a jeho duální graf	homeomorfní podgraf	[10]
Rozdělit grafy	${displaystyle C_ {4}, C_ {5}, {ar {C}} _ ​​{4} vlevo (= K_ {2} + K_ {2} vpravo)}$	indukovaný podgraf	[11]
2 připojené sériově paralelní (šířka stromu ≤ 2, šířka větve ≤ 2)	K.4	graf minor	Diestel (2000),[1] p. 327
Šířka stromu ≤ 3	K.5, osmistěn, pětiúhelníkový hranol, Wagnerův graf	graf minor	[12]
Šířka větve ≤ 3	K.5, osmistěn, krychle, Wagnerův graf	graf minor	[13]
Doplňkově redukovatelné grafy (grafy)	4-vrcholová cesta P4	indukovaný podgraf	[14]
Triviálně dokonalé grafy	4-vrcholová cesta P4 a 4-vrcholný cyklus C4	indukovaný podgraf	[15]
Prahové grafy	4-vrcholová cesta P4, 4-vrcholný cyklus C4a doplněk C4	indukovaný podgraf	[15]
Čárový graf 3 uniformních lineárních hypergrafů	konečný seznam zakázaných indukovaných podgrafů s minimálním stupněm alespoň 19	indukovaný podgraf	[16]
Čárový graf k-jednotné lineární hypergrafy, k > 3	konečný seznam zakázaných indukovaných podgrafů s minimálním stupněm okraje alespoň 2k2 − 3k + 1	indukovaný podgraf	[17][18]
Grafy ΔY-redukovatelné do jediného vrcholu	konečný seznam nejméně 68 miliard odlišných (1,2,3) klikových částek	graf minor	[19]
Obecné věty
Rodina definovaná an indukované dědičné vlastnictví	a, možná neomezená, překážková sada	indukovaný podgraf
Rodina definovaná a drobný dědičný majetek	konečná překážková sada	graf minor	Věta Robertson – Seymour

Viz také

• Erdős – Hajnalův dohad
• Zakázaný problém podgrafu
• Matroid menší
• Zarankiewiczův problém

Reference