Grib, Vaclav
Vaclav (Washek) Chvatal er professor emeritus i afdelingen for datalogi og softwareteknik ved Concordia University i Montreal , Quebec , Canada . Han har udgivet mange artikler om grafteori, kombinatorik og kombinatorisk optimering.
Biografi
Chvátal blev født i Prag i 1946 og modtog sin matematiske uddannelse ved Charles University i Prag , hvor han studerede under Zdeněk Hedrlin. Han flygtede fra Tjekkoslovakiet i 1968, tre dage efter den sovjetiske invasion, og afsluttede sin ph.d. I efteråret 1970 modtog han en kandidatgrad i matematik fra University of Waterloo under tilsyn af Crispin St. J. A. Nash-Williams. Han havde efterfølgende stillinger ved McGill University ( 1971 og 1978-1986 ) , Stanford University ( 1972 og 1974-1977 ) , University of Montreal ( 1972-1974 og 1977-1978 ) og Rutgers University ( 1986 før 1986 ) vender tilbage til Montreal til den canadiske lærestol for kombinatoriske optimeringsstudier ved Concordia ( 2004 - 2011 ) og den canadiske stol for diskrete matematikstudier ( 2011 - 2014 ) indtil pensionering.
Forskning
Chwatal lærte først om grafteori i 1964 , da han fandt en bog af Claude Bergé i en boghandel i Pilsen , og det meste af hans forskning er relateret til grafteori :
- Hans første matematiske publikation i en alder af 19 handlede om rettede grafer, som ikke kan kortlægges på sig selv af nogen ikke-triviel grafhomomorfi .
- Et andet grafteoretisk resultat af Chvatal var konstruktionen i 1970 af den mindst mulige trekantfri graf, der både er en 4-kromatisk og en 4-regulær graf, nu kendt som Chvatal-grafen.
- I et papir fra 1972 , der relaterer Hamiltonske cyklusser til forbindelse og den maksimale uafhængige sætstørrelse af en graf, blev Chvatal tildelt et Erdős-nummer på 1. Især hvis der eksisterer et s, således at den givne graf er s-vertex-forbundet og ikke har en (s + 1)-vertex -uafhængig mængde, skal grafen være Hamiltonsk.
- I et papir fra 1973 introducerede Chvatal begrebet grafstabilitet, et mål for grafforbindelse, der er tæt forbundet med eksistensen af Hamiltonske cyklusser. En graf er t-stiv, hvis, for hver k større end 1, fjernelse af mindre end tk hjørner efterlader færre end k tilsluttede komponenter i den resterende undergraf. For eksempel, i en graf med en Hamiltonsk cyklus, vil en fjernelse af ethvert ikke-tomt sæt hjørner bryde cyklussen i højst lige så mange dele, som der er fjernede hjørner, så Hamiltonske grafer er 1-stive. Chwatal formodede, at 3/2-stive grafer, og senere også 2-stive grafer, altid er Hamiltonske; selv om nyere forskere har fundet modeksempler til disse formodninger, er det stadig et åbent spørgsmål, om et konstant grafstabilitetsestimat er tilstrækkeligt til at garantere Hamiltonianitet.
Nogle af Chvátals arbejde beskæftiger sig med familier af sæt eller tilsvarende hypergrafer, et emne, der allerede er nævnt i hans doktorafhandling, en afhandling, hvor han også studerede Ramsey-teori .
Bøger
- Vašek Chvatal (1983). lineær programmering. W.H. Freeman. ISBN 978-0-7167-1587-0 .. Japansk oversættelse udgivet af Keigaku Shuppan, Tokyo, 1986.
- C. Berge og V. Chvatal (red.) (1984). Emner om perfekte grafer. Elsevier. ISBN 978-0-444-86587-8 .
- David L. Applegate; Robert E Bixby; Vašek Chvatal; William J. Cook (2007). The Travelling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8 .
- Vašek Chvatal (red.) (2011). Kombinatorisk optimering: Metoder og applikationer. iOS Tryk. ISBN 978-1-60750-717-8 .
- Vašek Chvatal (2021). Diskrete matematiske charme af Paul Erdős. En simpel introduktion. Cambridge University Press. ISBN 978-1-108-92740-6 .
Noter
- ↑ 1 2 Database for den tjekkiske nationale myndighed
- ↑ 1 2 3 Beviser zájmových osob StB (EZO)
Links
Tematiske steder |
|
---|
I bibliografiske kataloger |
---|
|
|