Homeomorfismus grafů

Dva grafy a jsou homeomorfní , pokud existuje izomorfismus nějakého dělení grafu a nějakého dělení grafu [1] . Pokud jsou hrany grafu chápány jako segmenty spojující vrcholy (jak je obvykle nakresleno na ilustracích), pak jsou dva grafy v kontextu teorie grafů homeomorfní, když jsou homeomorfní v topologickém smyslu.

Rozdělení a vyloučení

Obecně platí, že poddělení grafu G (někdy se používá termín rozšíření [2] nebo poddělení ) je graf získaný dělením hran v G . Rozdělením nějaké hrany e konečnými vrcholy { u , v } vznikne graf obsahující místo hrany e nový vrchol w a dvě hrany { u , w } a { w , v } [1] .

Například hrana e s konci { u , v }:

lze rozdělit na dvě hrany, e 1 a e 2 :

Inverzní operace, eliminující vrchol w s hranami, které k němu přiléhají ( e 1 , e 2 ), nahradí obě hrany sousedící s vrcholem w ( e 1 , e 2 ) novou hranou spojující koncové body dvojice. Je třeba zdůraznit, že tato operace je použitelná pouze pro vrcholy, které jsou incidentní s přesně dvěma hranami.

Například jednoduchý souvislý graf se dvěma hranami e 1 { u , w } a e 2 { w , v }:

má vrchol (pojmenovaný w ), který lze vyloučit, což má za následek:

Určit, zda je graf H homeomorfní k podgrafu G , je NP-úplný problém [3] .

Barycentrické pododdělení

Barycentrické dělení rozděluje každý okraj grafu. Toto je zvláštní druh dělení, které vždy dává bipartitní graf . Tento postup lze opakovat tak, že n-té barycentrické pododdělení je barycentrické pododdělení n-1 pododdělení . Druhé takové dělení je vždy jednoduchý graf .

Vložení do povrchu

Je zřejmé, že dělení grafu zachovává rovinnost. Tvrdí to Pontrjagin-Kuratovského teorém

konečný graf je rovinný právě tehdy, když neobsahuje podgraf homeomorfní k K 5 ( úplný graf s pěti vrcholy ) nebo K 3,3 ( úplný bipartitní graf se šesti vrcholy, z nichž tři jsou spojeny s každým ze zbývajících tři).

Ve skutečnosti se graf homeomorfní ke K 5 nebo K 3,3 nazývá Kuratowski podgraf .

Zobecnění vyplývající z Robertsonovy-Seymourovy věty říká, že pro jakékoli celé číslo g existuje konečná obstrukční množina grafů , takže graf H je vnořitelný do plochy rodu g právě tehdy, když H neobsahuje kopii homeomorfní k nějakému grafu. . Skládá se například z podgrafů Kuratovského.

Příklad

V následujícím příkladu jsou grafy G a H homeomorfní.

G H

Pokud je graf G' vytvořen dělením vnějších hran grafu G a graf H' je vytvořen dělením vnitřních hran grafu H, pak G' a H' mají podobná grafická znázornění:

G', H'

Mezi grafy G' a H' tedy existuje izomorfismus, což znamená, že G a H jsou homeomorfní.

Viz také

Poznámky

  1. ↑ 1 2 Yablonsky, 1986 , str. 225.
  2. ↑ Trudeau, 1993 , s. 76, definice 20.
  3. ↑ Šířeji studovaný problém v literatuře nazvaný „problém homeomorfismu podgrafu“ se ptá, zda pododdělení grafu H je izomorfní s podgrafem G . Jestliže H je cyklus s n vrcholy, problém je ekvivalentní k nalezení Hamiltonova cyklu , a je proto NP-úplný. Tato formulace je však pouze ekvivalentní otázce, zda je graf H homeomorfní k podgrafu G , když H neobsahuje vrcholy druhého stupně, protože to neumožňuje výjimku v H. Mírnou úpravou hamiltonovského cyklu lze ukázat, že daný problém je NP-úplný - přidáme každý jeden vrchol v H a G sousedící se všemi ostatními vrcholy. Pak graf G zvětšený o jeden vrchol obsahuje podgraf homeomorfní ke kolu s ( n  + 1) vrcholy právě tehdy, když G je hamiltonovský. Pro složitost problému homeomorfismu podgrafu viz článek LaPaugha a Rivesta ( LaPaugh, Rivest 1980 ).

Literatura