Planarni grafovi (zadatak)

[crni_macak]

Jeli mi moze molim vas netko objasniti kojim principom mozemo ustanoviti da li je neki graf planaran???

Aj pa ako netko zna neka mi rijesi ova dva zadatka:

1. Dokazite da graf K6 ne moze postati planaran uklanjanjem dva brida.

2. Ispitajte da li je K6,2,2 (potpuni tripartitni graf) planaran graf.

[Luuka]

Tu ti treba Eulerov tm (valjda se to tak zove, ne sjećam se više)... nešto u stilu p-q+r=2 (p broj vrhova, q broj bridova, r broj područja) i ona formula da je 2q=suma svih stupnjjeva vrhova = suma svih stupnjeva područja (valjda)... i onda ocijeniš nekak r iz ovog drugog i pokažeš da to ne može bit planarno... vidi vježbe (ako si slušo diskretnu), ima takvih zadataka, sa K3,3 i K5 mislim.

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy