Test planarnosti

[Geliriell]

Treba mi neki algoritam za testiranje planarnosti grafova. Bilo bi odlicno ako netko zna web stranicu, ali moze i preporuka neke knjige.

[Maroje]

http://en.wikipedia.org/wiki/Planarity_testing

_________________
Crikey!

[Geliriell]

Tu nema algoritama. Samo su navedene njihova imena i generalna ideja.
Takodjer, sve knjige koje sam do sada nasla o algoritmima ili o teoriji grafova, dodju do dijela o planarnosti i kazu nesto u stilu: "Ti algoritmi su prekomplicirani i necemo ih ovdje opisati."

[Luuka]

Koliko se ja sjećam kod planarnosti, u svakom grafu tražiš neki podgraf koji bi bio nešto slično K_{3,3} recimo... izbacuješ neke vrhove, uzmeš samo neek vrhove pa inducirani podgraf i sl... ako postoji podgraf koji je k33 onda nije planaran... to je dosta često palilo.

_________________
"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

[Maroje]

[Geliriell]

Moram napisati program koji ispituje poizvoljan graf.

[Luuka]

Možda da nekak Eulerovu formulu iskoristiš... ona vrijedi za planaran, pa ako tvoj graf nju ne zadovoljava onda nije.

Treba ti samo broj vrhova, bridova i područja... imaš i nju tamo na onom linku na wikipediju.

možda možeš s tim

_________________
"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

[krcko]

Joj Luuka daj ne lupetaj. Kako mozes prebrojati broj podrucja u opcem grafu?

Kriterij planarnosti preko podgrafova K_5 i K_3,3 (i njihovih subdivizija) zvuci jednostavno, ali nije nimalo jednostavan za provjeriti algoritamski. Jos ako se hoce napraviti efikasan program (koji radi u polinomijalnom vremenu - moze se postici linearno!) onda je zbilja "tehnicki zatjevno". Zato u vecini knjiga samo spomenu da se to moze i preskoce detalje.

Moj savjet je krenuti od Wikipedije i pogledati reference do kojih se moze doci. Mozda u nekoj ima razuman opis algoritma. Matematika koju citate u knjigama znatno je vise izbrusena od one iz clanaka. No ako zelite biti matematicari morate nauciti a) pretrazivati literaturu (tj. clanke - dok dodje do knjiga treba cekati puno godina) b) citati tekstove koji stilski nisu savrseni, koriste tehnicki zargon i pozivaju se na hrpu rezultata iz drugih clanaka.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[Luuka]

[Geliriell]

Ako je v = |V|, e = |E|, da li vrijedi: v >= e => graf je planaran, s tim da ne dopustamo trivijalne vrhove (one koji ne sadrze bridove)?

[krcko]

Ne mora biti ako nemas povezanost. Mozes uzeti K_5 i nabiti kraj toga hrpu "stapica" (dva vrha i jedan brid nepovezani s ostatkom). Zapravo, trebalo bi ti neko ogranicenje na broj komponenti povezanosti (povezanost je prejak uvjet).

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.