Ва́цлав (Ва́шек) Хватал — почесний професор факультету комп'ютерних наук та програмної інженерії Університету Конкордія в Монреалі (Квебек, Канада). Він опублікував багато статей з теорії графів, комбінаторики та комбінаторної оптимізації.
Життєпис
Хватал народився в Празі 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.
Примітки
Посилання
.svg){kind=small}
