Václav Chvátal

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Václav Chvátal
Chvatal-kyoto2007-costume-head.png
Narození 20. července 1946 (73 let)
Praha
Alma mater Univerzita ve Waterloo
Univerzita Karlova
Zaměstnavatelé Concordia University
Université de Montréal
Ocenění Frederick W. Lanchester Prize (2007)
Některá data mohou pocházet z datové položky.

Václav Chvátal (* 20. července 1946) je emeritním profesorem na univerzitě Concordia v Montrealu v Kanadě. Mezi hlavní obory jeho vědecké činnosti patří teorie grafů, kombinatorika, a kombinatorická optimalizace.

Chvátalův graf

Život[editovat | editovat zdroj]

Narodil se v Praze v roce 1946 a matematické vzdělání získal na Karlově univerzitě, kde studoval pod vedením Zdeňka Hedrlína.[1]. Tři dny po invazi sovětských vojsk v roce 1968 emigroval do Kanady. Na podzim 1970 dokončil doktorské studium (titul Ph.D.) na University of Waterloo.[2]. Působil na univerzitách McGill (1971 a 1978-1986), Stanford (1972 a 1974-1977), Université de Montréal (1972-1974 and 1977-1978), a Rutgers (1986-2004) před návratem do Montrealu, kde se stal na univerzitě Concordia držitelem křesla Canada Research Chair in Combinatorial Optimization[3][4] na období 2004-2011. To mu pak Natural Sciences and Engineering Research Council of Canada obnovil na dalších sedm let jako Canada Research Chair in Discrete Mathematics, ale Chvátal se ho vzdal v roce 2014, kdy odešel z osobních důvodů do důchodu.

V roce 2003 mu Université de la Méditerranné udělila čestný doktorát a v roce 2015 mu Institute for Operations Research and the Management Sciences udělil John von Neumann Theory Prize.[5]

Výzkum[editovat | editovat zdroj]

Chvátal objevil teorii grafů v plzeňském obchodě Сoвeтская Kнигa v roce 1964 [6] a velká část jeho práce se týká grafů:

  • V článku z roku 1973 [10] zavedl Chvátal pojem tuhosti grafu (graph toughness), který se váže k existenci hamiltonovských kružnic. Graf je t-tuhý když, pro každé k větší než 1, odstranění ménĕ než tk uzlů zanechá ve zbývajícím podgrafu ménĕ než k souvislých komponent. Například, v hamiltonovském grafu odstranění jakékoli neprázdné množiny uzlů rozbije ten graf na nejvýš tolik kusů, kolik bylo odstraněných uzlů, a tak jsou hamiltonovské grafy 1-tuhé. Chvátal vyslovil domněnku, že 3/2-tuhé grafy, a později že 2-tuhé grafy, jsou vždycky hamiltonovské; na tyto domněnky jsou protipříklady, ale není známo, jestli nějaká konstantní dolní mez na tuhost zaručuje, že graf je hamiltonovský.[11]

Některé z Chvátalových prací se týkají systémů množin neboli hypergrafů:

  • V hypotéze z roku 1972, kterou Erdős nazval "překvapivou" a "krásnou",[12] a která zůstává otevřena (Chvátal za její řešení nabídnul $10) [13][14] naznačil, že v každém systému množin uzavřenému pod operací tvorby podmnožin, největší podsystém vzájemně se protínajících se množin může vždy být vytvořen volbou jednoho bodu a následujícím výbĕrem všech množin, které tento bod obsahují.
  • V roce 1979 zobecnil předcházející výsledky Davida Johnsona (J. Comp. Sys. Sci. 1974) and László Lovásze (Discrete Math. 1975) týkající se aproximačního algoritmu pro problém set cover.[15]

Pod vlivem Jacka Edmondse ve Waterloo se začal Chvátal zajímat o lineární programování.[1] Brzy si uvědomil důležitost sečných nadrovin pro problémy kombinatorické optimalizace jako je hledání největší nezávislé množiny a zavedl pojem cutting-plane proof.[16][17][18][19] Na Stanfordu v sedmdesátých letech začal psát svou populární učebnici, Linear Programming, vydanou v roce 1983.[1]

Sečných nadrovin užívá také metoda branch and cut v počítačových programech k řešení problému obchodního cestujícího. Mezi lety 1988 and 2005, David Applegate, Robert Bixby, Vašek Chvátal, a William Cook napsali jeden takový program, Concorde.[20][21] V roce 2000 dostal jejich kolektiv cenu The Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming za desetistránkový článek[22] popisující několik zdokonalení metody branch and cut která vedla Concorde k řešení případu s 13.509 městy a v roce 2007 dostal tento kolektiv cenu Frederick W. Lanchester Prize za knihu The Traveling Salesman Problem: A Computational Study.

Chvátal je také znám

Knihy[editovat | editovat zdroj]

  • Vašek Chvátal. Linear Programming. [s.l.]: W.H. Freeman, 1983. ISBN 978-0-7167-1587-0. (anglicky) . Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
  • C. Berge and V. Chvátal (eds.). Topics on Perfect Graphs. [s.l.]: Elsevier, 1984. ISBN 978-0-444-86587-8. (anglicky) 
  • David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook. The Traveling Salesman Problem: A Computational Study. [s.l.]: Princeton University Press, 2007. Dostupné online. ISBN 978-0-691-12993-8. (anglicky) 
  • Vašek Chvátal (ed.). Combinatorial Optimization: Methods and Applications. [s.l.]: IOS Press, 2011. Dostupné online. ISBN 978-1-60750-717-8. (anglicky) 

Reference[editovat | editovat zdroj]

  1. a b c d AVIS, D.; BONDY, A.; COOK, W.; REED, B. Vasek Chvatal: A Short Introduction. Graphs and Combinatorics. 2007, s. 41–66. Dostupné online. DOI:10.1007/s00373-007-0721-4. (anglicky) 
  2. The Mathematics Genealogy Project – Václav Chvátal
  3. Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
  4. Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
  5. John von Neumann Theory Prize 2015. www.informs.org [online]. [cit. 2017-03-22]. Dostupné v archivu pořízeném dne 2016-08-20. 
  6. CHVÁTAL, Vašek. In praise of Claude Berge. Discrete Mathematics. 1997, s. 3–9. Dostupné online. DOI:10.1016/s0012-365x(96)00156-2. (anglicky) ,
  7. CHVÁTAL, Václav. On finite and countable rigid graphs and tournaments. Commentationes Mathematicae Universitatis Carolinae. 1965, s. 429–438. Dostupné online. (anglicky) .
  8. Václav Chvátal v encyklopedii MathWorld (anglicky)
  9. V. CHVÁTAL; P. ERDŐS. A note on Hamiltonian circuits. Discrete Mathematics. 1972, s. 111–113. Dostupné v archivu pořízeném z originálu dne 2017-07-06. (anglicky) ,
  10. CHVÁTAL, V. Tough graphs and hamiltonian circuits. Discrete Mathematics. 1973, s. 215–228. [httĔp://www.sciencedirect.com/science/article/pii/S0012365X06001397 Dostupné online]. (anglicky) ,
  11. LESNIAK, Linda. Chvátal's t0-tough conjecture. [s.l.]: [s.n.] Dostupné online. (anglicky) 
  12. Mathematical Reviews MR0369170
  13. V. CHVÁTAL; DŘ.A. KLARNER; D.E. KNUTH. Selected combinatorial research problems. Computer Science Department, Stanford University. 1972. Dostupné online. (anglicky) : Problem 25
  14. CHVÁTAL, Vašek. A conjecture in extremal combinatorics. [s.l.]: [s.n.] Dostupné online. (anglicky) 
  15. "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
  16. CHVÁTAL, Václav. Edmonds polytopes and weakly hamiltonian graphs. Mathematical Programming. 1973, s. 29–40. Dostupné online. DOI:10.1007/BF01580109. (anglicky) ,
  17. CHVÁTAL, Václav. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics. 1973, s. 305–337. Dostupné online. (anglicky) ,
  18. CHVÁTAL, Václav. Some linear programming aspects of combinatorics. Congressus Numerantium. 1975, s. 2–30. Dostupné online. (anglicky) ,
  19. CHVÁTAL, V. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B. 1975, s. 138–154. Dostupné online. (anglicky) .
  20. Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991.
  21. Artful Routes, Science News Online, Jan. 1, 2005.
  22. APPLEGATE, David; BIXBY, Robert; CHVÁTAL, Vašek; COOK, William. On the Solution of Traveling Salesman Problems. DOCUMENTA MATHEMATICA. 1998. Dostupné online. (anglicky) 
  23. Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  24. Diagonals: Part I 4. Art gallery problems, AMS Feature Column by Joseph Malkevitch
  25. Chvatal's Art Gallery Theorem in Alexander Bogomolny's Cut the Knot
  26. Obsession, Numb3rs, Episode 3, Season 2
  27. CHVÁTAL, Vašek. Notes on the Kolakoski Sequence. DIMACS Technical Reports. 1993. Dostupné online. (anglicky) 
  28. Dangerous Problems, Science News Online, Jul. 13, 2002.
  29. CHVÁTAL, Václav; SANKOFF, David. Longest common subsequences of two random sequences. Journal of Applied Probability. 1975, s. 306–315. DOI:10.2307/3212444. (anglicky) ,
  30. CHVÁTAL, Vašek; SZEMERÉDI, Endre. Many hard examples for resolution. Journal of the ACM. 1988, s. 759–768. DOI:10.1145/48014.48016. (anglicky) .