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

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

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

Біографія

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

Результат, відомий зараз як теорема Візінга, опублікований у 1964 році, коли Візінг працював у Новосибірську, стверджує, що ребра довільного графу з не більше ніж Δ ребрами на вершину можуть бути розфарбовані не більше ніж Δ + 1 кольорами.[3] Це продовження роботи Клода Шеннона, який показав, що будь-який мультиграф може мати реберне розфарбування не більше ніж (3/2)Δ кольорами (точна границя, як трикутник із Δ/2 ребрами на сторону потребує таке число кольорів).[4] Хоча теорема Візінга є зараз стандартним матеріалом у багатьох підручниках з теорії графів, Візінг мав спочатку труднощі з опублікуванням цього результату, і його стаття з цим результатом з'являється у маловідомому журналі, Дискретный анализ.[5] Візінг також зробив інші внески до теорії графів та розфарбування графів, включаючи введення спискового розфарбування[en],[6] формулювання гіпотези тотального розфарбування (досі нерозв'язана), у якій стверджується, що ребра та вершини будь-якого графу можуть бути розфарбовані разом не більше ніж Δ + 2 кольорами,[7] Гіпотеза Візінга[ru] (також нерозв'язана) стосується числа домінування декартового добутку графів,[8] і визначення модулярного добутку графів[en] від 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 {{citation}}: |format= вимагає |url= (довідка).
  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 [Архівовано 17 травня 2008 у Wayback Machine.].
  5. ↑ Повна назва цього журналу була Академия наук СССР. Сибирское отделение. Институт математики. Дискретный анализ. Сборник трудов. Він був перейменований на Методы дискретного анализа у 1980 році (ім'я, дане йому у Gutin та Toft, (2000)), припинив існування у 1991 році [1].
  6. ↑ Vizing, V. G. (1976), Vertex colorings with given colors, Diskret. Analiz. (In Russian), 29: 3—10 {{citation}}: |format= вимагає |url= (довідка).
  7. ↑ Vizing, V. G. (1968). Some unsolved problems in graph theory. Uspehi Mat. Naukno. (In Russian). 23 (6): 117—134. MR0240000. {{cite journal}}: |format= вимагає |url= (довідка). У 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 (PDF), European Mathematical Society Newsletter, 38: 22—23, архів оригіналу (PDF) за 5 червня 2011, процитовано 10 квітня 2010.
  • Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 9780387746401. Сторінки 136—137 відтворюють лист 1995 року від Візінга до Сойфера стосовно формулювання гіпотези тотального розфарбування, що також містить деякі біографічні подробиці про Візінга.
  • Вадим Георгійович Візінг(англ.) у проєкті «Математична генеалогія».


Ейлер Це незавершена стаття про математика.
Ви можете допомогти проєкту, виправивши або дописавши її.
українська персоналія Це незавершена стаття про особу, що має стосунок до України.
Ви можете допомогти проєкту, виправивши або дописавши її.