Na univerzitě Concordia o něm napsali, že je cestující profesor. Matematik Václav Chvátal zasvětil velkou část profesního života úloze známé jako problém obchodního cestujícího. Také on sám několikrát měnil působiště. Z komunistického Československa uprchl v roce 1968 do Kanady, řadu let žil také v USA. Bylo to nádherné dobrodružství, říká o své emigraci. Uznávaný matematik se vloni stal hostujícím profesorem na UK.
Po kolika letech se vracíte zpátky na Matematicko-fyzikální fakultu?
Po 51 letech.
V 60. letech jste na Matfyzu studoval. Co se vám vybaví z té doby?
Byla to magická doba. Semafor, Reduta, Činoherní klub. Československá nová vlna. Praskání ledů, které nakonec vyvrcholilo jarem ’68. Tou dobou vznikla moje přátelství s Josefem Škvoreckým a Ivanem Vyskočilem. Jsem vděčný, že jsem mohl brát rozum v tom neopakovatelném a vzrušujícím ovzduší.
Byla to zlatá éra i pro fakultu?
Pro mě a několik mých spolužáků určitě. Zdeněk Hedrlín, tehdy odborný asistent, pro nás vedl problémový seminář a pod jeho vedením jsme napsali svoje první články. Hedrlín byl mimořádný pedagog. Jeho jiskra byla lékem proti mindrákům a zkostnatělosti z dob Rakousko-Uherska.
V čem byl jako pedagog jiný?
Nevím o jiném pedagogovi, který v Praze v šedesátých letech zadával 18letým studentům otevřené problémy, a když je vyřešili, dovedl je k publikaci toho řešení pod jejich vlastním jménem. Učil nás sebejistotě hraničící až s drzostí. Jeho přístup k životu mi připomíná jedno z hesel pařížských studentů v květnu 68: Buďte realisti. Žádejte nemožné.
Jak vás ovlivnil?
Udělal pro mě mnoho neobyčejně dobrého. Ale taky mě ovlivnil jinak. Tou dobou jsem hodně přemýšlel o smyslu života, protože jsem nechtěl promarnit ten svůj. Cítil jsem, že daleko líp než matematika by ho naplnilo psaní povídek a románů nebo natáčení filmů. Proto jsem Hedrlínovi začátkem třetího ročníku za všechno poděkoval a řekl mu, že v práci s ním pokračovat nechci, i když Matfyz dodělám, abych nezklamal rodiče. To vyvolalo oheň na střeše. Jako by měl přijít o svého oblíbeného závodního koně. Líčil mi, jak špatně skončím, když matematiku opustím, a vábil mě, jak krásně se budu mít, když u ní zůstanu. Dokonce mi vyjednal doktorandské stipendium na univerzitě v Chicagu. Byl jsem proti jeho argumentům bezmocný, ale nechtěl jsem jejich závěry přijmout. Cítil jsem ten rozpor jako zápas o mou duši. Ten jsem nakonec vyhrál: před promocí na jaře 1968 jsem s díky odmítl to americké stipendium a chystal jsem se k přihlášce na FAMU. Ale potom přišla bratrská invaze a všechno dopadlo jinak.
Ve 22 letech, tři dny po srpnové invazi, jste emigroval do Kanady. Bylo to těžké rozhodnutí?
Vůbec ne. Samotného mě překvapilo, jak rychle a zásadně jsem změnil názor. Jednoho dne jsem se ještě radoval z Prahy, a za dva dny potom mi už bylo absolutně jasné, že tady zůstat nechci.
Jak se vám tím změnil život?
K lepšímu. Díky emigraci jsem poznal lidi a města, ve kterých jsem se našel.
Proč jste si vybral za cíl právě Kanadu?
To vyšlo vylučovací metodou. Po přejezdu rakouských hranic 24. srpna 1968 jsme - moje první manželka a já - spali v táboře pro české migranty ve Vídni a vydělávali si mytím nádobí v nemocnici. Přitom jsme obešli tři konzuláty - americký, australský a kanadský. V tom druhém a třetím s námi jednali jako s lidmi a kvůli tomu kontrastu, nebe a dudy, jsme vyškrtli USA ze seznamu. Australané nám nabídli, že nám zaplatí letenky k nim, a pokud by se nám u nich nelíbilo, po dvou letech zase letenky kamkoli jinam na zeměkouli. Z toho jsem byl nadšením bez sebe, ale manželka se rozplakala, že by to bylo příliš daleko od rodičů. Takže zbyla Kanada. A jsem moc rád, že to tak dopadlo.
Dařilo se vám hned od začátku?
Dařilo. Už v tom lágru to bylo fajn. Když vynechám americké úředníky, všichni ostatní na nás, emigranty z východního bloku, hleděli jako na normální lidi. Kolegové mě brali takového, jaký jsem.
V Kanadě jste v matematice pokračoval. Na University of Waterloo jste obhájil doktorát. Střídavě jste pak působil na kanadských a amerických univerzitách. Které místo vám nejvíc přirostlo k srdci?
Tři města, kde se cítím skutečně doma, jsou v abecedním pořádku Montreal, Paříž a Tokio. Především kvůli lidem. Je mi blízká jejich mentalita - radost ze života, hravost a ohleduplnost vůči bližním.
„Dlouho jsem nechápal, co přesně znamená pojem soul amerických černochů, než mi došlo, že právě duše je to, co mi v USA chybí“
Kdy se vám naskytla příležitost poznat blíž Paříž a Tokio?
Paříž jsem navštívil poprvé v roce 1970, Tokio o devět let později. V 70. a 80. letech jsem tam pravidelně jezdil, někdy na deset dní, jindy třeba na celý semestr. Paříž a Francii mi daroval Claude Berge [matematik, jeden ze zakladatelů moderní kombinatoriky a teorie grafů; pozn. red.], Tokio a Japonsko zase Jin Akiyama [emeritní profesor Tokai University a ředitel centra pro výuku a studium matematiky na Tokyo University of Science; pozn. red.]. Je to umění, darovat někomu město nebo zemi. Vším svým chováním říkáte tomu obdarovanému: Sem patříš stejně jako já. Tady je všechno tvoje stejně jako moje. A na někom, kdo by snad nesouhlasil, nám vůbec nemusí záležet. Jak Claude, tak Jin v tom byli virtuózní.
Ve Spojených státech jste neměl ten pocit?
V Kalifornii na jaře 1972 asi měl, ale krátce po příjezdu na Rutgers v roce 1986 mi konečně došlo, že do USA nepatřím. Přesto je mezi mými nejbližšími kamarády i několik Američanů. Těm se obdivuju, že v takové zemi vyrostli v tak vzácné lidi, a znovu mi to ukazuje, jak scestné jsou národní stereotypy.
Co vám nevyhovovalo ve Spojených státech, potažmo na Rutgers?
Komplex vícecennosti, jakým trpí i další velmoci. Mnozí tam těžko řeknou „United States” bez automatického dodatku „the best country in the world”. Občas se tam vyskytne výrok „I am a better American than you”, který stojí za rozbor. Neschopnost brát své přebujelé vlastenectví s humorem. Davový útěk do uniformity předepsané v televizi. Dlouho jsem nechápal, co přesně znamená pojem soul amerických černochů, než mi došlo, že právě duše je to, co mi v USA chybí, nejspíš stejně jako chybí jim v tamější většinové společnosti.
Na Rutgers jsme jednou rozhodovali o prodloužení pracovní smlouvy mladšího kolegy jménem Chris. Ten vybočoval z normy například tím, že žil v komunitě, která měla svého guru. Při projednávání jeho případu, v jeho nepřítomnosti, na něj několik kolegů vytáhlo pomluvy, které opakovaným tříbením získaly hodnost faktů. Tak jsme se dozvěděli, že Chris je členem kultu, kterému musí odevzdávat 60 % svého platu, a těch 60 % se během diskuse vyšplhalo na 90 %. Bylo pro mne poučné pozorovat, jak se dělá hon na čarodějnice. Ale znepokojilo mě sdělení, že nechal svého doktoranda krátce před obhajobou jeho disertace bez pomoci a odletěl za svým guru na ostrov v jižním Pacifiku. Když jsem se na to Chrise přeptal, vysvětlil mi, jak to bylo doopravdy. Zmíněný ex-doktorand pak poslal našemu oddělení prohlášení, že by si nedovedl představit ohleduplnějšího a nápomocnějšího školitele. Kolegové byli připraveni Chrise uklovat a já jsem jim to takhle pokazil. Při následující schůzi jsem byl oficiálně pokárán za narušení důvěrnosti jednání.
Přesto jste na Rutgers strávil skoro 20 let…
Na Rutgers mě zlákali nabídkou daleko lepšího místa. Kvůli němu jsem si vyžádal na McGillu dvouletou neplacenou dovolenou. Po jejím vypršení mi řekl vedoucí naší katedry, že po dalších dvou letech má vzniknout na McGillu stejně dobrá pozice, jako ta na Rutgers, a ujistil mě, že ta bude čekat na mě. Ta pozice skutečně vznikla, ale na poslední chvíli ji zabral děkan pro svého vlastního kandidáta. Tehdy jsem se ještě mohl vrátit na svoje původní místo, ale ve frustraci jsem tu nabídku odmítl. To byla velká chyba. Pak jsem zůstal vězet na Rutgers dalších 14 let, než přišla ta báječná nabídka z Concordie.
O jakou nabídku šlo?
V roce 2000 založila kanadská vláda 2000 profesorských pozic nazvaných Canada Research Chairs, které mají dva stupně. Ten vyšší, který jsem přijal v roce 2004, je udělován na sedm let a je obnovitelný na dalších sedm. Univerzita k němu dostává 200 000 dolarů ročně a díky tomu jsem mohl pozvat na Concordii řadu vynikajících spolupracovníků. Vedl jsem tam problémový seminář - mou v pořadí druhou variaci na Hedrlínovo téma - kterého se účastnili i lidi z dalších montrealských univerzit a skrze internet taky lidi ze Šanghaje.
„Všechny matematiky žene směs hledání Pravdy a Krásy s chutí křičet ‚Podívejte se na mě, já jsem chytřejší než vy!‘”
Podstatnou část kariéry jste se zabýval problémem obchodního cestujícího (Travelling Salesman Problem; TSP). Proč se tuto slavnou úlohu ještě nikomu nepodařilo vyřešit?
Zadání každého příkladu TSP začíná s konečnou množinou, jejímž prvkům říkáme „města“, a sestává z funkce, která přiřazuje každé dvojici měst cenu cesty mezi těmito dvěma městy. Úkolem je najít nejlevnější pořadí, ve kterém lze všechna města navštívit a pak se vrátit do toho výchozího. Protože těch možných pořadí je jenom konečně mnoho, řešení kteréhokoli takového příkladu je přímočaré. Zádrhel je ovšem v tom, že to přímočaré řešení může vyžadovat nesnesitelnou spoustu času. Neznáme žádný algoritmus, kterému by při zdvojnásobení počtu měst stačilo jen osmkrát víc času. Ani když to slovo „osmkrát“ nahradíme slovem „stokrát“ nebo dokonce „milionkrát“ a tak dál.
Svým studentům jste prý ten problém přibližoval na příkladu se žraloky.
Pro řešení příkladů TSP je klíčové oddělit daný bod v n-rozměrném prostoru od dané množiny bodů v tom prostoru nadrovinou. Na konferenci, která se konala u pláže v Brazílii, jsem případ n=2 ilustroval tím, že ten bod je nehybně číhající žralok a ta množina sestává z turistů v oceánu.
Se třemi dalšími kolegy jste v 90. letech vyvinul počítačový program, který určité úlohy z oblasti TSP dokáže řešit.
Program se jmenuje Concorde a vyřešil příklady, které do té doby nedokázal vyřešit nikdo jiný. Problém obchodního cestujícího zformuloval Karl Menger kolem roku 1930 a dlouhou dobu neměl nikdo ani potuchy, jak na něj. Pak přišel velký třesk. V roce 1954 George Dantzig, Ray Fulkerson a Selmer Johnson vymysleli takzvanou metodu řezů a tou vyřešili příklad 59 měst v USA, což bylo v té době ohromující. Všechno, co přišlo potom, jsou jen takové polevy na dortu, který upekli oni. Náš program Concorde patří mezi ně. Mimo jiné jsme našli nové způsoby oddělování „žraloka od turistů“. Discover Magazine zařadil naše řešení příkladu 3 038 měst na svůj seznam 50 vrcholů vědy v roce 1992. Poslední nejtěžší a největší příklad, který Concorde - za pomoci dalších lidí – vyřešil, měl 85 900 měst.
Jaké má problém obchodního cestujícího využití v reálném životě?
Relativně malé. Jeho hlavní význam je jako význam počítačových šachů - poskytuje arénu, kde v krvelačné soutěži výzkumníci vybrušují své matematické a počítačové techniky. Ty se pak mohou uplatnit v širších a užitečnějších souvislostech.
Je to soutěživost, co žene matematiky, aby se pouštěli do řešení dalších a složitějších problémů?
Myslím, že všechny matematiky žene směs hledání Pravdy a Krásy s chutí křičet „podívejte se na mě, já jsem chytřejší než vy!” a rozdíly jsou jen v podílech těch dvou složek. Mě motivovala na začátku romantická ctižádost. Moji soutěživost posilovala matematická olympiáda a Hedrlín se ji snažil ve mně vypěstovat až do nezdravých rozměrů. Naštěstí mě to přešlo a začala mě motivovat hlavně zvědavost, jak se věci mají, ať už na to přijdu já nebo někdo jiný.
Profesor Chvátal bude na Matfyzu v letním semestru vyučovat
předmět Discrete
Mathematics of Paul Erdős – NDMI107 (foto: Tomáš Princ)
V zahraničí jste spolupracoval s řadou vynikajících vědců, například s legendárním maďarským matematikem Pálem Erdősem. Čeho se vaše společná práce týkala?
Vydali jsme spolu tři články z teorie grafů a kombinatoriky. Výsledek toho prvního - A note on Hamiltonian circuits – je známý jako Chvátal-Erdős Theorem.
Co vás svedlo dohromady?
K tomu došlo ještě během mých studií. Hedrlín mi dojednal, že se Erdősovi představím při jeho návštěvě slovenské Akademie věd v Bratislavě na jaře 1966. To se stalo, a protože nějakým přehmatem neměl na Erdőse nikdo z akademie čas, dělal jsem mu po tři dny společnost já. Přidělili nám k tomu limuzínu s řidičem.
Jak jste ty tři dny strávili?
Každé ráno mě limuzína odvezla z mojí spartánské ubytovny do Erdősova přepychového hotelu. Na jeho terase mě čekala opulentní snídaně na účet akademie. Potom mi Erdős do večera s neobyčejnou trpělivostí vysvětloval matematické věty a jejich důkazy, zadával mi jednoduchá cvičení, předkládal těžší otevřené problémy a přitom taky toleroval mou lámanou angličtinu. V jednom z těch dnů jsme spolu vykonali pouť do Povážské Bystrice, kde se narodila Erdősova matka Anna.
Byl opravdu tak svérázný, jak se o něm traduje?
Byl. Ale ti, kteří se zaměřují na jeho výstřednost, jenom kloužou po povrchu a uniká jim jeho podstata. Tou byla jeho obrovská dobrota. Vyzařoval empatii a byl velkoryse štědrý jak s vlastními myšlenkami, tak s penězi. Kamarádská a uvolněná nálada v diskrétní matematice vděčí mnoho jeho osobnímu příkladu.
Jak probíhala vaše spolupráce?
Náš první společný článek vznikl během jízdy v autě. Já jsem mu řekl o svojí hypotéze z teorie grafů, on ji během následující 80minutové cesty dokázal, a já jsem pak ten důkaz sepsal. V případě druhého článku jsme šli ve dvou na večeři, u předkrmu jsem mu řekl svou hypotézu z teorie grafů, on během hlavního chodu dokázal její slabší verzi, a pak jsem ten důkaz sepsal. Oba případy dosvědčují, že byl v matematice výkonnější než já - což jsem ani nemusel podotknout - a že se mu líbily moje otázky. Z toho jsem měl a mám velikou radost. Náš třetí společný článek vznikal během několika dnů, kdy jsme si pinkali nápady tam a zpátky jako pingpongové míčky.
Od roku 2014 jste oficiálně v důchodu, ale hádám, že pracujete pořád…
Mezi lety 1965 a 2014 jsem vydal 130 článků a po roce 2014 čtyři. Teď věnuju matematice míň času a energie, a tak jich mám víc na divadla a kina.
Žijete opět v Praze a v loňském roce jste se stal hostujícím profesorem na UK. Berete to jako nové dobrodružství?
Moje žena a já pobaveně pozorujeme, jací jsme dobrodruzi. Markéta se vzdala místa vedoucí lékařky neurologické laboratoře na státní univerzitě v New Yorku, které jí vyhovovalo po všech stránkách, a pracuje teď na částečný úvazek na pražské poliklinice. Hodně času věnuje 11leté holčičce, kterou máme od srpna 2018 v pěstounské péči. I pro mě je nová emigrace novým dobrodružstvím. Zaujetí, se kterým objevuju další tváře Prahy, mi připomíná to, se kterým jsem před lety systematicky objevoval další tváře Tokia. Navíc teď budu také učit a moc se na to těším. Doufám, že studenty to bude bavit taky.
prof. Václav Chvátal, Ph.D. (* 1946)
Český matematik a emeritní profesor na Concordia University. V roce 1968,
krátce po dokončení studia na MFF UK, emigroval do Kanady. Doktorský titul
obhájil v roce 1970 na University of Waterloo. Působil v Kanadě a USA, vedle
zmíněné Concordie, kde byl deset let držitelem Canada Research
Chair, také na univerzitách McGill, Stanford University, Université de
Montréal nebo Rutgers. Řadí se k předním odborníkům na teorii grafů,
kombinatoriku a diskrétní optimalizaci (známý je např. Chvátalův graf
nebo jeho art gallery theorem). Je autorem nebo spoluautorem více než 130
článků v odborných časopisech a čtyř knižních publikací, mj. učebnice
Linear programming. Podílel se na vzniku počítačového programu
Concorde určeného k řešení problému obchodního cestujícího. Za svou
práci obdržel několik ocenění (Beale-Orchard-Hays Prize for Excellence in
Computational Mathematical Programming, Frederick W. Lanchester Prize, John von
Neumann Theory Prize). Vedle matematiky se věnoval také literární tvorbě.
Jeho povídku Déjà Vu z roku 1972 zařadila Martha Foleyová,
spoluzakladatelka a editorka časopisu Story, na svůj známý seznam
nejlepších amerických povídek roku. Je autorem několika písňových
textů, které zhudebnil Vlastimil Hála. Jeho rovnice 
se v chybné verzi objevila v knize Josefa Škvoreckého Hříchy pro pátera
Knoxe. Od roku 2015 žije se svou ženou v Praze.