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

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

Вадим Георгійович Візінг (народився у 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, p. 124 .

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

  • Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 9780387746401 . Сторінки 136–137 відтворюють лист 1995 року від Візінга до Сойфера стосовно формулювання гіпотези тотального розфарбування, що також містить деякі біографічні подробиці про Візінга.
  • Вадим Георгійович Візінг at the Mathematics Genealogy Project
Отримано з http://uk.wikipedia.org/w/index.php?title=Вадим_Георгійович_Візінг&oldid=11933810