Etusivu

Joukko-oppia

Relaatiot

Funktiot

Relaatioden ominaisuuksia

Järjestysrelaatiot

Ekvivalenssiluokat

Verkkojen
isomorfisuus

Eulerin kaava
verkoille

Kuratowskin lause

Ohje

Kuratowskin lause, osa 1

Kuratowskin verkot K3,3 ja K5 (alla) ovat äärellisiä avaruusverkkoja. Se, että kyseessä on
avaruusverkko, voidaan todistaa esimerkiksi seuraavan tunnetun tuloksen avulla:

Tasoverkolle, jossa on n ≥ 3 solmua ja m kaarta, pätee
m ≤ 3n - 6.
 Huomaa, että yhtälö pätee joillekin avaruusverkoille, mutta jos se ei päde, on verkko varmasti
avaruusverkko.

Voidaan helposti huomata, että verkossa K5 on 5 solmua ja 10 kaarta, joten yllä esitetty
epäyhtälö ei päde (3·5 - 6 = 9 < 10 ). Mutta verkossa K3,3 on 6 solmua ja 9 kaarta, joten
epäyhtälö pätee (3·6 - 6 = 12 > 9). Pohdi, miten se voidaan todistaa avaruusverkoksi!

Seuraava