Вацлав Хватал
Вацлав Хватал | |
|---|---|
 Вацлав Хватал (2020) | |
| Рожденный | 20 июля 1946 г. |
| Национальность | Канадский , Чешский |
| Альма-матер | Университет Ватерлоо Карлов университет |
| Известный | Схватил график Константы Хватала – Санкова Бонди – Теорема о захвате Пересечение числового неравенства График прочности |
| Награды | Премия Била-Орчард-Хейса (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] и этот вопрос остается открытым (за решение Chvátal предлагает приз в размере 10 долларов) [15] [16] он предположил, что в любом семействе множеств, замкнутом относительно операции взятия подмножеств , наибольшее попарно пересекающееся подсемейство всегда можно найти, выбрав элемент одного из множеств и сохранив все множества, содержащие этот элемент.
- В 1979 году [17] он изучил взвешенную версию проблемы покрытия множеств и доказал, что жадный алгоритм обеспечивает хорошие приближения к оптимальному решению, обобщая предыдущие невзвешенные результаты Дэвида С. Джонсона (J. Comp. Sys. Sci., 1974) и Ласло Ловаса (Discrete Математика, 1975).
Хватал впервые заинтересовался линейным программированием под влиянием Джека Эдмондса, когда Хватал был студентом Ватерлоо. [4] Он быстро осознал важность секущих плоскостей для решения задач комбинаторной оптимизации, таких как вычисление максимальных независимых множеств , и, в частности, ввел понятие доказательства секущей плоскости. [18] [19] [20] [21] В Стэнфорде в 1970-х годах он начал писать свой популярный учебник « Линейное программирование» , который был опубликован в 1983 году. [4]
Плоскости сечения лежат в основе метода ветвей и разрезов, используемого эффективными решателями задачи коммивояжера . В период с 1988 по 2005 год команда Дэвида Л. Эпплгейта , Роберта Э. Биксби , Вашека Хватала и Уильяма Дж. Кука разработала один такой решатель — Concorde . [22] [23] В 2000 году команда была награждена премией Била-Орчарда-Хейса за выдающиеся достижения в области вычислительного математического программирования за свою десятистраничную статью. [24] перечисление некоторых усовершенствований метода ветвей и разрезов, разработанных Конкордом, которые привели к решению примера в 13 509 городах, и он был удостоен премии Фредерика В. Ланчестера в 2007 году за книгу « Проблема коммивояжера: вычислительное исследование» .
Хватал также известен доказательством теоремы о художественной галерее . [25] [26] [27] [28] для исследования самоописывающей цифровой последовательности, [29] [30] за его работу с Дэвидом Санкоффом над константами Хватала – Санкоффа, управляющими поведением задачи о самой длинной общей подпоследовательности на случайных входных данных, [31] и за его работу с Эндре Семереди над сложными примерами доказательства резолюционной теоремы . [32]
Книги
[ редактировать ]- Васек Хватал (1983). Линейное программирование . У. Х. Фриман. ISBN 978-0-7167-1587-0 Японский перевод, опубликованный Кейгаку Шуппан, Токио, 1986 г.
- К. Берге и В. Хватал (ред.) (1984). Темы о идеальных графах . Эльзевир. ISBN 978-0-444-86587-8 .
{{cite book}}:|author=имеет общее имя ( справка ) - Дэвид Л. Эпплгейт; Роберт Э. Биксби; Вашек Хватал; Уильям Дж. Кук (2007). Задача коммивояжера: вычислительное исследование . Издательство Принстонского университета. ISBN 978-0-691-12993-8 . [33]
- Вашек Хватал, изд. (2011). Комбинаторная оптимизация: методы и приложения . ИОС Пресс. ISBN 978-1-60750-717-8 .
- Васек Хватал (2021). Дискретные математические чары Пауля Эрдеша. Простое введение . Издательство Кембриджского университета. ISBN 978-1-108-92740-6 .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Предыдущие победители премии Била-Орчарда-Хейса .
- ^ Премия Фредерика В. Ланчестера 2007 г. , получено 19 марта 2017 г.
- ↑ Премия Джона фон Неймана за теорию 2015 г. , получено 19 марта 2017 г.
- ^ Перейти обратно: а б с д и ж Авис, Д .; Бонди, А.; Кук, В .; Рид, Б. (2007). «Васек Хватал: Краткое введение» (PDF) . Графы и комбинаторика . 23 : 41–66. CiteSeerX 10.1.1.127.5910 . дои : 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), «О конечных и счетных жестких графах и турнирах» , Математические заметки Университета Каролины , 6 : 429–438 .
- ^ Вайсштейн, Эрик В. «График Хватала» . Математический мир .
- ^ В. Хватал ; П. Эрдеш (1972), «Заметка о гамильтоновых схемах» (PDF) , Discrete Mathematics , 2 (2): 111–113, doi : 10.1016/0012-365x(72)90079-9 ,
- ^ Хватал, В. (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 5 (3): 215–228, doi : 10.1016/0012-365x(73)90138-6 ,
- ^ Лесняк, Линда, Хватала t 0 -сложная гипотеза (PDF)
- ^ Математические обзоры MR0369170
- ^ В. Хватал ; Дэвид А. Кларнер ; DE Кнут (1972), «Избранные задачи комбинаторного исследования» (PDF) , Факультет компьютерных наук, Стэнфордский университет , Stan-CS-TR-72-292 : Задача 25
- ^ Хватал, Вашек , Гипотеза в экстремальной комбинаторике.
- ^ «Жадная эвристика для задачи покрытия множеств», Математика исследования операций, 1979
- ^ Хватал, Вацлав (1973), «Многогранники Эдмондса и слабо гамильтоновы графы», Mathematical Programming , 5 : 29–40, doi : 10.1007/BF01580109 , S2CID 8140217 ,
- ^ Хватал, Вацлав (1973), «Многогранники Эдмондса и иерархия комбинаторных задач», Discrete Mathematics , 4 (4): 305–337, doi : 10.1016/0012-365x(73)90167-2 ,
- ^ Хватал, Вацлав (1975), «Некоторые аспекты комбинаторики линейного программирования» (PDF) , Congressus Numerantium , 13 : 2–30 ,
- ^ Хватал, В. (1975), «О некоторых многогранниках, связанных с графами», Журнал комбинаторной теории, серия B , 18 (2): 138–154, doi : 10.1016/0095-8956(75)90041-6 .
- ^ Математическая задача, долгая загадка, медленная доходность. Нью-Йорк Таймс , 12 марта 1991 г.
- ^ Artful Routes , Science News Online, 1 января 2005 г.
- ^ Эпплгейт, Дэвид; Биксби, Роберт; Хватал, Вашек ; Кук, Уильям (1998), «О решении задач коммивояжера» , Documenta Mathematica , дополнительный том ICM III
- ^ Вайсштейн, Эрик В. «Теорема о художественной галерее». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/ArtGalleryTheorem.html
- ^ Диагонали: Часть I 4. Проблемы художественной галереи , Колонка статей AMS Джозефа Малкевича
- ^ Теорема Хваталя о художественной галерее в книге Александра Богомольного «Разрезать узел».
- ^ Одержимость , Numb3rs, Эпизод 3, Сезон 2
- ^ Хватал, Вашек (1993), «Заметки о последовательности Колакоски» , Технические отчеты DIMACS , TR: 93-84
- ^ Опасные проблемы , Science News Online, 13 июля 2002 г.
- ^ Хватал, Вацлав ; Санкофф, Дэвид (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Journal of Applied Probability , 12 (2): 306–315, doi : 10.2307/3212444 , JSTOR 3212444 , S2CID 250345191 .
- ^ Hvátal, Вашек ; Семереди, Эндре (1988), «Множество сложных примеров решения проблемы», Journal of the ACM , 35 (4): 759–768, doi : 10.1145/48014.48016 , S2CID 2526816 .
- ^ Борчерс, Брайан (25 марта 2007 г.). «Обзор задачи коммивояжера: вычислительное исследование » . Обзоры MAA, Математическая ассоциация Америки .
Внешние ссылки
[ редактировать ]
- Канадские математики
- Канадцы чешского происхождения
- Чешские математики
- Чехословацкие эмигранты в Канаде
- Канадские исследовательские кафедры
- Комбинатористы
- Выпускники Университета Ватерлоо
- Выпускники Карлова университета
- 1946 года рождения
- Живые люди
- Академический состав Университета Конкордия
- Лауреаты премии Джона фон Неймана по теории