Хватал, Вацлав
| Вацлав Хватал | |
|---|---|
| чеш. Václav Chvátal | |
 | |
| Дата рождения | 20 июля 1946[1][2] (78 лет) |
| Место рождения | |
| Страна | |
| Род деятельности | математик, преподаватель университета, специалист в области информатики |
| Научная сфера | комбинаторика[1], теория графов[1] и комбинаторная оптимизация[1] |
| Место работы | |
| Альма-матер | |
| Научный руководитель | Crispin Nash-Williams[вд] |
| Награды и премии | |
 Медиафайлы на Викискладе | |
Вацлав (Вашек) Хваталь — почетный профессор факультета компьютерных наук и программной инженерии Университета Конкордия в Монреале, Квебек, Канада. Он опубликовал множество статей по теории графов, комбинаторике и комбинаторной оптимизации.
Биография
[править | править код]Хватал родился в Праге в 1946 году и получил математическое образование в Карловом университете в Праге, где он учился под руководством Зденека Хедрлина. Он бежал из Чехословакии в 1968 году, через три дня после советского вторжения, и защитил докторскую диссертацию. Осенью 1970 года получил степень магистра математики в Университете Ватерлоо под руководством Криспина Сент-Дж. А. Нэш-Уильямса. Впоследствии он занимал должности в Университете Макгилла (1971 и 1978-1986 гг.), Стэнфордском университете (1972 и 1974-1977 гг.)), Монреальского университета (1972-1974 гг. и 1977-1978 гг.) и Университета Рутгерса (1986-2004 гг.), прежде чем вернуться в Монреаль на кафедру канадских исследований комбинаторной оптимизации в Конкордии (2004-2011 гг.) и Канадскую кафедру дискретных исследований математики (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.
