Kaavio homeomorfismi

Kaksi graafia ja ovat homeomorfisia , jos graafin jollakin alajaolla on isomorfismi ja graafin jokin alajako [ 1] . Jos graafin reunat ymmärretään pisteitä yhdistäviksi segmenteiksi (kuten kuvissa yleensä piirretään), niin kaksi graafia ovat homeomorfisia graafiteorian kontekstissa, kun ne ovat homeomorfisia topologisessa mielessä .

Alajako ja poissulkeminen

Yleensä graafin G alajako (joskus käytetään termiä laajennus [2] tai osajako ) on graafi, joka saadaan jakamalla G :n reunat . Jakamalla jonkin reunan e loppupisteillä { u , v } saadaan graafi, joka sisältää uuden kärjen w ja kaksi reunaa { u , w } ja { w , v } reunan e sijasta [1] .

Esimerkiksi reuna e , jonka päät ovat { u , v }:

voidaan jakaa kahteen reunaan, e 1 ja e 2 :

Käänteisoperaatio eliminoi kärjen w ja siihen kohdistuvat reunat ( e 1 , e 2 ), korvaa molemmat kärjen w viereiset reunat ( e 1 , e 2 ) uudella reunalla, joka yhdistää parin päätepisteet. On korostettava, että tätä operaatiota voidaan soveltaa vain pisteisiin, joissa on täsmälleen kaksi reunaa.

Esimerkiksi yksinkertainen yhdistetty graafi , jossa on kaksi reunaa e 1 { u , w } ja e 2 { w , v }:

sillä on kärkipiste (nimeltään w ), joka voidaan sulkea pois, mikä johtaa:

Sen määrittäminen, onko graafi H homeomorfinen aligraafin G kanssa, on NP-täydellinen tehtävä [3] .

Barysentriset alajaot

Barysentrinen alajako jakaa graafin jokaisen reunan. Tämä on erityinen alajako, joka antaa aina kaksiosaisen graafin . Tämä menettely voidaan toistaa siten, että n:s barysentrinen alajako on n-1- alajaon barysentrinen alajako . Toinen tällainen jako on aina yksinkertainen graafi .

Upotus pintaan

On ilmeistä, että graafin jakaminen säilyttää tasomaisuuden. Pontryagin-Kuratovsky-lause sanoo sen

äärellinen graafi on tasainen silloin ja vain, jos se ei sisällä aligraafia , joka on homeomorfinen K 5 :lle ( täydellinen graafi , jossa on viisi kärkeä ) tai K 3,3 ( täydellinen kaksiosainen graafi , jossa on kuusi pistettä, joista kolme on kytketty kuhunkin jäljellä olevaan pisteeseen kolme).

Itse asiassa K 5 :n tai K 3,3 :n homeomorfista graafia kutsutaan Kuratowskin aligraafiksi .

Robertson-Seymourin lauseesta seuraava yleistys väittää, että mille tahansa kokonaisluvulle g on olemassa äärellinen obstruktiivinen graafien joukko siten, että graafi H on upotettava g -suvun pintaan silloin ja vain, jos H ei sisällä kopiota, joka on homeomorfinen jollekin graafille. . Se koostuu esimerkiksi Kuratovskin aligraafista.

Esimerkki

Seuraavassa esimerkissä graafit G ja H ovat homeomorfisia.

G H

Jos kuvaaja G' luodaan jakamalla graafin G ulkoreunat ja graafi H' luodaan jakamalla graafin H sisäreunat, niin G':llä ja H':llä on samanlaiset graafiset esitykset:

G', H'

Siten graafien G' ja H' välillä on isomorfismi, mikä tarkoittaa, että G ja H ovat homeomorfisia.

Katso myös

Muistiinpanot

  1. ↑ 1 2 Yablonsky, 1986 , s. 225.
  2. ↑ Trudeau, 1993 , s. 76, määritelmä 20.
  3. ↑ Kirjallisuudessa laajemmin tutkittu ongelma, jota kutsutaan "aligraafin homeomorfismin ongelmaksi", kysyy, onko graafin H osa-alue isomorfinen aligraafin G kanssa . Jos H on sykli, jossa on n kärkeä, ongelma vastaa Hamiltonin syklin löytämistä ja on siksi NP-täydellinen. Tämä muotoilu vastaa kuitenkin vain kysymistä, onko graafi H homeomorfinen aligraafin G kanssa, kun H ei sisällä kakkosasteen pisteitä, koska tämä ei salli H : n poikkeusta. Hamiltonin sykliä hieman modifioimalla voidaan osoittaa, että annettu tehtävä on NP-täydellinen - lisäämme kumpaankin kärkeen H :ssa ja G :ssä kaikkien muiden kärkien viereen. Sitten yhdellä kärjellä korotettu graafi G sisältää aligraafin, joka on homeomorfinen pyörälle , jolla on ( n  + 1) -pisteet, jos ja vain jos G on Hamiltonin. Aligraafin homeomorfismiongelman monimutkaisuudesta, katso LaPaughin ja Rivestin artikkeli ( LaPaugh, Rivest 1980 ).

Kirjallisuus