Václav Chvátal

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Václav Chvátal
Narození 20. července 1946 (70 let)
Praha
Alma mater Univerzita ve Waterloo
Zaměstnavatel Concordia University
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]




  1. a b c d  "Vasek Chvatal: A Short Introduction"(2007). Graphs and Combinatorics 23: 41–66. doi:10.1007/s00373-007-0721-4. 
  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
  6. Chvátal, Vašek(1997),"In praise of Claude Berge",Discrete Mathematics165-166: 3–9, http://www.sciencedirect.com/science/journal/0012365X/165-166 ,
  7. Chvátal, Václav(1965),"On finite and countable rigid graphs and tournaments",Commentationes Mathematicae Universitatis Carolinae6: 429–438, http://dml.cz/dmlcz/105034 .
  8. Václav Chvátal v encyklopedii MathWorld (anglicky)
  9. V. Chvátal; P. Erdős(1972),"A note on Hamiltonian circuits",Discrete Mathematics2: 111–113, http://www.math-inst.hu/~p_erdos/1972-02.pdf ,
  10. Chvátal, V.(1973),"[httĔp://www.sciencedirect.com/science/article/pii/S0012365X06001397 Tough graphs and hamiltonian circuits]",Discrete Mathematics5: 215–228, httĔp://www.sciencedirect.com/science/article/pii/S0012365X06001397 ,
  11. Lesniak, Linda,, http://faculty.nps.edu/rgera/Conjectures/jmm2012/Linda-Lesniak.pdf 
  12. Mathematical Reviews MR0369170
  13. V. Chvátal; Dř.A. Klarner; D.E. Knuth(1972),"Selected combinatorial research problems",Computer Science Department, Stanford UniversityStan-CS-TR-72-292, http://users.encs.concordia.ca/~chvatal/Stan-CS-TR-72-292.pdf : Problem 25
  14. Chvátal, Vašek,, http://users.encs.concordia.ca/~chvatal/conjecture.html 
  15. "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
  16. Chvátal, Václav(1973),"Edmonds polytopes and weakly hamiltonian graphs",Mathematical Programming5: 29–40, https://link.springer.com/article/10.1007%2FBF01580109 ,
  17. Chvátal, Václav(1973),"Edmonds polytopes and a hierarchy of combinatorial problems",Discrete Mathematics4: 305–337, http://dx.doi.org/10.1016/j.disc.2006.03.009 ,
  18. Chvátal, Václav(1975),"Some linear programming aspects of combinatorics",Congressus Numerantium13: 2–30, http://i.stanford.edu/pub/cstr/reports/cs/tr/75/505/CS-TR-75-505.pdf ,
  19. Chvátal, V.(1975),"On certain polytopes associated with graphs",Journal of Combinatorial Theory, Series B18: 138–154, http://www.sciencedirect.com/science/article/pii/0095895675900416 .
  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(1998),"On the Solution of Traveling Salesman Problems",DOCUMENTA MATHEMATICAExtra Volume ICM III, https://www.math.uni-bielefeld.de/documenta/xvol-icm/17/Cook.MAN.html 
  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(1993),"Notes on the Kolakoski Sequence",DIMACS Technical ReportsTR: 93-84, http://dimacs.rutgers.edu/TechnicalReports/abstracts/1993/93-84.html 
  28. Dangerous Problems, Science News Online, Jul. 13, 2002.
  29. Chvátal, Václav; Sankoff, David(1975),"Longest common subsequences of two random sequences",Journal of Applied Probability12: 306–315 ,
  30. Chvátal, Vašek; Szemerédi, Endre(1988),"Many hard examples for resolution",Journal of the ACM35: 759–768 .