Vadim Georgievich Vizing ( ruso : Вадим Георгиевич Визинг , Ucrania : Вадим Георгійович Візінг ; 25 marzo 1937 a 23 agosto 2017) [1] fue un Soviética y Ucrania matemático conocido por sus contribuciones a la teoría de grafos , y especialmente para el teorema de Vizing indicando que los bordes de cualquier gráfico simple con el grado máximo Δ se puede colorear con un máximo de Δ + 1 colores.
Biografía
Vizing nació en Kiev el 25 de marzo de 1937. [2] [3] Su madre era mitad alemana, [nota 1] y debido a esto las autoridades soviéticas obligaron a su familia a mudarse a Siberia en 1947. Después de completar sus estudios de pregrado en matemáticas en la Universidad Estatal de Tomsk en 1959, comenzó su doctorado. Estudia en el Instituto Steklov de Matemáticas de Moscú , sobre el tema de la aproximación de funciones , pero se fue en 1962 sin completar su título. [2] En cambio, regresó a Novosibirsk , trabajando desde 1962 hasta 1968 en la Academia de Ciencias de Rusia allí y obteniendo un doctorado. en 1966. [2] [4] En Novosibirsk, fue un participante habitual en el seminario de AA Zykov sobre teoría de grafos. [5] Después de ocupar varios puestos adicionales, se trasladó a Odessa en 1974, donde enseñó matemáticas durante muchos años en la Academia de Tecnología de Alimentos [2] (originalmente conocida como Одесский технологический институт пищевой промышомевой промышованим. Мтий промышованиной ". Instituto Tecnológico de la Industria Alimentaria de Odessa que lleva el nombre de Mikhail Lomonosov ").
Resultados de la investigacion
El resultado ahora conocido como teorema de Vizing , publicado en 1964 cuando Vizing estaba trabajando en Novosibirsk, establece que los bordes de cualquier gráfico con como máximo Δ bordes por vértice se pueden colorear usando como máximo Δ + 1 colores. [V64] Es una continuación del trabajo de Claude Shannon , quien demostró que cualquier multigrafo puede tener sus bordes coloreados con un máximo de (3/2) colores Δ (un límite apretado, ya que un triángulo con Δ / 2 bordes por lado requiere tantos colores). [6] [nota 2] Aunque el teorema de Vizing es ahora material estándar en muchos libros de texto de teoría de grafos, Vizing tuvo problemas para publicar el resultado inicialmente, y su artículo aparece en una publicación desconocida, Diskret. Analiz . [nota 3]
Vizing también hizo otras contribuciones a la teoría de grafos y la coloración de grafos, incluida la introducción de coloración de listas , [V76] la formulación de la conjetura de coloración total (aún sin resolver) que indica que los bordes y vértices de cualquier gráfico se pueden colorear juntos como máximo con Δ + 2 colores, [V68] [nota 4] La conjetura de Vizing (también sin resolver) sobre el número de dominación de los productos cartesianos de los gráficos , [V68] y la definición de 1974 del producto modular de los gráficos como una forma de reducir los problemas de isomorfismo de los subgrafos para encontrar camarillas máximas en gráficos. [V74] También demostró una versión más sólida del teorema de Brook que se aplica a la coloración de listas.
A partir de 1976, Vizing dejó de trabajar en la teoría de grafos y en su lugar estudió problemas de programación , [7] solo regresó a la teoría de grafos nuevamente en 1995. [2]
Premios
- Gran Medalla de Plata del Instituto de Matemáticas del Departamento de Siberia de la Academia de Ciencias de Rusia [5]
Publicaciones Seleccionadas
V64. | Vizing, VG (1964), "Sobre una estimación de la clase cromática de un gráfico p ", Diskret. Analiz. (en ruso), 3 : 25–30, MR 0180505 |
V68. | Vizing, VG (1968), "Algunos problemas no resueltos en teoría de grafos", Uspekhi Mat. Nauk (en ruso), 23 (6): 117-134, MR 0240000 |
V74. | Vizing, VG (1974), "Reducción del problema de isomorfismo y entrada isomorfa a la tarea de encontrar la no densidad de un grafo", Proc. 3ra Conf. De toda la Unión Problemas de la cibernética teórica , pág. 124 |
V76. | Vizing, VG (1976), " Coloreaciones de vértices con colores dados", Diskret. Analiz. (en ruso), 29 : 3–10 |
Notas
- ^ "Vizing" puede ser la romanización de la transcripción fonética del apellido alemán Wiesing al ruso.
- ↑ Tanto en Gutin & Toft (2000) como en Soifer (2008) , Vizing menciona que su trabajo fue motivado por el teorema de Shannon. Para el ejemplo del límite inferior del triángulo, consulte, por ejemplo, Colorful Mathematics .
- ^ El nombre completo de esta revista era Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudov . Fue rebautizado como Metody Diskretnogo Analiza en 1980 (nombre que se le dio en Gutin & Toft (2000) ) y descontinuado en 1991 [1] .
- ↑ En Soifer (2008) , Vizing afirma que formuló la conjetura en 1964, pero cuando se publicó en 1968, Behzad había planteado de forma independiente la misma conjetura.
Referencias
- ^ Borodin, OV, Памяти В. Г. Визинга [ En memoria de VG Vizing ] (en ruso), Instituto de Matemáticas de Sobolev , consultado el 10 de marzo de 2018
- ^ a b c d e Gutin, Gregory; Toft, Bjarne (diciembre de 2000), "Entrevista con Vadim G. Vizing" (PDF) , Boletín de la Sociedad Matemática Europea , 38 : 22-23
- ^ Soifer, Alexander (2008), El libro de colorear matemático , Springer-Verlag, ISBN 978-0-387-74640-1. Las páginas 136–137 reproducen una carta de 1995 de Vizing a Soifer sobre la formulación de la conjetura de coloración total, que también incluye algunos detalles biográficos sobre Vizing.
- ^ Vadim G. Vizing en el Proyecto de genealogía de las matemáticas
- ^ a b Mel'nikov, LS (2008), "О семинаре Зыкова в Новосибирске" [Acerca del seminario de Zykov en Novosibirsk] (PDF) , en Kasyanov, VN (ed.), Construcción y optimización de programas paralelos (en ruso), Instituto AP Ershov Sistemas informáticos, págs. 164-173
- ^ Shannon, Claude E. (1949), "Un teorema sobre colorear las líneas de una red", J. Math. Física , 28 : 148-151, MR 0030203.
- ^ Goldberg, Mark (1983), El desarrollo de la combinatoria en la URSS: un breve estudio histórico y matemático , Delphic Associates, Falls Church, VA, p. 35, MR 0757359 ,
Vizing ha cambiado un poco sus intereses de investigación, de la teoría de grafos pura a la teoría de la programación
enlaces externos
- Lista de publicaciones recientes de Vadim Vizing y mathnet.ru