Вацлав Хватал
Чешско-канадский математик
Вацлав Хватал
Вацлав Хватал (2020)
Рожденный( 1946-07-20 )20 июля 1946 г. (78 лет)
Прага
НациональностьКанадский , чешский
Альма-матерУниверситет Ватерлоо,
Чарльз университет
ИзвестныйГраф Хватала
Константы Хватала–Санкова
Теорема Бонди–Хваталя
Неравенство числа пересечений
Прочность графа
НаградыПремия Била-Орчарда-Хейса (2000 г.) [1]
Почетный доктор, Средиземноморский университет (2003 г.)
Премия Фредерика В. Ланчестера (2007 г.) [2]
Премия Джона фон Неймана по теории (2015 г.) [3]
Научная карьера
ПоляМатематика , Информатика , Исследование операций
УчрежденияУниверситет Конкордия
научный руководительКриспин Нэш-Уильямс
ДокторантыДэвид Эвис (Стэнфорд, 1977)
Брюс Рид (Макгилл, 1986)

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

Биография

Хватал родился в 1946 году в Праге и получил математическое образование в Карловом университете в Праге, где он учился под руководством Зденека Хедрлина . [4] Он бежал из Чехословакии в 1968 году, через три дня после советского вторжения , [5] и защитил докторскую диссертацию. по математике в Университете Ватерлоо под руководством Криспина Сент-Джей Эйч-Эй Нэш-Уильямса осенью 1970 года. [4] [6] Впоследствии он занимал должности в Университете Макгилла (1971 и 1978–1986), Стэнфордском университете (1972 и 1974–1977), Университете Монреаля (1972–1974 и 1977–1978) и Университете Ратгерса (1986–2004), прежде чем вернуться в Монреаль на Канадскую исследовательскую кафедру комбинаторной оптимизации [7] [5] в Конкордии (2004–2011) и Канадскую исследовательскую кафедру дискретной математики (2011–2014) до выхода на пенсию.

Исследовать

Граф Хватала

Хватал впервые узнал о теории графов в 1964 году, когда нашел книгу Клода Берже в книжном магазине города Пльзень [8], и большая часть его исследований посвящена теории графов:

  • Его первая математическая публикация, сделанная в возрасте 19 лет, касалась ориентированных графов , которые не могут быть отображены в себя никаким нетривиальным гомоморфизмом графов [9]
  • Другим результатом теории графов Хватала было построение в 1970 году наименьшего возможного графа без треугольников , который является как 4- хроматическим , так и 4- регулярным , теперь известного как граф Хватала . [4] [10]
  • Статья 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], он предположил, что в любом семействе множеств, замкнутом относительно операции взятия подмножеств , наибольшее попарно пересекающееся подсемейство всегда можно найти, выбрав элемент одного из множеств и сохранив все множества, содержащие этот элемент.
  • В 1979 году [17] он изучил взвешенную версию задачи покрытия множеств и доказал, что жадный алгоритм обеспечивает хорошие приближения к оптимальному решению, обобщая предыдущие невзвешенные результаты Дэвида С. Джонсона (J. Comp. Sys. Sci. 1974) и Ласло Ловаса (Discrete Math. 1975).

Хватал впервые заинтересовался линейным программированием под влиянием Джека Эдмондса , когда он был студентом в Ватерлоо. [4] Он быстро осознал важность секущих плоскостей для решения задач комбинаторной оптимизации, таких как вычисление максимальных независимых множеств , и, в частности, ввел понятие доказательства секущей плоскостью. [18] [19] [20] [21] В Стэнфорде в 1970-х годах он начал писать свой популярный учебник « Линейное программирование », который был опубликован в 1983 году. [4]

Секущие плоскости лежат в основе метода ветвей и отсечений , используемого эффективными решателями задачи коммивояжера . В период с 1988 по 2005 год команда Дэвида Л. Эпплгейта , Роберта Э. Биксби , Вашека Хватала и Уильяма Дж. Кука разработала один такой решатель, Concorde . [22] [23] В 2000 году команда была награждена премией Била-Орчарда-Хэйса за выдающиеся достижения в вычислительном математическом программировании за десятистраничную работу [24], в которой перечислены некоторые усовершенствования метода ветвей и отсечений, предложенные Concorde, которые привели к решению задачи с 13 509 городами, а в 2007 году она была награждена премией Фредерика У. Ланчестера за книгу « Задача коммивояжера: вычислительное исследование» .

Хватал также известен доказательством теоремы о художественной галерее [25] [26] [ 27] [28] исследованием самоописываемой цифровой последовательности [29] [30] его работой с Дэвидом Санкоффом над константами Хватала–Санкоффа, контролирующими поведение задачи о самой длинной общей подпоследовательности на случайных входных данных [31] и его работой с Эндре Семереди над сложными примерами для доказательства теоремы о разрешении [32] .

Книги

  • Вашек Хватал (1983). Линейное программирование . У. Х. Фриман. ISBN 978-0-7167-1587-0.. Японский перевод опубликован Кейгаку Шуппан, Токио, 1986 г.
  • C. Berge и V. Chvátal (ред.) (1984). Темы о совершенных графах. Elsevier. ISBN 978-0-444-86587-8. {{cite book}}: |author=имеет общее название ( помощь )
  • Дэвид Л. Эпплгейт; Роберт Э. Биксби; Вашек Хватал; Уильям Дж. Кук (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.

Смотрите также

Ссылки

  1. ^ Прошлые лауреаты премии Била-Орчарда-Хэйса.
  2. ↑ Премия Фредерика У. Ланчестера 2007 г., получено 19 марта 2017 г.
  3. ↑ Премия Джона фон Неймана по теории 2015 г., получено 19 марта 2017 г.
  4. ^ 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. 
  5. ^ Вашек Хватал — «путешествующий профессор», репортаж Concordia за четверг, 10 февраля 2005 г.
  6. ^ Проект математической генеалогии - Вацлав Хватал
  7. ↑ Вашек Хватал награжден премией за должность председателя Канадского научного совета, отчет Concordia за четверг, 23 октября 2003 г.
  8. ^ Хватал, Вашек (1997), «Похвала Клоду Берже», Дискретная математика , 165–166: 3–9, doi : 10.1016/s0012-365x(96)00156-2,
  9. ^ Хватал, Вацлав (1965), «О конечных и счетных жестких графах и турнирах», Commentationes Mathematicae Universitatis Carolinae , 6 : 429–438.
  10. ^ Вайсштейн, Эрик В. «График Хватала». Математический мир .
  11. ^ V. Chvátal; P. Erdős (1972), «Заметка о гамильтоновых цепях» (PDF) , Discrete Mathematics , 2 (2): 111–113, doi : 10.1016/0012-365x(72)90079-9,
  12. ^ Chvátal, V. (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 5 (3): 215–228, doi : 10.1016/0012-365x(73)90138-6,
  13. ^ Лесняк, Линда, t0-сложная гипотеза Хватала (PDF)
  14. ^ Математические обзоры MR0369170
  15. ^ В. Хватал; Дэвид А. Кларнер ; DE Кнут (1972), «Избранные задачи комбинаторного исследования» (PDF) , факультет компьютерных наук, Стэнфордский университет , Stan-CS-TR-72-292: Задача 25
  16. ^ Хватал, Вашек, Гипотеза в экстремальной комбинаторике
  17. ^ «Жадная эвристика для задачи покрытия множеств», Математика исследования операций, 1979
  18. ^ Chvátal, Václav (1973), «Многогранники Эдмондса и слабо гамильтоновы графы», Математическое программирование , 5 : 29–40, doi :10.1007/BF01580109, S2CID  8140217,
  19. ^ Chvátal, Václav (1973), «Многогранники Эдмондса и иерархия комбинаторных задач», Discrete Mathematics , 4 (4): 305–337, doi : 10.1016/0012-365x(73)90167-2,
  20. ^ Chvátal, Václav (1975), «Некоторые аспекты линейного программирования в комбинаторике» (PDF) , Congressus Numerantium , 13 : 2–30,
  21. ^ Chvátal, V. (1975), «О некоторых многогранниках, связанных с графами», Журнал комбинаторной теории, Серия B , 18 (2): 138–154, doi : 10.1016/0095-8956(75)90041-6.
  22. ↑ Математическая задача, долго озадачивала, медленно поддавалась решению. New York Times , 12 марта 1991 г.
  23. ↑ Artful Routes, Science News Online, 1 января 2005 г.
  24. ^ Эпплгейт, Дэвид; Биксби, Роберт; Хватал, Вашек; Кук, Уильям (1998), «О решении задач коммивояжера», Documenta Mathematica , Дополнительный том ICM III
  25. ^ Weisstein, Eric W. «Теорема о художественной галерее». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  26. ^ Диагонали: Часть I 4. Проблемы художественной галереи, AMS Feature Column Джозефа Малкевича
  27. ^ Теорема о художественной галерее Хватала в произведении Александра Богомольного «Разруби узел»
  28. ↑ Одержимость, Числа, Эпизод 3, Сезон 2
  29. ^ Хватал, Вашек (1993), «Заметки о последовательности Колакоски», Технические отчеты DIMACS , TR: 93-84
  30. ↑ Опасные проблемы, Science News Online, 13 июля 2002 г.
  31. ^ Chvátal, Václav; Sankoff, David (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Journal of Applied Probability , 12 (2): 306–315, doi :10.2307/3212444, JSTOR  3212444, S2CID  250345191.
  32. ^ Хватал, Вашек; Семереди, Эндре (1988), «Множество сложных примеров решения проблемы», Журнал ACM , 35 (4): 759–768, doi : 10.1145/48014.48016 , S2CID  2526816.
  33. ^ Борчерс, Брайан (25 марта 2007 г.). «Обзор задачи коммивояжера: вычислительное исследование». Обзоры MAA, Математическая ассоциация Америки .
  • Домашняя страница Chvátal
Взято с "https://en.wikipedia.org/w/index.php?title=Вацлав_Хватал&oldid=1243345678"