Graf homøomorfi

To grafer og er homøomorfe , hvis der er en isomorfi af en underinddeling af grafen og en underinddeling af grafen [1] . Hvis kanterne på en graf forstås som segmenter, der forbinder hjørner (som det normalt tegnes i illustrationer), så er to grafer homøomorfe i grafteori-sammenhæng, når de er homøomorfe i topologisk forstand.

Underinddeling og udelukkelse

Generelt er en underinddeling af en graf G (nogle gange bruges udtrykket forlængelse [2] eller underinddeling ) en graf, der opnås ved at dividere kanter i G . At dividere nogle kant e med endelige hjørner { u , v } giver en graf, der indeholder et nyt toppunkt w og to kanter { u , w } og { w , v } i stedet for kant e [1] .

For eksempel kant e med ender { u , v }:

kan opdeles i to kanter, e 1 og e 2 :

Den omvendte operation, der eliminerer toppunktet w med kanter, der falder ind dertil ( e 1 , e 2 ), erstatter begge kanter , der støder op til toppunktet w ( e 1 , e 2 ) med en ny kant, der forbinder parrets endepunkter. Det skal understreges, at denne operation kun er anvendelig for toppunkter, der er indfaldende med nøjagtig to kanter.

For eksempel en simpel forbundet graf med to kanter e 1 { u , w } og e 2 { w , v }:

har et toppunkt (kaldet w ), der kan udelukkes, hvilket resulterer i:

At bestemme om en graf H er homøomorf til en subgraf G er et NP-komplet problem [3] .

Barycentriske underafdelinger

Den barycentriske underinddeling opdeler hver kant af grafen. Dette er en speciel form for underopdeling, der altid giver en todelt graf . Denne procedure kan gentages, så den n'te barycentriske underafdeling er den barycentriske underafdeling af n-1 underafdelingen . Den anden opdeling er altid en simpel graf .

Indlejring i en overflade

Det er indlysende, at underinddeling af grafen bevarer planheden. Pontryagin-Kuratovsky-sætningen siger det

en finit graf er plan , hvis og kun hvis den ikke indeholder en subgraf , der er homøomorf til K 5 ( fuldstændig graf med fem hjørner ), eller K 3,3 ( komplet todelt graf med seks spidser, hvoraf tre er forbundet med hver af de resterende tre).

Faktisk kaldes en graf, der er homøomorf til K 5 eller K 3,3 , en Kuratowski-undergraf .

Generaliseringen efter Robertson-Seymour- sætningen siger, at der for ethvert heltal g eksisterer et begrænset obstruktivt sæt af grafer , således at grafen H kan indlejres i en overflade af slægten g , hvis og kun hvis H ikke indeholder en kopi homøomorf til en graf . For eksempel består den af ​​Kuratovsky-undergrafer.

Eksempel

I det følgende eksempel er graferne G og H homøomorfe.

G H

Hvis grafen G' er skabt ved at underinddele de ydre kanter af graf G, og grafen H' skabes ved at underinddele de indre kanter af graf H, så har G' og H' lignende grafiske repræsentationer:

G', H'

Der er således en isomorfi mellem graferne G' og H', hvilket betyder, at G og H er homøomorfe.

Se også

Noter

  1. ↑ 1 2 Yablonsky, 1986 , s. 225.
  2. ↑ Trudeau, 1993 , s. 76, definition 20.
  3. ↑ Et mere udbredt undersøgt problem i litteraturen kaldet "subgraph homeomorphism problem" spørger, om en underopdeling af en graf H er isomorf til en subgraf G . Hvis H er en cyklus med n toppunkter, svarer problemet til at finde en Hamiltonsk cyklus , og er derfor NP-komplet. Denne formulering svarer dog kun til at spørge, om en graf H er homøomorf til en undergraf G , når H ikke indeholder hjørner af grad to, da dette ikke tillader en undtagelse i H. Det kan påvises, at det givne problem er NP-komplet ved at ændre den Hamiltonske cyklus en smule - vi tilføjer et toppunkt hver i H og G ved siden af ​​alle andre toppunkter. Så indeholder grafen G øget med et toppunkt en subgraf, der er homøomorf til et hjul med ( n  + 1) hjørner, hvis og kun hvis G er Hamiltonsk. For kompleksiteten af ​​subgraf homeomorphism problem, se papiret af LaPaugh og Rivest ( LaPaugh, Rivest 1980 ).

Litteratur