Ва́цлав (Ва́шек) Хватал — почесний професор факультету комп'ютерних наук та програмної інженерії Університету Конкордія в Монреалі (Квебек, Канада). Він опублікував багато статей з теорії графів, комбінаторики та комбінаторної оптимізації.
Вацлав Хватал | |
---|---|
Народився | 20 липня 1946[1][2][3] (77 років) Прага, Чехословаччина[2][3] |
Країна | Канада Чехословаччина[3] |
Діяльність | математик, викладач університету, інформатик |
Alma mater | Університет Ватерлоо Карлів університет |
Галузь | комбінаторика[2], теорія графів[2] і комбінаторна оптимізація[2] |
Заклад | Університет Конкордія Монреальський університет |
Вчителі | d |
Аспіранти, докторанти | d d[5] d[5] d[5] d[5] d[5] d[5] d[5] d[5] d[5] d |
Нагороди | d (2007) |
Вацлав Хватал у Вікісховищі |
Життєпис
Хватал народився в Празі 1946 року й отримав математичну освіту в Карловому університеті в Празі, де навчався під керівництвом [en]. Він утік із Чехословаччини 1968 року, через три дні після радянського вторгнення, та захистив докторську дисертацію. Восени 1970 отримав ступінь магістра математики в Університеті Ватерлоо під керівництвом [en]. Згодом він обіймав посади в Університеті Макгілла (1971 та 1978—1986 роки), Стенфордському університеті (1972 та 1974—1977 роки), Монреальському університеті (1972—1974 і 1977—1978 роки) та Рутґерському університеті, перш ніж повернутися до Монреаля на [en] з комбінаторної оптимізації в Конкордії (2004—2011) та [en] з дискретної математики (2011—2014) до пенсії.
Дослідження
Хватал уперше дізнався про теорію графів 1964 року, коли знайшов у книгарні міста Пльзень книгу Клода Берже, і більша частина його досліджень пов'язана з теорією графів:
- Його перша математична публікація у віці 19 років стосувалася орієнтованих графів, які не можна відобразити на себе ніяким нетривіальним гомоморфізмом графів.
- Другим теоретико-графічним результатом Хватала була побудова 1970 року мінімально можливого графа без трикутників, який є як 4-хроматичним, так і 4-регулярним графом, тепер відомим як граф Хватала.
- У статті 1972 року, що зв'язує гамільтонові цикли зі зв'язністю та максимальним розміром незалежної множини графа, Хваталу присвоєно число Ердеша 1. Зокрема, якщо існує таке s, що даний граф є s-вершинно-зв'язним і не має (s + 1)-вершинно-незалежної множини, граф має бути гамільтоновим.
- У статті 1973 року Хватал увів поняття стійкості графа, міру зв'язності графа, тісно пов'язану з існуванням гамільтонових циклів. Граф є t-жорстким, якщо для кожного k більше 1 видалення менш ніж tk вершин залишає в підграфі, що залишився, менше k компонент зв'язності. Наприклад, у графі з гамільтоновим циклом видалення будь-якої непорожньої множини вершин розбиває цикл не більше ніж на стільки частин, скільки видалено вершин, тому гамільтонові графи 1-жорсткі. Хватал припустив, що 3/2-жорсткі графи, а пізніше і 2 — жорсткі графи, завжди гамільтонові; попри те, що пізніші дослідники знайшли контрприклади цим гіпотезам, залишається відкритим питання про те, чи достатньо певної сталої оцінки стійкості графа, щоб гарантувати гамільтоновість.
Деякі роботи Хватала стосуються сімейств множин або, що те саме, гіперграфів, зокрема тему згадано в його докторській дисертації, де він також розглядав теорію Рамсея.
Книги
- Vašek Chvátal (1983). Linear Programming. W.H. Freeman. .. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
- C. Berge and V. Chvátal (eds.) (1984). Topics on Perfect Graphs. Elsevier. .
- David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. .
- Vašek Chvátal (ed.) (2011). Combinatorial Optimization: Methods and Applications. IOS Press. .
- Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press. .
Примітки
- Deutsche Nationalbibliothek Record #110721772 // Gemeinsame Normdatei — 2012—2016.
- Czech National Authority Database
- Evidence zájmových osob StB
- Cook W., Avis D., Bondy J. A. et al. Vašek Chvátal: A Very Short Introduction // Graphs and Combinatorics — , 2007. — Vol. 23, Iss. S1. — P. 41–65. — ISSN 0911-0119; 1435-5914 — doi:10.1007/S00373-007-0721-4
- Математичний генеалогічний проєкт — 1997.
Посилання
- Домашня сторінка Хватала
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Va clav Va shek Hvatal pochesnij profesor fakultetu komp yuternih nauk ta programnoyi inzheneriyi Universitetu Konkordiya v Monreali Kvebek Kanada Vin opublikuvav bagato statej z teoriyi grafiv kombinatoriki ta kombinatornoyi optimizaciyi Vaclav HvatalNarodivsya20 lipnya 1946 1946 07 20 1 2 3 77 rokiv Praga Chehoslovachchina 2 3 Krayina Kanada Chehoslovachchina 3 Diyalnistmatematik vikladach universitetu informatikAlma materUniversitet Vaterloo Karliv universitetGaluzkombinatorika 2 teoriya grafiv 2 i kombinatorna optimizaciya 2 ZakladUniversitet Konkordiya Monrealskij universitetVchitelidAspiranti doktorantid d 5 d 5 d 5 d 5 d 5 d 5 d 5 d 5 d 5 dNagorodid 2007 Vaclav Hvatal u VikishovishiZhittyepisHvatal narodivsya v Prazi 1946 roku j otrimav matematichnu osvitu v Karlovomu universiteti v Prazi de navchavsya pid kerivnictvom en Vin utik iz Chehoslovachchini 1968 roku cherez tri dni pislya radyanskogo vtorgnennya ta zahistiv doktorsku disertaciyu Voseni 1970 otrimav stupin magistra matematiki v Universiteti Vaterloo pid kerivnictvom en Zgodom vin obijmav posadi v Universiteti Makgilla 1971 ta 1978 1986 roki Stenfordskomu universiteti 1972 ta 1974 1977 roki Monrealskomu universiteti 1972 1974 i 1977 1978 roki ta Rutgerskomu universiteti persh nizh povernutisya do Monrealya na en z kombinatornoyi optimizaciyi v Konkordiyi 2004 2011 ta en z diskretnoyi matematiki 2011 2014 do pensiyi DoslidzhennyaHvatal upershe diznavsya pro teoriyu grafiv 1964 roku koli znajshov u knigarni mista Plzen knigu Kloda Berzhe i bilsha chastina jogo doslidzhen pov yazana z teoriyeyu grafiv Jogo persha matematichna publikaciya u vici 19 rokiv stosuvalasya oriyentovanih grafiv yaki ne mozhna vidobraziti na sebe niyakim netrivialnim gomomorfizmom grafiv Drugim teoretiko grafichnim rezultatom Hvatala bula pobudova 1970 roku minimalno mozhlivogo grafa bez trikutnikiv yakij ye yak 4 hromatichnim tak i 4 regulyarnim grafom teper vidomim yak graf Hvatala U statti 1972 roku sho zv yazuye gamiltonovi cikli zi zv yaznistyu ta maksimalnim rozmirom nezalezhnoyi mnozhini grafa Hvatalu prisvoyeno chislo Erdesha 1 Zokrema yaksho isnuye take s sho danij graf ye s vershinno zv yaznim i ne maye s 1 vershinno nezalezhnoyi mnozhini graf maye buti gamiltonovim U statti 1973 roku Hvatal uviv ponyattya stijkosti grafa miru zv yaznosti grafa tisno pov yazanu z isnuvannyam gamiltonovih cikliv Graf ye t zhorstkim yaksho dlya kozhnogo k bilshe 1 vidalennya mensh nizh tk vershin zalishaye v pidgrafi sho zalishivsya menshe k komponent zv yaznosti Napriklad u grafi z gamiltonovim ciklom vidalennya bud yakoyi neporozhnoyi mnozhini vershin rozbivaye cikl ne bilshe nizh na stilki chastin skilki vidaleno vershin tomu gamiltonovi grafi 1 zhorstki Hvatal pripustiv sho 3 2 zhorstki grafi a piznishe i 2 zhorstki grafi zavzhdi gamiltonovi popri te sho piznishi doslidniki znajshli kontrprikladi cim gipotezam zalishayetsya vidkritim pitannya pro te chi dostatno pevnoyi staloyi ocinki stijkosti grafa shob garantuvati gamiltonovist Deyaki roboti Hvatala stosuyutsya simejstv mnozhin abo sho te same gipergrafiv zokrema temu zgadano v jogo doktorskij disertaciyi de vin takozh rozglyadav teoriyu Ramseya KnigiVasek Chvatal 1983 Linear Programming W H Freeman ISBN 978 0 7167 1587 0 Japanese translation published by Keigaku Shuppan Tokyo 1986 C Berge and V Chvatal eds 1984 Topics on Perfect Graphs Elsevier ISBN 978 0 444 86587 8 David L Applegate Robert E Bixby Vasek Chvatal William J Cook 2007 The Traveling Salesman Problem A Computational Study Princeton University Press ISBN 978 0 691 12993 8 Vasek Chvatal ed 2011 Combinatorial Optimization Methods and Applications IOS Press ISBN 978 1 60750 717 8 Vasek Chvatal 2021 Discrete Mathematical Charms of Paul Erdos A Simple Introduction Cambridge University Press ISBN 978 1 108 92740 6 PrimitkiDeutsche Nationalbibliothek Record 110721772 Gemeinsame Normdatei 2012 2016 d Track Q27302d Track Q36578 Czech National Authority Database d Track Q13550863 Evidence zajmovych osob StB d Track Q104900509 Cook W Avis D Bondy J A et al Vasek Chvatal A Very Short Introduction Graphs and Combinatorics Springer Science Business Media 2007 Vol 23 Iss S1 P 41 65 ISSN 0911 0119 1435 5914 doi 10 1007 S00373 007 0721 4 d Track Q15284723d Track Q4978188d Track Q3180867d Track Q176916d Track Q3709153d Track Q2578302d Track Q59699134 Matematichnij genealogichnij proyekt 1997 d Track Q829984PosilannyaDomashnya storinka Hvatala