Etusivu

Joukko-oppia

Relaatiot

Funktiot

Relaatioden ominaisuuksia

Järjestysrelaatiot

Ekvivalenssiluokat

Verkkojen
isomorfisuus

Eulerin kaava
verkoille

Kuratowskin lause

Ohje

Kuratowskin lause, osa 2

Kuratowskin lauseen mukaan äärellinen verkko on tasoverkko, jos ja vain jos se ei sisällä
yhtään sellaista aliverkkoa, joka voidaan muuntaa verkoksi, joka on isomorfinen Kuratowskin
verkon K5 tai K3,3 kanssa. Muuntaminen voidaan tehdä seuraavilla keinoilla

1) Poistetaan silmukat ja rinnakkaiset kaaret

2) Poistetaan 2-asteinen solmu ja yhdistetään siihen liittyneet kaaret.

3) Kaari kutistetaan pisteeksi, jolloin kaaren päät yhtyvät yhdeksi solmuksi.

Huomaa, että keinon 3) käyttämisessä on oltava varovainen. Se saattaa muuttaa avaruusverkon
tasoverkoksi!

Esimerkiksi alla oleva verkko on avaruusverkko (siis ei ole tasoverkko). Sovelletaan ensin
kohtaa 2) solmuihin s7 ja s8. Poistamalla solmut s9 ja s10 muodostetaan verkon aliverkko,
joka on selvästi isomorfinen Kuratowskin verkon K3,3 kanssa

Tehtävä. Onko seuraava verkko tasoverkko?

Vielä eräs uusi asia