Chyťte, Václave
Václav (Washek) Chvátal je emeritním profesorem na katedře počítačových věd a softwarového inženýrství na Concordia University v Montrealu , Quebec , Kanada . Publikoval mnoho prací o teorii grafů, kombinatorice a kombinatorické optimalizaci.
Životopis
Chvátal se narodil v Praze v roce 1946 a matematické vzdělání získal na Univerzitě Karlově v Praze , kde studoval u Zdeňka Hedrlina. Z Československa uprchl v roce 1968, tři dny po sovětské invazi, a dokončil Ph.D. Na podzim roku 1970 získal magisterský titul v matematice z University of Waterloo pod vedením Crispin St. J. A. Nash-Williams. Následně zastával pozice na McGill University ( 1971 a 1978-1986 ) , Stanford University ( 1972 a 1974-1977 ) , University of Montreal ( 1972-1974 a 1977-1978 ) a Rutgers University ( 1986 ) - . až do důchodu
se vrací do Montrealu na kanadskou katedru kombinatorických optimalizačních studií v Concordia ( 2004-2011 ) a kanadskou katedru diskrétních matematických studií ( 2011-2014 ) .
Výzkum
Chwatal se poprvé dozvěděl o teorii grafů v roce 1964 , když našel knihu Clauda Bergého v knihkupectví v Plzni a většina jeho výzkumů se týká teorie grafů :
- Jeho první matematická publikace ve věku 19 let byla o orientovaných grafech, které na sebe nelze zmapovat žádným netriviálním homomorfismem grafů .
- Dalším grafově teoretickým výsledkem Chvátala byla v roce 1970 konstrukce nejmenšího možného grafu bez trojúhelníků, který je jak 4-chromatický, tak 4-regulární graf, nyní známý jako Chvátalův graf.
- V článku z roku 1972 , který vztahoval hamiltonovské cykly ke konektivitě a maximální nezávislé množině velikosti grafu, bylo Chvatalovi přiděleno Erdősovo číslo 1. Zejména pokud existuje s takové, že daný graf je s-vrcholově spojen a není mít (s + 1)-vertex -nezávislou množinu, graf musí být hamiltonovský.
- Chvátal ve svém článku z roku 1973 zavedl pojem stability grafu, tedy míru konektivity grafu, která úzce souvisí s existencí hamiltonovských cyklů. Graf je t-rigidní, pokud pro každé k větší než 1 odstranění méně než tk vrcholů ponechá méně než k spojených komponent ve zbývajícím podgrafu. Například v grafu s hamiltonovským cyklem odstranění jakékoli neprázdné sady vrcholů rozdělí cyklus na nejvýše tolik částí, kolik je odstraněných vrcholů, takže hamiltonovské grafy jsou 1-rigidní. Chwatal předpokládal, že 3/2-rigidní grafy a později také 2-rigidní grafy jsou vždy hamiltonovské; ačkoli novější výzkumníci nalezli protipříklady k těmto domněnkám, zůstává otevřenou otázkou, zda nějaký konstantní odhad stability grafu je dostatečný k zaručení hamiltonianity.
Některé z Chvátalových prací se zabývají rodinami množin nebo ekvivalentně hypergrafy, což je téma již zmíněno v jeho doktorské disertační práci, v níž se také zabýval Ramseyho teorií .
Knihy
- Vašek Chvátal (1983). lineární programování. W. H. Freeman. ISBN 978-0-7167-1587-0 .. Japonský překlad vydal Keigaku Shuppan, Tokio, 1986.
- C. Berge a V. Chvátal (eds.) (1984). Témata o dokonalých grafech. Elsevier. ISBN 978-0-444-86587-8 .
- David L. Applegate; Robert E Bixby; Vašek Chvátal; William J. Cook (2007). Problém cestujícího obchodníka: výpočetní studie. Princeton University Press. ISBN 978-0-691-12993-8 .
- Vašek Chvátal (ed.) (2011). Kombinatorická optimalizace: Metody a aplikace. iOS Press. ISBN 978-1-60750-717-8 .
- Vašek Chvátal (2021). Diskrétní matematická kouzla Paula Erdőse. Jednoduchý úvod. Cambridge University Press. ISBN 978-1-108-92740-6 .
Poznámky
- ↑ 1 2 Databáze českého národního úřadu
- ↑ 1 2 3 Evidence zájmových osob StB (EZO)
Odkazy
Tematické stránky |
|
---|
V bibliografických katalozích |
---|
|
|