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 však 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í prof. Kratochvíl 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í exaktní část přednášky. A (nejen) na těchto příkladech se posluchačům pokusí demonstrovat některé obecné úvahy předeslané v názvu přednášky.
Prof. RNDr. Jan Kratochvíl, CSc. je absolventem pardubického gymnázia Dašická. Vystudoval MFF UK, kde potom působil nejprve na katedře algebry a později na katedře aplikované matematiky. Jeho vědecká práce je zaměřena především na oblast diskrétní matematiky a teoretické informatiky. Absolvoval několik delších pobytů v USA a Austrálii a řadu kratších pobytů v mnoha dalších zemích. Je autorem 100 odborných článků a řady konferenčních příspěvků, včetně 12 zvaných plenárních přednášek na mezinárodních konferencích. Roku 2012 byl zvolen děkanem MFF UK.
Ve čtvrtek 21. listopadu 2013 od 17 hodin v posluchárně B1 (Dopravní fakulty Jana Pernera) Univerzity Pardubice. Pořádá JČMF Pardubice. Vstup volný.