Визинг, Вадим Георгиевич
Вадим Георгиевич Визинг | |
---|---|
Дата рождения | 25 марта 1937 |
Место рождения | |
Дата смерти | 23 августа 2017 |
Место смерти | Одесса |
Страна | СССР → Украина |
Род деятельности | graph theorist, математик |
Научная сфера | математика |
Альма-матер |
Вадим Георгиевич Визинг (25 марта 1937, Киев — 23 августа 2017, Одесса) — советский и украинский математик, известный благодаря исследованиям в теории графов, прежде всего — теореме Визинга.
Мать — наполовину немка, в связи с чем, по утверждению Визинга, семья была сослана в Сибирь в 1947 году. Окончил Томский государственный университет по специальности математика в 1959 году, после чего поступил в аспирантуру в Институте математики имени Стеклова в Москве, работал в области теории приближений, но покинул аспирантуру в 1962 году, не получив степень[1]. Вместо этого переехал в Новосибирск, где в Институте математики Сибирского отделения АН СССР защитил в 1966 году кандидатскую диссертацию[1]. В 1974 году переехал в Одессу, где преподавал математику в течение многих лет в Технологическом институте пищевой промышленности[1].
Результат, известный сейчас как теорема Визинга, опубликован в 1964 году во время работы в Новосибирске, утверждает, что рёбра произвольного графа с не более чем рёбрами на вершину могут быть раскрашены не более чем цветами[2]. Западными авторами считается, что Визинг имел трудности с публикацией результата, указывая на «малоизвестность» журнала «Дискретный анализ» (издававшегося Институтом математики СО АН СССР). Другой вклад в теорию графов — введение понятия списочного раскраса[3] и формулировка нерешённой по состоянию на 2017 год гипотезы тотального раскраса[4][5]. Гипотеза Визинга (сформулированная в 1974 году и также нерешённая) касается числа доминирования прямого произведения графов[4] и определения модулярного произведения графов как способа сведения задач изоморфизма подграфа для нахождения крупнейших клик в графах[6].
С 1976 года Визинг изучал задачи теории расписаний, вернувшись к теории графов вновь только в 1995 году[1].
Примечания
- ↑ 1 2 3 4 Гутин, Тофт, 2000.
- ↑ В. Г. Визинг. Об оценке хроматического класса -графа // Дискретный анализ : сборник. — Новосибирск: Институт математики СО АН СССР, 1964. — Т. 3. — С. 25–30.
- ↑ Визинг В. Г. Раскраска вершин графа в предписанные цвета // Дискретный анализ. — 1976. — Т. 29. — С. 3—10.
- ↑ 1 2 В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи математических наук. — 1968. — Т. 23, вып. 6. — С. 117–134.
- ↑ Визинг утверждает, что он сформулировал эту гипотезу в 1964 году, однако пока она была опубликована в 1968 году, Бехзад независимо выдвинул аналогичную гипотезу
- ↑ Визинг В. Г. Сведение проблемы изоморфизма и изоморфного вхождения к задаче нахождения неплотности графа // Тез. Докл. III Всесоюз.конф. По проблемам теоретической кибернетики. — Новосибирск: ИМ СО АН СССР, 1974. — С. 124—125.
Литература
- Interview with Vadim G. Vizing // European Mathematical Society Newsletter. — 2000. — Т. 38, № December. — P. 22—23.
- Alexander Soifer. The Mathematical Coloring Book. — Springer-Verlag, 2008. — ISBN 9780387746401.. Страницы 136—137 воспроизводят письмо от 1995 года от Визинга к Сойферу относительно формулировки гипотезы тотального раскраска, также содержит некоторые биографические подробности о Визинге.