Vadim G. Vizing

Un article de Wikipédia, l'encyclopédie libre.
Vadim Vizing
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 80 ans)
OdessaVoir et modifier les données sur Wikidata
Nationalité
Formation
Activités

modifier - modifier le code - modifier WikidataDocumentation du modèle

Vadim Georgievich Vizing (en russe : Вади́м Гео́ргиевич Визинг, en ukrainien : Вадим Георгійович Візінг) né le à Kiev, et mort le à Odessa)[1],[2] est un mathématicien soviétique et ukrainien, connu pour ses contributions à la théorie des graphes, et en particulier pour le théorème de Vizing qui énonce que les arêtes d'un graphe simple de degré au plus Δ peuvent être colorées avec au plus Δ + 1 couleurs.

Biographie[modifier | modifier le code]

Vizing est né à Kiev le 25 mars 1937[3],[4]. Sa mère était pour moitié d'origine allemande[note 1] et pour cette raison les autorités soviétiques ont obligé sa famille à déménager en Sibérie en 1947. Vizing termine ses études de premier cycle en mathématiques à l'université d'État de Tomsk en 1959, puis il commence un doctorat à l'Institut de mathématiques Steklov à Moscou, sur le thème de l'approximation des fonctions, mais ce sujet ne l’intéresse guère et il quitte l'Institut en 1962 sans avoir obtenu son diplôme[3]. Il retourne à Novossibirsk et travaille de 1962 à 1968 à l'Académie des sciences de Russie où il obtient un doctorat en 1966[3],[5] sous la direction sinon officielle, du moins effective de A. A. Zykov[3]. À Novossibirsk, il est un participant régulier au séminaire de A. A. Zykov en théorie des graphes[6]. Après avoir occupé divers autres postes, il part pour Odessa en 1974, où il enseigne les mathématiques pendant de nombreuses années à l'Académie de technologie alimentaire [3] (connue au début sous le nom de Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, Institut technologique d'Odessa de l'industrie alimentaire qui porte le nom de Mikhaïl Lomonossov). con

Résultats de recherche[modifier | modifier le code]

Le résultat maintenant connu sous le nom de théorème de Vizing, publié en 1964 lorsque Vizing travaillait à Novossibirsk, indique que les arêtes de tout graphe avec au plus Δ arêtes par sommet peuvent être colorées en utilisant au plus Δ + 1 couleurs[7]. Il s'agit d'une continuation du travail de Claude Shannon, qui a montré que tout multigraphe peut avoir ses arêtes colorées avec au plus (3/2) Δ couleurs (cette borne est atteinte puisqu'un triangle avec Δ / 2 arêtes par côté exige ce nombre de couleurs)[8]. Le théorème de Vizing est maintenant un thème standard dans de nombreux manuels de théorie des graphes, mais Vizing avait du mal à publier le résultat et son article sur ce sujet apparaît dans un journal peu connu : Diskret. Analiz..

Vizing a également apporté d'autres contributions à la théorie des graphes et à la coloration des graphes, y compris l'introduction de la coloration de liste[9], la formulation de la conjecture de coloration totale (toujours non résolue) indiquant que les arêtes et les sommets de tout graphe peuvent être colorés ensemble avec au plus Δ + 2 couleurs[10]. La conjecture de Vizing (également non résolue) concernant la taille d'un ensemble dominant dans les produits cartésiens de graphes[10] et la définition en 1974 du produit modulaire des graphes comme moyen de réduire les problèmes d'isomorphisme des sous-graphes à la recherche de cliques maximales dans les graphes[11]. Il a également prouvé une version plus forte du théorème de Brooks qui s'applique à la coloration des listes.

À partir de 1976, Vizing a cessé de travailler en théorie des graphes pour étudier des problèmes d'ordonnancement[12] ; il ne revient à la théorie des graphes qu'en 1995[3].

Récompense[modifier | modifier le code]

  • Grande médaille d'argent de l'Institut de mathématiques du département sibérien de l'Académie russe des sciences [6]

Publications (sélection)[modifier | modifier le code]

  • (ru) Vadim Vizing, « On an estimate of the chromatic class of a p-graph », Diskret. Analiz., vol. 3,‎ , p. 25–30 (MR 0180505)
  • (ru) Vadim Vizing, « Some unsolved problems in graph theory », Uspekhi Mat. Nauk, vol. 23, no 6,‎ , p. 117–134 (MR 0240000)
  • Vadim Vizing, « 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
  • (ru) Vadim Vizing, « Vertex colorings with given colors », Diskret. Analiz., vol. 29,‎ , p. 3–10

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. ↑ "Vizing" est peut-être l'écriture romane du nom allemand russifié Wiesing ou Wising.

Références[modifier | modifier le code]

  1. ↑ (ru) Oleg V. Borodin, « Памяти В. Г. Визинга (In memoriam V. G. Vizing) », Sobolev Institute of Mathematics (en),‎ 2018 ? (lire en ligne).
  2. ↑ (ru) V. L. Beresnev, A. A. Evdokimov, S. V. Sevast’yanov et Yu. V. Shamardin, « To the memory of V. G. Vizing », Diskretn. Anal. Issled. Oper, vol. 24, no 4,‎ , p. 130 (zbMATH 1399.01006).
  3. ↑ a b c d e et f Gregory Gutin et Bjarne Toft, « Interview with Vadim G. Vizing », European Mathematical Society Newsletter, vol. 38,‎ , p. 22–23 (lire en ligne)
  4. ↑ Alexander Soifer, The Mathematical Coloring Book, Springer-Verlag, (ISBN 978-0-387-74640-1). Les pages 136–137 reproduiseent une lettre de 1995 de Vizing à Soifer concernant la formulation de la conjecture de la coloration totale ; le texte contient aussi quelques détails biographiques sur Vizing.
  5. ↑ (en) « Vadim Georgievich Vizing », sur le site du Mathematics Genealogy Project
  6. ↑ a et b Leonid S. Mel'nikov, « О семинаре Зыкова в Новосибирске (About Zykov's seminar in Novosibirsk) », dans V. N. Kasyanov (éditeur), Parallel programs construction and optimization, A. P. Ershov Institute of Informatics Systems,‎ (lire en ligne), p. 164–173
  7. ↑ Vizing 1964.
  8. ↑ Claude E. Shannon, « A theorem on coloring the lines of a network », J. Math. Physics, vol. 28,‎ , p. 148-151 (MR 0030203).
  9. ↑ Vizing 1976.
  10. ↑ a et b Vizing 1968.
  11. ↑ Vizing 1974.
  12. ↑ Mark Goldberg, The development of combinatorics in the USSR: a brief historical and mathematical survey, Delphic Associates, Falls Church, VA, (MR 757359), p. 35

Liens externes[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Vadim_G._Vizing&oldid=197645121 ».