CGTA seminar, 13. mart 2012.

• 12. Mart,  2012
• Komentari (0)

Naredni sastanak CGTA seminara održaće se u utorak, 13. marta 2012, od 18:00 - 20:00 časova na Matematičkom fakultetu, IV sprat (projektor sala)

Predavač: Kosta Došen, Matematički institut SANU:

Naslov predavanja: Kriterijum planarnosti za grafove

Sadržaj: Dokazano je da je povezani graf planaran ako i samo ako su svi njegovi kociklovi sa bar četiri ivice ,,zasnovani'' u grafu. Pojam zasnovanosti u tom kriterijumu za planarnost, koji je čisto kombinatoran, potiče od intuitivne ideje da kod  planarnosti treba da postoji linearno uredjenje ivica kocikla takvo da u dva podgrafa koji ostaju posle odstranjivanja tih ivica ne sme da bude ukrtštanja disjunktnih puteva koji povezuju čvorove tih ivica. Za smer zdesna ulevo gornje ekvivalencije dokaz koji će biti dat zasniva se na Kuratovskovljevoj teoremi o planarnosti koja govori o grafovima K_{3,3} i K_5, ali sam kriterijum ne spominje K_{3,3} i K_5. Pokazuje se da su još neke varijante kriterijuma nužne i dovoljne za planarnost.

---