Вадим Геннадьевич Визинг - Vadim G. Vizing

Вадим Георгиевич Визинг (русский: Вади́м Гео́ргиевич Визинг, украинец: Вадим Георгійович Візінг; 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] Хотя теорема Визинга теперь является стандартным материалом во многих учебниках по теории графов, сначала Визингу было трудно опубликовать результат, и его статья по ней появилась в малоизвестном журнале, Дискрет. Анализ.[заметка 3]

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

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

Награды

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

Избранные публикации

V64.Визинг В. Г. (1964), "Об оценке хроматического класса п-граф », Дискрет. Анализ. (по-русски), 3: 25–30, Г-Н  0180505
V68.Визинг, В. Г. (1968), "Некоторые нерешенные проблемы теории графов", Успехи матем. Наук (по-русски), 23 (6): 117–134, Г-Н  0240000
V74.Визинг В. Г. (1974), "Сведение проблемы изоморфизма и изоморфного входа к задаче нахождения неплотности графа", Proc. 3-я Всесоюзная конф. Проблемы теоретической кибернетики, п. 124
V76.Визинг, В. Г. (1976), "Раскраски вершин заданными цветами", Дискрет. Анализ. (по-русски), 29: 3–10

Примечания

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

Рекомендации

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

внешняя ссылка