Вацлав Хватал

Вацлав Хватал (чеш. Václav Chvátal; род. 20 июля 1946, Прага) — чешско-канадский математик, специализирующийся в области теории графов, комбинаторики и теории сложности вычислений. Известен фундаментальными результатами в теории графов, в частности теоремой Хватала, а также вкладом в теорию целочисленного программирования и алгоритмов.

Биография

Вацлав Хватал родился в Праге, Чехословакия. В 1964 году поступил в Карлов университет в Праге, где изучал математику. В 1968 году, после вторжения войск Варшавского договора в Чехословакию, эмигрировал в Канаду. Продолжил обучение в Университете Ватерлоо, где в 1970 году получил степень магистра, а в 1972 году — доктора философии (PhD) под руководством Клода Бержа. Диссертация была посвящена гиперграфам и теории графов.

После защиты Хватал работал в Университете Макгилла (Монреаль), Университете Монреаля, Университете Нью-Брансуика (Фредериктон), а затем в Университете Конкордия (Монреаль) и Университете Ратгерса (Нью-Джерси, США). С 2004 года является профессором кафедры информатики и программной инженерии в Университете Конкордия. В 2014 году вышел на пенсию, но продолжает научную деятельность.

Научные достижения

Теория графов

Хватал является одним из ведущих специалистов в теории графов. Его работы охватывают широкий круг тем, включая раскраску графов, гамильтоновы циклы, совершенные графы и хроматические числа.

• Теорема Хватала (1972): устанавливает достаточное условие для существования гамильтонова цикла в графе. Формулируется так: если для графа \( G \) с \( n \) вершинами (\( n \ge 3 \)) последовательность степеней вершин \( d_1 \le d_2 \le \dots \le d_n \) удовлетворяет условию: для любого \( k < n/2 \) выполняется \( d_k > k \) или \( d_{n-k} \ge n-k \), то граф является гамильтоновым. Эта теорема обобщает более ранние результаты Дирака и Оре.

• Гипотеза Хватала (1973): о том, что любой граф с минимальной степенью не менее 3 содержит цикл длины, равной степени вершины. Гипотеза остаётся открытой, хотя частичные результаты получены.

• Хваталовы графы: класс графов, введённых Хваталом, которые являются минимальными негамильтоновыми графами с заданными свойствами. Пример — граф Хватала (12-вершинный граф, не имеющий гамильтонова цикла, но удовлетворяющий условию Оре).

• Совершенные графы: Хватал внёс вклад в теорию совершенных графов, в частности в доказательство теоремы о сильных совершенных графах (совместно с другими авторами).

Комбинаторика и целочисленное программирование

Хватал является соавтором фундаментальных работ по теории целочисленного программирования. Вместе с Харви Гринбергом он разработал метод отсекающих плоскостей Хватала — Гринберга, который используется для решения задач целочисленного линейного программирования. Этот метод позволяет последовательно добавлять линейные неравенства, отсекающие нецелочисленные решения, до получения целочисленного оптимума.

Теория сложности вычислений

В области теории сложности Хватал известен работами по NP-полноте и алгоритмам. Он исследовал сложность задач коммивояжёра, раскраски графов и других классических задач. Его книга «Линейное программирование» (1983) стала стандартным учебником по этой теме.

Основные труды

• «Линейное программирование» (1983) — учебник по линейному и целочисленному программированию, переведённый на несколько языков.
• «Теория графов» (совместно с Клодом Бержем, 1976) — монография по теории графов.
• «Комбинаторная оптимизация» (совместно с Уильямом Куком, 1997) — учебник по комбинаторной оптимизации.
• Многочисленные статьи в ведущих математических журналах, включая Journal of Combinatorial Theory, Discrete Mathematics, Mathematics of Operations Research.

Признание и награды

• Член Королевского общества Канады (1984).
• Лауреат премии Гёделя (1992) за вклад в теорию сложности и целочисленное программирование.
• Премия Фулкерсона (1993) за работы по комбинаторной оптимизации.
• Почётный доктор ряда университетов, включая Университет Ватерлоо и Карлов университет.

Интересные факты

• Хватал является автором термина «граф Хватала», который используется в учебниках по теории графов как пример негамильтонова графа.
• В 2012 году он опубликовал мемуары «Математика и жизнь», где описал свой путь от эмигранта до ведущего математика.
• Хватал активно занимается популяризацией математики, выступая с лекциями для школьников и студентов.

Источники

• Chvátal, V. «Linear Programming». W. H. Freeman, 1983.
• Chvátal, V. «Tough graphs and Hamiltonian circuits». Discrete Mathematics, 1973.
• Chvátal, V. «On Hamilton’s ideals». Journal of Combinatorial Theory, 1972.
• Chvátal, V. «The traveling salesman problem: a guided tour of combinatorial optimization». Wiley, 1985.
• Биография на сайте Университета Конкордия.
• Статья в «Математическом энциклопедическом словаре».