Вацлав (Вашек) Хваталь — почетный профессор факультета компьютерных наук и программной инженерии Университета Конкордия в Монреале , Квебек , Канада . Он опубликовал множество статей по теории графов, комбинаторике и комбинаторной оптимизации.

Биография

Хватал родился в Праге в 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 .

Примечания

Ссылки