Vadim G. Vizing - Vadim G. Vizing

Vadim Georgievich Vizing ( ryska : Вади́м Гео́ргиевич Визинг , ukrainska : Вадим Георгійович Візінг ; 25 mars 1937-23 augusti 2017) var en sovjetisk och ukrainsk matematiker känd för sina bidrag till grafteorin , och speciellt för Vating's kanter. diagram med maximal grad Δ kan färgas med högst Δ + 1 färger.

Biografi

Vizing föddes i Kiev den 25 mars 1937. Hans mor var halvtysk, och på grund av detta tvingade de sovjetiska myndigheterna sin familj att flytta till Sibirien 1947. Efter att ha avslutat sina grundstudier i matematik vid Tomsk State University 1959, började sin doktorsexamen studier vid Steklov-institutet för matematik i Moskva , om ämnet funktionstillnärmning , men han lämnade 1962 utan att slutföra sin examen. Istället återvände han till Novosibirsk , arbetade 1962 till 1968 vid den ryska vetenskapsakademien där och fick en doktorsexamen. 1966. I Novosibirsk deltog han regelbundet i AA Zykovs seminarium inom grafteori. Efter att ha haft flera ytterligare befattningar flyttade han till Odessa 1974, där han undervisade i matematik under många år vid Academy for Food Technology (ursprungligen känd som Одесский технологический институт пищевой промышленности им. М. В. Ломоносова uppkallad efter Mikhail Lomonosov ").

Forskningsresultat

Resultatet som nu kallas Vizings sats , publicerad 1964 när Vizing arbetade i Novosibirsk, säger att kanterna på valfri graf med högst Δ-kanter per vertex kan färgas med högst Δ + 1-färger. Det är en fortsättning på arbetet av Claude Shannon , som visade att vilken multigraf som helst kan ha sina kanter färgade med högst (3/2) Δ-färger (en tät ram, eftersom en triangel med Δ / 2 kanter per sida kräver så många färger ). Även om Vizings teorem nu är standardmaterial i många läroböcker för grafteorier, hade Vizing svårt att publicera resultatet från början, och hans papper om det visas i en obskur tidskrift, Diskret. Analiz .

Vizing gjorde också andra bidrag till grafteori och graffärgning, inklusive införandet av listfärgning , formuleringen av den totala färggissningen (fortfarande olöst) som anger att kanterna och hörnarna på valfri graf tillsammans kan färgas med högst Δ + 2 färger , Vizings gissningar (även olösta) angående dominansantalet av kartesiska produkter i grafer , och 1974 års definition av den modulära produkten av grafer som ett sätt att minska problem med isomorfism i subgrafen för att hitta maximala klick i grafer. Han bevisade också en starkare version av Brook's teorem som gäller listfärgning.

Från 1976 slutade Vizing arbeta med grafteori och studerade istället problem med schemaläggning och återvände bara till grafteori igen 1995.

Utmärkelser

  • Stor silvermedalj från institutet för matematik vid den sibiriska avdelningen vid den ryska vetenskapsakademin

Valda publikationer

V64. Vizing, VG (1964), "På en uppskattning av en p- bilds kromatiska klass ", Diskret. Analiz. (på ryska), 3 : 25–30, MR   0180505
V68. Vizing, VG (1968), "Några olösta problem i grafteorin", Uspekhi Mat. Nauk (på ryska), 23 (6): 117–134, MR   0240000
V74. Vizing, VG (1974), "Minskning av problemet med isomorfism och isomorf ingång till uppgiften att hitta otätheten i en graf", Proc. 3: e All-Union Conf. Problem med teoretisk cybernetik , s. 124
V76. Vizing, VG (1976), "Vertex färgämnen med givna färger", Diskret. Analiz. (på ryska), 29 : 3–10

Anteckningar

Referenser

externa länkar