Хватал впервые узнал о теории графов в 1964 году, когда нашел книгу Клода Берже в книжном магазине города Пльзень [8], и большая часть его исследований посвящена теории графов:
Его первая математическая публикация, сделанная в возрасте 19 лет, касалась ориентированных графов , которые не могут быть отображены в себя никаким нетривиальным гомоморфизмом графов [9]
Статья 1972 года [11], связывающая гамильтоновы циклы со связностью и максимальным размером независимого множества графа, принесла Хваталу его число Эрдёша, равное 1. В частности, если существует s такое, что заданный граф является s - вершинно связным и не имеет ( s + 1)-вершинно независимого множества, граф должен быть гамильтоновым. Авис и др. [4] рассказывают историю о том, как Хватал и Эрдёш работали над этим результатом в ходе долгой поездки, а позже поблагодарили Луизу Гай «за ее спокойное вождение».
В статье 1973 года [12] Хватал ввел понятие графовой жесткости , меры связности графа , которая тесно связана с существованием гамильтоновых циклов . Граф является t -жестким, если для каждого k, большего 1, удаление менее tk вершин оставляет менее k связных компонентов в оставшемся подграфе. Например, в графе с гамильтоновым циклом удаление любого непустого множества вершин разбивает цикл на не более чем столько частей, сколько удалено вершин, поэтому гамильтоновы графы являются 1-жесткими. Хватал предположил, что 3/2-жесткие графы, а позже и 2-жесткие графы всегда являются гамильтоновыми; несмотря на то, что более поздние исследователи нашли контрпримеры к этим гипотезам, все еще остается открытым вопрос, достаточно ли некоторой постоянной границы для графовой жесткости, чтобы гарантировать гамильтоновость. [13]
Некоторые из работ Хватала касаются семейств множеств, или, что то же самое, гиперграфов , — темы, которая уже затрагивалась в его докторской диссертации, где он также изучал теорию Рамсея .
В гипотезе 1972 года, которую Эрдёш назвал «удивительной» и «красивой» [14] и которая остаётся открытой (за её решение Хватал назначил премию в 10 долларов) [15] [16], он предположил, что в любом семействе множеств, замкнутом относительно операции взятия подмножеств , наибольшее попарно пересекающееся подсемейство всегда можно найти, выбрав элемент одного из множеств и сохранив все множества, содержащие этот элемент.
Хватал впервые заинтересовался линейным программированием под влиянием Джека Эдмондса , когда он был студентом в Ватерлоо. [4] Он быстро осознал важность секущих плоскостей для решения задач комбинаторной оптимизации, таких как вычисление максимальных независимых множеств , и, в частности, ввел понятие доказательства секущей плоскостью. [18] [19] [20] [21] В Стэнфорде в 1970-х годах он начал писать свой популярный учебник « Линейное программирование », который был опубликован в 1983 году. [4]
Секущие плоскости лежат в основе метода ветвей и отсечений , используемого эффективными решателями задачи коммивояжера . В период с 1988 по 2005 год команда Дэвида Л. Эпплгейта , Роберта Э. Биксби , Вашека Хватала и Уильяма Дж. Кука разработала один такой решатель, Concorde . [22] [23] В 2000 году команда была награждена премией Била-Орчарда-Хэйса за выдающиеся достижения в вычислительном математическом программировании за десятистраничную работу [24], в которой перечислены некоторые усовершенствования метода ветвей и отсечений, предложенные Concorde, которые привели к решению задачи с 13 509 городами, а в 2007 году она была награждена премией Фредерика У. Ланчестера за книгу « Задача коммивояжера: вычислительное исследование» .
Дэвид Л. Эпплгейт; Роберт Э. Биксби; Вашек Хватал; Уильям Дж. Кук (2007). Задача коммивояжера: вычислительное исследование. Издательство Принстонского университета. ISBN 978-0-691-12993-8.[33]
Vašek Chvátal, ред. (2011). Комбинаторная оптимизация: методы и приложения. IOS Press. ISBN 978-1-60750-717-8.
Вашек Хватал (2021). Дискретные математические чары Пауля Эрдёша. Простое введение. Издательство Кембриджского университета. ISBN 978-1-108-92740-6.
↑ Премия Фредерика У. Ланчестера 2007 г., получено 19 марта 2017 г.
↑ Премия Джона фон Неймана по теории 2015 г., получено 19 марта 2017 г.
^ abcdef Avis, D. ; Bondy, A.; Cook, W. ; Reed, B. (2007). "Vasek Chvatal: A Short Introduction" (PDF) . Графы и комбинаторика . 23 : 41–66. CiteSeerX 10.1.1.127.5910 . doi :10.1007/s00373-007-0721-4. S2CID 11121944.
^ Вашек Хватал — «путешествующий профессор», репортаж Concordia за четверг, 10 февраля 2005 г.
^ Проект математической генеалогии - Вацлав Хватал
↑ Вашек Хватал награжден премией за должность председателя Канадского научного совета, отчет Concordia за четверг, 23 октября 2003 г.
^ Хватал, Вашек (1997), «Похвала Клоду Берже», Дискретная математика , 165–166: 3–9, doi : 10.1016/s0012-365x(96)00156-2,
^ Хватал, Вацлав (1965), «О конечных и счетных жестких графах и турнирах», Commentationes Mathematicae Universitatis Carolinae , 6 : 429–438.
^ В. Хватал; Дэвид А. Кларнер ; DE Кнут (1972), «Избранные задачи комбинаторного исследования» (PDF) , факультет компьютерных наук, Стэнфордский университет , Stan-CS-TR-72-292: Задача 25
^ Хватал, Вашек, Гипотеза в экстремальной комбинаторике
^ «Жадная эвристика для задачи покрытия множеств», Математика исследования операций, 1979
^ Chvátal, Václav (1973), «Многогранники Эдмондса и слабо гамильтоновы графы», Математическое программирование , 5 : 29–40, doi :10.1007/BF01580109, S2CID 8140217,
^ Chvátal, Václav (1973), «Многогранники Эдмондса и иерархия комбинаторных задач», Discrete Mathematics , 4 (4): 305–337, doi : 10.1016/0012-365x(73)90167-2,
^ Chvátal, Václav (1975), «Некоторые аспекты линейного программирования в комбинаторике» (PDF) , Congressus Numerantium , 13 : 2–30,
^ Chvátal, V. (1975), «О некоторых многогранниках, связанных с графами», Журнал комбинаторной теории, Серия B , 18 (2): 138–154, doi : 10.1016/0095-8956(75)90041-6.
↑ Математическая задача, долго озадачивала, медленно поддавалась решению. New York Times , 12 марта 1991 г.
↑ Artful Routes, Science News Online, 1 января 2005 г.
^ Эпплгейт, Дэвид; Биксби, Роберт; Хватал, Вашек; Кук, Уильям (1998), «О решении задач коммивояжера», Documenta Mathematica , Дополнительный том ICM III
^ Weisstein, Eric W. «Теорема о художественной галерее». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/ArtGalleryTheorem.html
^ Диагонали: Часть I 4. Проблемы художественной галереи, AMS Feature Column Джозефа Малкевича
^ Теорема о художественной галерее Хватала в произведении Александра Богомольного «Разруби узел»
