Вадим Георгійович Візінг

Вадим Георгійович Візінг (25 березня 1937, Київ — 23 серпня 2017, Одеса) — український математик, відомий завдяки результатам у теорії графів, і особливо через теорему Візінга, у якій стверджується, що ребра довільного графу з максимальним степенем Δ можуть бути розфарбовані не більше ніж Δ + 1 кольорами.

Вадим Георгійович Візінг
Народився 25 березня 1937(1937-03-25)
Київ, Українська РСР, СРСР
Помер 23 серпня 2017(2017-08-23) (80 років)
Країна  Україна
Діяльність математик
Галузь теорія графів
Alma mater Томський державний університет

Біографія

Візінг народився в Києві 25 березня, 1937 року.[1][2] Його мати була наполовину німкеня, і через це радянська влада примусила його родину переїхати до Сибіру у 1947 році. Після завершення Томського державного університету з математики в 1959 році, він почав навчання в аспірантурі в Інституті математики ім. Стєклова у Москві, з теми наближення функцій, але він покинув аспірантуру у 1962 році не отримавши ступінь.[1] Натомість, він повернувся до Новосибірську, де працював у 1962-68 роках у Російській академії наук і отримав ступінь кандидата у 1966 році.[1] Після перебування на декількох різних посадах, він переїхав до Одеси у 1974 році, де викладав математику протягом багатьох років у Академії харчових технологій.[1]

Результат, відомий зараз як теорема Візінга, опублікований у 1964 році, коли Візінг працював у Новосибірську, стверджує, що ребра довільного графу з не більше ніж Δ ребрами на вершину можуть бути розфарбовані не більше ніж Δ + 1 кольорами.[3] Це продовження роботи Клода Шеннона, який показав, що будь-який мультиграф може мати реберне розфарбування не більше ніж (3/2)Δ кольорами (точна границя, як трикутник із Δ/2 ребрами на сторону потребує таке число кольорів).[4] Хоча теорема Візінга є зараз стандартним матеріалом у багатьох підручниках з теорії графів, Візінг мав спочатку труднощі з опублікуванням цього результату, і його стаття з цим результатом з'являється у маловідомому журналі, Дискретный анализ.[5] Візінг також зробив інші внески до теорії графів та розфарбування графів, включаючи введення спискового розфарбування,[6] формулювання гіпотези тотального розфарбування (досі нерозв'язана), у якій стверджується, що ребра та вершини будь-якого графу можуть бути розфарбовані разом не більше ніж Δ + 2 кольорами,[7] Гіпотеза Візінга (також нерозв'язана) стосується числа домінування декартового добутку графів,[8] і визначення модулярного добутку графів від 1974 року, як спосіб зведення задач ізоморфізму підграфу до знаходження найбільших клік у графах.[9] Починаючи з 1976 року, Візінг припинив роботу в теорії графів і вивчав задачі теорії розкладів натомість, повернувшись до теорії графів знову тільки у 1995 році.[1]

Примітки
  1. Gutin та Toft, (2000).
  2. Soifer, (2008).
  3. Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz. (In Russian) 3: 25–30. MR0180505..
  4. Shannon, Claude E. (1949). A theorem on coloring the lines of a network. J. Math. Physics 28: 148—151. MR0030203.. У Gutin та Toft, (2000) та Soifer, (2008), Візінг пригадує, що його робота була мотивована теоремою Шеннона. Для прикладу з нижньою границею трикутика, дивіться напр. Colorful Mathematics.
  5. Повна назва цього журналу була Академия наук СССР. Сибирское отделение. Институт математики. Дискретный анализ. Сборник трудов. Він був перейменований на Методы дискретного анализа у 1980 році (ім'я, дане йому у Gutin та Toft, (2000)), припинив існування у 1991 році .
  6. Vizing, V. G. (1976). Vertex colorings with given colors. Diskret. Analiz. (In Russian) 29: 3–10..
  7. Vizing, V. G. (1968). Some unsolved problems in graph theory. Uspehi Mat. Naukno. (In Russian) 23 (6): 117–134. MR0240000.. У Soifer, (2008), Візінг стверджує, що він сформулював цю гіпотезу у 1964 році, проте доки вона була опублікована, у 1968 році Behzad незалежно висунув тотожню гіпотезу.
  8. Vizing, (1968).
  9. Vizing, V. G. (1974). Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph. Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics. с. 124..

Джерела
  • Gutin, Gregory; Toft, Bjarne (December 2000). Interview with Vadim G. Vizing. European Mathematical Society Newsletter 38: 22–23..
  • Soifer, Alexander (2008). The Mathematical Coloring Book. Springer-Verlag. ISBN 9780387746401.. Сторінки 136—137 відтворюють лист 1995 року від Візінга до Сойфера стосовно формулювання гіпотези тотального розфарбування, що також містить деякі біографічні подробиці про Візінга.
  • Вадим Георгійович Візінг(англ.) в проєкті «Математична генеалогія».
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.