Přednáška prof. Kratochvíla "Diskrétní matematika na prahu 21. století: Věda, umění nebo víra?"

Teorie rovinných grafů patří mezi rodinné stříbro diskrétní matematiky – strukturální Kuratowského věta je pokládána za počátek moderní éry teorie grafů, zatímco lineární algoritmus Hopcrofta a Tarjana na rozpoznávání rovinných grafů zaujímá své pevné místo v síni slávy teoretické informatiky. Visualizace grafů svým estetickým nábojem tvoří první přirozený můstek mezi vědeckými a uměleckými aspekty matematiky. Axiomatická výstavba matematiky je založena na víře v platnost nedokazovaných základních postulátů. V teoretické informatice, ale i v aplikacích dotýkajících se každodenního lidského života, se ale základem čím dál více stává jiná víra: víra v negativní řešení milionového problému P = NP.
V této přednášce představíme tři nedávné příklady zobecnění rovinných grafů a jejich algoritmické aspekty – abstraktní topologické grafy, dokreslování částečně předkreslených grafů a nekřížící se konektory. Těmito konkrétními příklady vyplníme exaktní část přednášky. A (nejen) na těchto příkladech se posluchačům pokusíme demonstrovat některé obecné úvahy předeslané v názvu přednášky.