Вадим Г. Визинг
Советский украинский математик (1937–2017)

Вадим Георгиевич Визинг ( 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. Analiz . [примечание 3]

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

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

Награды

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

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

В64.
Визинг, В.Г. (1964), "Об оценке хроматического класса p -графа", Дискретный анализ , 3 : 25–30, MR  0180505
В68.
Визинг, В.Г. (1968), «Некоторые нерешенные проблемы теории графов», Успехи математических наук , 23 (6): 117–134, Bibcode :1968RuMaS..23..125V, doi :10.1070/RM1968v023n06ABEH001252, MR  0240000, S2CID  250848148
В74.
Визинг, В.Г. (1974), "Сведение задачи изоморфизма и изоморфного входа к задаче нахождения неплотности графа", Труды 3-й Всесоюзной конференции "Проблемы теоретической кибернетики" , стр. 124
В76.
Визинг, В.Г. (1976), «Раскраски вершин заданными цветами», Дискретный анализ , 29 : 3–10

Примечания

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

Ссылки

  1. ^ Бородин О.В., Памяти В. Г. Визинга [ Памяти В.Г. Визинга ] (на русском языке), Институт математики им. Соболева , получено 10 марта 2018 г.
  2. ^ abcde Гутин, Грегори; Тофт, Бьярне (декабрь 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. Physics , 28 (1–4): 148–151, doi :10.1002/sapm1949281148, MR  0030203.
  7. ^ Голдберг, Марк (1983), Развитие комбинаторики в СССР: краткий исторический и математический обзор , Delphic Associates, Фоллс-Черч, Вирджиния, стр. 35, MR  0757359, Визинг несколько изменил свои исследовательские интересы, перейдя от чистой теории графов к теории расписаний.
  • Список последних публикаций Вадима Визинга и mathnet.ru
Взято с "https://en.wikipedia.org/w/index.php?title=Вадим_Г._Визинг&oldid=1254467443"