Вацлав (Вашек) Хватал ( чешский: [ˈvaːtslaf ˈxvaːtal] - почетный профессор факультета компьютерных наук и программной инженерии в Университете Конкордия в Монреале, Квебек , Канада. Он много публиковал по вопросам теории графов , комбинаторики и комбинаторной оптимизации. .
Вацлав Хваталь | |
---|---|
Родившийся | |
Национальность | Канадская , чешская |
Альма-матер | Университет Ватерлоо Карлова университета |
Награды | Премия Биля-Орчарда-Хейса (2000) [1] Docteur Honoris Causa, Université de la Méditerranné (2003) Премия Фредерика В. Ланчестера (2007) [2] Премия Джона фон Неймана за теорию (2015) [3] |
Научная карьера | |
Поля | Математика , информатика , исследования операций |
Учреждения | Университет Конкордия |
Докторант | Криспин Нэш-Уильямс |
Докторанты | Дэвид Авис (Стэнфорд, 1977), Брюс Рид (Макгилл, 1986) |
биография
Хватал родился в Праге в 1946 году и получил математическое образование в Карловом университете в Праге, где он учился под руководством Зденека Хедрлина. [4] Он бежал из Чехословакии в 1968 году, через три дня после советского вторжения , [5] и защитил докторскую диссертацию. Осенью 1970 года получил степень бакалавра математики в Университете Ватерлоо под руководством Криспина Сент-Дж. А. Нэш-Уильямса . [4] [6] Впоследствии он занимал должности в Университете Макгилла (1971 и 1978-1986), Стэнфордском университете. (1972 и 1974-1977), Université de Montréal (1972-1974 и 1977-1978) и Rutgers University (1986-2004), прежде чем вернуться в Монреаль на кафедру канадских исследований комбинаторной оптимизации [7] [5] в Concordia. (2004-2011) и кафедрой дискретной математики Канады (2011-2014) до выхода на пенсию.
Исследовать
Хваталь впервые познакомился с теорией графов в 1964 году, когда он нашел книгу Клода Берже в книжном магазине города Пльзень [8], и большая часть его исследований связана с теорией графов:
- Его первая математическая публикация в возрасте 19 лет касалась ориентированных графов, которые не могут быть отображены в самих себя никаким нетривиальным гомоморфизмом графов [9].
- Другим теоретико-графическим результатом Хватала было построение в 1970 г. наименьшего возможного графа без треугольников, который является как 4- хроматическим, так и 4- регулярным графом, который теперь известен как граф Хватала . [4] [10]
- 1972 бумага [11] , касающиеся гамильтоновых циклов для связности и максимального независимого множества размера графа, заработал Chvátal его количество Erdos , равное 1. В частности, если существует не ев таким образом, что данный график с - вершина соединенных и не имеет ( s + 1) -вершинное независимое множество, граф должен быть гамильтоновым. Avis et al. [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). ) и Ласло Ловас (Дискретная математика. 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). Линейное программирование . WH Freeman. ISBN 978-0-7167-1587-0.. Японский перевод опубликован Кэйгаку Шуппан, Токио, 1986.
- К. Берге и В. Хватал (ред.) (1984). Темы об идеальных графах . Эльзевир. ISBN 978-0-444-86587-8.CS1 maint: дополнительный текст: список авторов ( ссылка )
- Дэвид Л. Эпплгейт; Роберт Э. Биксби; Вашек Хватал; Уильям Дж. Кук (2007). Проблема коммивояжера: вычислительное исследование . Издательство Принстонского университета. ISBN 978-0-691-12993-8.
- Вашек Хватал (редактор) (2011). Комбинаторная оптимизация: методы и приложения . IOS Press. ISBN 978-1-60750-717-8.CS1 maint: дополнительный текст: список авторов ( ссылка )
Смотрите также
- Список людей Университета Ватерлоо
Рекомендации
- ^ Прошлые победители премии Билла-Орчарда-Хейса .
- ↑ Frederick W. Lanchester Prize 2007 , получено 19 марта 2017 г.
- ^ John von Neumann Theory Prize 2015 , получено 19 марта 2017 г.
- ^ а б в г д е Авис, Д .; Бонди, А .; Кук, W .; Рид, Б. (2007). "Васек Чватал: Краткое введение" (PDF) . Графы и комбинаторика . 23 : 41–66. CiteSeerX 10.1.1.127.5910 . DOI : 10.1007 / s00373-007-0721-4 . S2CID 11121944 .
- ^ a b Васек Хватал - «странствующий профессор» , отчет Concordia за четверг, 10 февраля 2005 г.
- ^ Проект математической генеалогии - Вацлав Хватал
- ^ Васек Chvatal награжден Канада исследований Председатель , четверг Отчет Конкордии, 23 октября, 2003.
- ^ Chvátal, Vašek (1997), "В похвале Клод Berge" , дискретная математика , 165-166: 3-9, DOI : 10.1016 / s0012-365x (96) 00156-2,
- ^ Chvátal, Вацлав (1965), "О конечных и счетных жестких графах и турнирах" , Commentationes Mathematicae Universitatis Carolinae , 6 : 429–438.
- ^ Вайсштейн, Эрик В. «График Chvátal» . MathWorld .
- ^ В. Хваталь ; П. Эрдеш (1972), «Заметка о гамильтоновых схемах» (PDF) , Дискретная математика , 2 (2): 111–113, DOI : 10.1016 / 0012-365x (72) 90079-9,
- ^ Chvátal, В. (1973), "Жесткие графики и гамильтоновы цепи" , дискретная математика , 5 (3): 215-228, DOI : 10.1016 / 0012-365x (73) 90138-6,
- ^ Лесняк, Линда, t 0- трудная гипотеза Хватала (PDF)
- ^ Математические обзоры MR0369170
- ^ В. Хваталь ; Дэвид А. Кларнер ; Д.Е. Кнут (1972), "Избранные комбинаторные исследовательские задачи" (PDF) , факультет компьютерных наук, Стэнфордский университет , Stan-CS-TR-72-292: Проблема 25
- ^ Chvátal, Vašek , Гипотеза в экстремальной комбинаторике
- ^ "Жадная эвристика для проблемы покрытия множества", Математика исследования операций, 1979
- ^ Chvátal, Вацлав (1973), "Эдмондс многогранники и слабо гамильтоновые графы", Математическое программирование , 5 : 29-40, DOI : 10.1007 / BF01580109 , S2CID 8140217,
- ^ Chvátal, Вацлав (1973), "Многогранники Эдмондса и иерархия комбинаторных задач", Дискретная математика , 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 г.
- ^ Хитрые Маршруты , Science News Online, январь 1, 2005.
- ^ Эпплгейт, Дэвид; Биксби, Роберт; Хватал, Вашек ; Кук, Уильям (1998), «О решении задач коммивояжера» , Documenta Mathematica , Extra Volume ICM III
- ^ Вайсштейн, Эрик В. «Теорема художественной галереи». Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/ArtGalleryTheorem.html
- ^ Диагонали: Часть I 4. Проблемы художественной галереи , Рубрика с характеристиками AMS Иосифа Малькевича.
- ^ Художественная галерея теорема Chvatal в в Александр Богомольный «s Cut Узла
- ↑ Одержимость , Numb3rs, Эпизод 3, Сезон 2
- ^ Chvátal, Vašek (1993), "Заметки о последовательности Колакоски" , Технические отчеты DIMACS , TR: 93-84
- ↑ Dangerous Problems , Science News Online, 13 июля 2002 г.
- ^ Хватал, Вацлав ; Sankoff, Дэвид (1975), "Самые длинные общие подпоследовательности двух случайных последовательностей", Журнал прикладной вероятности , 12 (2): 306-315, DOI : 10,2307 / 3212444 , JSTOR 3212444.
- ^ Хватал, Вашек ; Семереди, Эндре (1988), "Многие твердые примеры для разрешения", Журнал ACM , 35 (4): 759-768, DOI : 10,1145 / 48014,48016 , S2CID 2526816.
Внешние ссылки
- Домашняя страница Chvátal