Ctvrtek 9:00 - S1
Přednášíme společně s dr. Jelínkem a dr. Rutterem.
27.2.2014
Dotykove a viditelnostni reprezentace rovinnych bipartitinich grafu
Kazdy 2-souvisly rovinny graf ma tzv. viditelnostni reprezentaci, v niz vrcholy jsou reprezentovany vodorovnymi useckami, steny svislymi useckami a hrany obdelniky jimi ohranicenymi. Pritom se zadne usecky neprotinaji, vodorovna usecka (prislusna vrcholu v) se dotyka svisle usecky (odpovidajici stene s) tehdy a jen tehdy, kdyz v lezi na hranici steny s.
Kazdy rovinny bipartitini graf ma dotykovou reprezentaci pomoci vodorovnych a svislych usecek. (Smery odpovidaji nalezeni do partit.)