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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Візінг народився в Києві 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. а б в г д {{subst:harvtxt|Gutin|Toft|2000}}.
  2. Soifer (2008).
  3. Vizing, V. G. (1964), «On an estimate of the chromatic class of a p-graph» (In Russian), Diskret. Analiz. 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 році [1].
  6. Vizing, V. G. (1976), «Vertex colorings with given colors» (In Russian), Diskret. Analiz. 29: 3–10 .
  7. Vizing, V. G. Some unsolved problems in graph theory (In Russian) // Uspehi Mat. Naukno., 23 (1968) (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 .

Джерела[ред.ред. код]

  • Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 9780387746401 . Сторінки 136–137 відтворюють лист 1995 року від Візінга до Сойфера стосовно формулювання гіпотези тотального розфарбування, що також містить деякі біографічні подробиці про Візінга.
  • Вадим Георгійович Візінг at the Mathematics Genealogy Project