ЦГТА семинар, 13. март 2012.

• 12. Март, 2012
• Коментари (0)

Наредни састанак ЦГТА семинара одржаће се у уторак, 13. марта 2012, од 18:00 - 20:00 часова на Математичком факултету, IV спрат (пројектор сала)

Предавач: Коста Дошен, Математички институт САНУ:

Наслов предавања: Критеријум планарности за графове

Садржај: Доказано је да је повезани граф планаран ако и само ако су сви његови коциклови са бар четири ивице ,,засновани'' у графу. Појам заснованости у том критеријуму за планарност, који је чисто комбинаторан, потиче од интуитивне идеје да код  планарности треба да постоји линеарно уређење ивица коцикла такво да у два подграфа који остају после одстрањивања тих ивица не сме да буде укртштања дисјунктних путева који повезују чворове тих ивица. За смер здесна улево горње еквиваленције доказ који ће бити дат заснива се на Куратовсковљевој теореми о планарности која говори о графовима K_{3,3} и K_5, али сам критеријум не спомиње K_{3,3} и К_5. Показује се да су још неке варијанте критеријума нужне и довољне за планарност.