Вацлав Хватал
Ва́цлав (Ва́шек) Хватал — почесний професор факультету комп'ютерних наук та програмної інженерії Університету Конкордія в Монреалі (Квебек, Канада). Він опублікував багато статей з теорії графів, комбінаторики та комбінаторної оптимізації.
| Вацлав Хватал | |
|---|---|
 | |
| Народився |
20 липня 1946[1][2][3] (77 років) Прага, Чехословаччина[2][3] |
| Країна |
.svg){kind=small} Канада Чехословаччина[3] |
| Діяльність | математик, викладач університету, інформатик |
| Alma mater |
Університет Ватерлоо Карлів університет |
| Галузь | комбінаторика[2], теорія графів[2] і Комбінаторна оптимізація[2] |
| Заклад |
Університет Конкордія Монреальський університет |
| Вчителі | Zdeněk Hedrlínd[4] |
| Аспіранти, докторанти |
Давид Авісd Брюс Рідd[5] Liping Sund[5] Hui-Yu Wangd[5] Ming Ouyangd[5] Glenn Rhoadsd[5] Ryan Bruce Haywardd[5] Hang-Tong Laud[5] Wenan Zangd[5] Mark Goldsmithd[5] Stephan Olariud |
| Нагороди | |
 Вацлав Хватал у Вікісховищі | |
Життєпис ред.
Хватал народився в Празі 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. ISBN 978-0-7167-1587-0.. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
- C. Berge and V. Chvátal (eds.) (1984). Topics on Perfect Graphs. Elsevier. ISBN 978-0-444-86587-8.
- David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8.
- Vašek Chvátal (ed.) (2011). Combinatorial Optimization: Methods and Applications. IOS Press. ISBN 978-1-60750-717-8.
- Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press. ISBN 978-1-108-92740-6.
Примітки ред.
- ↑ 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 — Springer Science+Business Media, 2007. — Vol. 23, Iss. S1. — P. 41–65. — ISSN 0911-0119; 1435-5914 — doi:10.1007/S00373-007-0721-4
- ↑ а б в г д е ж и к Математичний генеалогічний проєкт — 1997.