Вадим Георгиевич Визинг
Vadim Georgievich Vizing ( Russian : Вадим Георгиевич Визинг , Russian : Вадим Георгиевич Визинг; 25 March 1937 – 23 August 2017) [1] был советским и украинским математиком, известным своим вкладом в теорию графов , и особенно благодаря теореме Визинга, утверждающей, что ребра любого простого графа с максимальной степенью Δ можно раскрасить не более чем Δ + 1 цветом.
Биография
[ редактировать ]Визинг родился в Киеве . 25 марта 1937 года [2] [3] Его мать была наполовину немкой, [примечание 1] и из-за этого советские власти вынудили его семью переехать в Сибирь в 1947 году. После окончания бакалавриата по математике в Томском государственном университете в 1959 году он защитил докторскую диссертацию. учился в Математическом институте им. Стеклова в Москве по теме аппроксимации функций , но ушел в 1962 году, не получив ученой степени. [2] Вместо этого он вернулся в Новосибирск , где с 1962 по 1968 год работал в Российской академии наук и получил степень доктора философии. в 1966 году. [2] [4] В Новосибирске он был постоянным участником семинара А. А. Зыкова по теории графов. [5] Заняв различные дополнительные должности, в 1974 году переехал в Одессу , где долгие годы преподавал математику в Академии пищевых технологий. [2] (originally known as Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, "Odessa Technological Institute of Food Industry named after Mikhail Lomonosov ").
Результаты исследования
[ редактировать ]Результат, ныне известный как теорема Визинга , опубликованный в 1964 году, когда Визинг работал в Новосибирске, утверждает, что ребра любого графа с не более чем Δ ребрами на вершину могут быть раскрашены с использованием не более Δ + 1 цвета. [В64] Это продолжение работы Клода Шеннона , который показал, что ребра любого мультиграфа могут быть раскрашены не более чем в (3/2)Δ цветов (жесткая граница, поскольку треугольник с Δ/2 ребрами на сторону требует такого количества цветов ). [6] [примечание 2] Хотя теорема Визинга сейчас является стандартным материалом во многих учебниках по теории графов, у Визинга изначально возникли проблемы с публикацией результата, и его статья по ней появилась в малоизвестном журнале Discret. Анализ . [примечание 3]
Визинг также внес другой вклад в теорию графов и раскраску графов, включая введение раскраски списков . [В76] формулировка гипотезы о полной раскраске (пока нерешенной), утверждающая, что ребра и вершины любого графа вместе могут быть раскрашены не более чем в Δ + 2 цвета, [V68] [примечание 4] Гипотеза Визинга (также нерешенная) о числе доминирования декартовых произведений графов , [V68] и определение 1974 года модульного произведения графов как способа сведения проблем изоморфизма подграфов к поиску максимальных клик в графах. [В74] Он также доказал более сильную версию теоремы Брука , применимую к раскраске списков.
С 1976 года Визинг прекратил работу над теорией графов и вместо этого занялся проблемами планирования . [7] снова вернулся к теории графов только в 1995 году. [2]
Награды
[ редактировать ]- Большая серебряная медаль Института математики Сибирского отделения РАН. [5]
Избранные публикации
[ редактировать ]| В64. |
| V68. | Визинг В.Г. (1968), "Некоторые нерешенные задачи теории графов", Успехи матем. Наук , 23 (6): 117–134, Бибкод : 1968РуМаС..23..125В , doi : 10.1070/RM1968v023n06ABEH001252 , MR 0240000 , S2CID 250848148 |
| В74. | Визинг В.Г. (1974), "Редукция проблемы изоморфизма и изоморфного входа к задаче нахождения неплотности графа", Тр. 3-я Всесоюзная конф. Проблемы теоретической кибернетики , с. 124 |
| В76. | Визинг, В.Г. (1976), "Раскраски вершин заданными цветами", Дискрет. Анализ. (на русском языке), 29 : 3–10. |
Примечания
[ редактировать ]- ^ «Визинг» может быть латинизацией фонетической транскрипции немецкой фамилии Визинг на русский язык.
- ^ И в Gutin & Toft (2000) , и в Soifer (2008) Визинг упоминает, что его работа была мотивирована теоремой Шеннона. Пример нижней границы треугольника см., например, в разделе « Цветная математика» .
- ^ The full name of this journal was Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudov . It was renamed Metody Diskretnogo Analiza in 1980 (the name given for it in Gutin & Toft (2000) ) and discontinued in 1991 [1] .
- ^ В Сойфере (2008) Визинг утверждает, что он сформулировал гипотезу в 1964 году, но к моменту ее публикации в 1968 году Бехзад независимо выдвинул ту же гипотезу.
Ссылки
[ редактировать ]- ^ Бородин О.В., Памяти В. Г. Визинга [ Памяти В.Г. Визинга ] (на русском языке), Институт математики им. Соболева , получено 10 марта 2018 г.
- ↑ Перейти обратно: Перейти обратно: а б с д и Гутин, Григорий; Тофт, Бьярне (декабрь 2000 г.), «Интервью с Вадимом Г. Визингом» (PDF) , Информационный бюллетень Европейского математического общества , 38 : 22–23
- ^ Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, ISBN 978-0-387-74640-1 . На страницах 136–137 воспроизведено письмо Визинга Сойферу от 1995 года, касающееся формулировки гипотезы о полной окраске, которое также включает некоторые биографические подробности о Визинге.
- ^ Вадим Г. Визинг в проекте «Математическая генеалогия»
- ↑ Перейти обратно: Перейти обратно: а б Мельников, Л.С. (2008), «О семинаре Зыкова в Новосибирске» [О семинаре Зыкова в Новосибирске] (PDF) , в Касьянов В.Н. (ред.), Построение и оптимизация параллельных программ (на русском языке), Институт проблем им. А.П. Ершова. Системы информатики, стр. 164–173.
- ^ Шеннон, Клод Э. (1949), «Теорема о раскраске линий сети», J. Math. Физика , 28 (1–4): 148–151, doi : 10.1002/sapm1949281148 , MR 0030203 .
- ^ Гольдберг, Марк (1983), Развитие комбинаторики в СССР: краткий исторический и математический обзор , Delphic Associates, Falls Church, VA, стр. 35, MR 0757359 ,
Визинг несколько изменил свои исследовательские интересы: от чистой теории графов к теории расписаний.
Внешние ссылки
[ редактировать ]- Список последних публикаций Вадима Визинга и mathnet.ru
