Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Вадим Георгиевич Визинг ( русский : Вадим Гео́ргиевич Визинг , украинский : Вадим Георгійович Візінг ; 25 марта 1937 - 23 августа 2017) [1] был советским и украинским математиком, известным своим вкладом в теорию графов , и особенно теоремой Визинга, утверждающей, что края любого простого графа максимальной степени Δ можно раскрасить не более чем в Δ + 1 цвет.

Биография [ править ]

Визинг родился в Киеве 25 марта 1937 года. [2] [3] Его мать была наполовину немкой [примечание 1], и из-за этого советские власти вынудили его семью переехать в Сибирь в 1947 году. После завершения учебы в бакалавриате. по математике в Томском государственном университете в 1959 г. защитил кандидатскую диссертацию. учился в Математическом институте им. Стеклова в Москве по теме приближения функций , но ушел в 1962 году, не получив ученой степени. [2] Вместо этого он вернулся в Новосибирск , где работал с 1962 по 1968 год в Российской академии наук.там и получение степени доктора философии. в 1966 г. [2] [4] В Новосибирске он был постоянным участником семинара А.А. Зыкова по теории графов. [5] После работы на различных дополнительных должностях в 1974 году он переехал в Одессу , где в течение многих лет преподавал математику в Академии пищевых технологий [2] (первоначально известной как Одесский технологический институт пищевой промышленности им. М. В. Ломоносова "). Одесский технологический институт пищевой промышленности имени Михаила Ломоносова »).

Результаты исследования [ править ]

Результат, ныне известный как теорема Визинга , опубликованный в 1964 году, когда Визинг работал в Новосибирске, утверждает, что ребра любого графа с не более чем Δ ребрами на вершину можно раскрасить, используя не более Δ + 1 цвет. [V64] Это продолжение работы Клода Шеннона , который показал, что края любого мультиграфа могут быть окрашены не более чем в (3/2) Δ цветов (жесткая граница, поскольку треугольник с Δ / 2 ребрами на сторону требует это много цветов). [6] [примечание 2] Хотя теорема Визинга теперь является стандартным материалом во многих учебниках по теории графов, Визингу изначально не удалось опубликовать результат, и его статья по ней опубликована в малоизвестном журнале Diskret. Анализ .[заметка 3]

Визинг также внес другой вклад в теорию графов и раскраску графов, включая введение раскраски списком , [V76] формулировку гипотезы о полной раскраске (все еще не решенной) о том, что ребра и вершины любого графа могут быть окрашены не более чем в Δ + 2 -х цветов, [V68] [примечание 4] гипотеза Визинга (также нерешенной) о доминировании числа из декартовых произведений графов , [V68] и в 1974 году определение модульного произведения графов , как способ снижения подграф изоморфизма проблем для нахождения максимальное количество кликов в графах.[V74] Он также доказал более сильную версию теоремы Брука, которая применима к раскраске списков.

С 1976 года Визинг перестал работать над теорией графов и вместо этого изучал проблемы составления расписаний [7], вернувшись снова к теории графов только в 1995 году [2].

Награды [ править ]

  • Большая серебряная медаль Института математики Сибирского отделения Российской академии наук [5]

Избранные публикации [ править ]

Заметки [ править ]

  1. ^ "Визинг" может быть латинизацией фонетической транскрипции немецкой фамилии Визинг на русский язык.
  2. ↑ Как в Gutin & Toft (2000), так и в Soifer (2008) , Визинг упоминает, что его работа была мотивирована теоремой Шеннона. Пример нижней границы треугольника см. В разделе « Красочная математика» .
  3. ↑ Полное наименование журнала - Академия Наук СССР. Сибирское отделение. Institut Matematiki. Дискретный анализ. Сборник трудов . В1980 г.он был переименован в Методы Дискретного анализа (название дано в Gutin & Toft (2000) ) и прекращен в 1991 г. [1] .
  4. ^ В Сойфер (2008) Визинг заявляет, что он сформулировал гипотезу в 1964 году, но к тому времени, когда она была опубликована в 1968 году, Бехзад независимо друг от друга высказал ту же гипотезу.

Ссылки [ править ]

  1. ^ Бородин, О.В., Памяти В. Г. Визинга [ Памяти В.Г. Визинга ], Институт математики им. Соболева , дата обращения 10.03.2018
  2. ^ a b c d e Гутин Григорий; Тофт, Бьярн (декабрь 2000 г.), «Интервью с Вадимом Визингом» (PDF) , Информационный бюллетень Европейского математического общества , 38 : 22–23
  3. ^ Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, ISBN 978-0-387-74640-1. На страницах 136–137 воспроизведено письмо Визинга к Сойферу от 1995 года относительно формулировки гипотезы полной окраски, которое также включает некоторые биографические данные о Визинге.
  4. ↑ Вадим Г. Визинг в проекте « Математическая генеалогия»
  5. ^ a b Мельников, Л.С. (2008), "О семинаре Зыкова в Новосибирске" [О семинаре Зыкова в Новосибирске] (PDF) , в кн. Касьянов, В.Н. (ред.), Построение и оптимизация параллельных программ , АП. Институт систем информатики им. Ершова, стр. 164–173.
  6. ^ Шеннон, Клод Э. (1949), "Теорема о раскраске линий сети", J. Math. Физика , 28 : 148–151, MR 0030203. .
  7. ^ Голдберг, Марк (1983), Развитие комбинаторики в СССР: краткий исторический и математический обзор , Delphic Associates, Falls Church, VA, p. 35, MR 0757359 , Визинг несколько изменил свои исследовательские интересы с чистой теории графов на теорию расписаний. 

Внешние ссылки [ править ]

  • Список последних публикаций Вадима Визинга и mathnet.ru