Vkládání grafů - Graph embedding

Heawoodův graf a související mapa vložené do prstence.

V topologické teorie grafů , jako vkládání (také hláskoval vnoření ) části grafu na povrchu je znázornění na , ve kterém body jsou spojeny s vrcholy a jednoduchých oblouků ( homeomorphic představy o ) jsou spojeny s hranami v takovým způsobem, že: ${\ displaystyle G}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle G}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle [0,1]}$

koncové body oblouku spojené s hranou jsou body spojené s koncovými vrcholy ${\ displaystyle e}$ ${\ displaystyle e,}$
žádné oblouky nezahrnují body spojené s jinými vrcholy,
dva oblouky se nikdy neprotínají v bodě, který je uvnitř jednoho z oblouků.

Zde je povrch kompaktní , propojený - potrubí . ${\ displaystyle 2}$

Vložení grafu do povrchu je neformálně vykreslení grafu na povrchu takovým způsobem, že jeho hrany se mohou protínat pouze v jejich koncových bodech. Je dobře známo, že jakýkoli konečný graf lze vložit do trojrozměrného euklidovského prostoru . Rovinný graf je ten, který může být vložen do 2-dimenzionální euklidovském prostoru ${\ displaystyle \ mathbb {R} ^ {3}}$ ${\ displaystyle \ mathbb {R} ^ {2}.}$

Vložení je často považováno za třídu ekvivalence (podle homeomorfismů ) reprezentací právě popsaného druhu. ${\ displaystyle \ Sigma}$

Někteří autoři definují slabší verzi definice „vložení grafu“ tím, že vynechají podmínku bez průniku hran. V takových kontextech je přísnější definice popsána jako „nepřekračující vložení grafu“.

Tento článek se zabývá pouze striktní definicí vkládání grafů. Slabší definici pojednávají články „ kresba grafu “ a „ číslo křížení “.

Terminologie

Pokud je graf vložen na uzavřenou plochu , doplněk spojení bodů a oblouků spojených s vrcholy a hranami je rodina oblastí (nebo ploch ). 2-buňka vkládání , buněčný vkládání nebo mapa je vkládání, ve které každá tvář je homeomorphic k otevřené disk. Uzavřený 2-buňka vkládání je vkládání, ve kterém uzávěr každého obličeje je homeomorphic do uzavřené disk. ${\ displaystyle G}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle G}$

Rod z grafu je minimální celé číslo tak, že graf může být vložen do povrchu rodu . Zejména rovinný graf má rod , protože to může být vypracován na kouli, aniž by self-křížení. Tyto non-orientovatelné rod příslušníky grafu je minimální celé číslo tak, že graf může být vložen do non-orientable povrchu (bez orientovatelné) rodu . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 0}$ ${\ displaystyle n}$ ${\ displaystyle n}$

K Eulerovy rod grafu je minimální celé číslo tak, že graf může být vložen do orientovatelným povrchu (orientovatelné) rodu nebo v non-orientable povrchu (bez orientovatelné) rodu . Graf je orientovatelně jednoduchý, pokud je jeho rod Euler menší než jeho neorientovatelný rod. ${\ displaystyle n}$ ${\ displaystyle n / 2}$ ${\ displaystyle n}$

Maximální rod z grafu je maximální celé číslo tak, že graf může být p-buněk vložené do orientovatelným povrchu rodu . ${\ displaystyle n}$ ${\ displaystyle 2}$ ${\ displaystyle n}$

Kombinatorické vkládání

Vložený graf jednoznačně definuje cyklické řádky hran dopadajících na stejný vrchol. Sada všech těchto cyklických řádů se nazývá rotační systém . Vložení se stejným rotačním systémem se považují za ekvivalentní a odpovídající třída ekvivalence vložení se nazývá kombinatorické vkládání (na rozdíl od termínu topologické vkládání , který odkazuje na předchozí definici, pokud jde o body a křivky). Někdy se samotný rotační systém nazývá „kombinatorické vkládání“.

Vložený graf také definuje přirozené cyklické řádky hran, které tvoří hranice ploch vložení. Zpracování těchto objednávek založených na tvářích je však méně přímočaré, protože v některých případech mohou být některé hrany dvakrát překročeny podél hranice plochy. Například toto je vždy případ vložení stromů, které mají jednu tvář. K překonání této kombinatorické nepříjemnosti lze uvažovat, že každá hrana je podélně „rozdělena“ na dvě „poloviční hrany“ nebo „strany“. Podle této konvence je u všech příčných hraničních ploch tváře každá poloviční hrana překročena pouze jednou a dvě poloviční hrany stejné hrany jsou vždy překročeny v opačných směrech.

Další ekvivalentní reprezentace pro buněčné vložení zahrnují pásový graf , topologický prostor vytvořený slepením topologických disků pro vrcholy a okraje vloženého grafu a graf zakódovaný do grafu , kubický graf v barvě hrany se čtyřmi vrcholy pro každý okraj vložený graf.

Výpočetní složitost

Problém nalezení rodu grafu je NP-tvrdý (problém určení, zda -vertexový graf má rod, je NP-úplný ). ${\ displaystyle n}$ ${\ displaystyle g}$

Současně je problém s rodem grafů fixovatelný s pevnými parametry , tj. Jsou známy polynomiální časové algoritmy, které kontrolují, zda lze graf vložit do povrchu daného fixního rodu, a také najít vložení.

První průlom v tomto ohledu nastal v roce 1979, kdy byly algoritmy časové složitosti O ( n ^{O ( g )} ) nezávisle předloženy Výročnímu sympoziu ACM o teorii výpočetní techniky : jeden I.Filotti a GL Miller a druhý John Reif . Jejich přístupy byly zcela odlišné, ale na návrh programového výboru předložily společný dokument. Nicméně Wendy Myrvold a William Kocay dokázal v roce 2011, že algoritmus dán Filotti, Miller a Reif byl nesprávný.

V roce 1999 bylo oznámeno, že případ fixního rodu lze vyřešit časově lineárně ve velikosti grafu a dvojnásobně exponenciálně v rodu.

Vkládání grafů do prostorů vyšších rozměrů

Je známo, že jakýkoli konečný graf lze vložit do trojrozměrného prostoru.

Jednou z metod, jak toho dosáhnout, je umístit body na libovolnou přímku v prostoru a nakreslit hrany jako křivky, z nichž každá leží ve zřetelné polorovině , přičemž všechny poloroviny mají tuto přímku jako společnou hranici. Vložení jako je toto, ve kterém jsou hrany nakresleny na polorovinách, se nazývá knižní vložení grafu. Tato metafora pochází z představy, že každá z rovin, kde je nakreslena hrana, je jako stránka knihy. Bylo zjištěno, že ve skutečnosti může být na stejné „stránce“ nakresleno několik okrajů; tloušťka kniha grafu je minimální počet halfplanes potřebných pro takovou výkresu.

Alternativně lze libovolný konečný graf nakreslit přímými hranami ve třech rozměrech bez křížení umístěním jeho vrcholů do obecné polohy tak, aby žádné čtyři nebyly koplanární. Toho lze například dosáhnout umístěním i- tého vrcholu do bodu ( i , i ² , i ³ ) momentové křivky .

Vložení grafu do trojrozměrného prostoru, ve kterém nejsou topologicky spojeny žádné dva cykly, se nazývá vložení bez odkazů . Graf má vložení bez odkazů, právě když nemá jeden ze sedmi grafů rodiny Petersenových jako nezletilý .

Galerie

Petersen graf a související mapa vložené do projektivní roviny. Jsou identifikovány protilehlé body v kruhu, které poskytují uzavřený povrch neorientovatelného rodu 1.
Pappus graf a související mapa vložené do prstence.
Kleinův graf stupně 7 a související mapa vložené do orientovatelného povrchu rodu 3.

Viz také

Vkládání , pro jiné druhy vložení
Tloušťka knihy
Tloušťka grafu
Dvojnásobně spojený seznam hran , datová struktura, která představuje graf vložený do roviny
Pravidelná mapa (teorie grafů)
Fáryho věta , která říká, že přímé lineární planární vložení rovinného grafu je vždy možné.
Triangulace (geometrie)

Languages

In other projects