Claude Berge - Claude Berge

Claude Jacques Berge (5. června 1926 - 30. června 2002) byl a francouzština matematik, uznávaný jako jeden z moderních zakladatelů společnosti kombinatorika a teorie grafů.

Životopis a profesionální historie

Rodiče Clauda Bergeho byli André Berge a Geneviève Fourcade. André Berge (1902-1995) byl lékař a psychoanalytik, který kromě své profesionální práce vydal několik románů. Byl synem hornického inženýra René Berge a Antoinette Faure. Félix François Faure (1841-1899) byl otcem Antoinette Faure; byl prezidentem Francie v letech 1895 až 1899. André Berge se oženil s Geneviève v roce 1924 a Claude, který je předmětem této biografie, byl druhým z jejich šesti dětí. Jeho pět sourozenců bylo Nicole (nejstarší), Antoine, Philippe, Edith a Patrick. Claude se zúčastnil École des Roches poblíž Verneuil-Sur-Avre asi 110 km západně od Paříže. Tato slavná soukromá škola, kterou založil sociolog Edmond Demolins v roce 1899, přilákala do svého inovativního vzdělávacího programu studenty z celé Francie. V této fázi svého života si Claude nebyl jistý tématem, na které by se měl specializovat. V pozdějším životě řekl:

"Nebyl jsem si úplně jistý, že chci dělat matematiku." Často bylo větší nutkání studovat literaturu. “

Jeho láska k literatuře a dalším nematematickým předmětům ho nikdy neopustila a níže si povíme, jak hráli v jeho životě velkou roli. Rozhodl se však studovat matematiku na pařížské univerzitě. Po udělení prvního stupně pokračoval v doktorském výzkumu, který mu doporučil André Lichnerowicz. Matematické práce začal vydávat v roce 1950. V tomto roce se objevily dva jeho články, krátký referát Sur l'isovalence et la régularité des transformateurs a hlavní 30stránkový referát Sur un nouveau calcul symbolique et ses applications. Symbolický počet, o kterém hovořil v této hlavní práci, je kombinací generujících funkcí a Laplaceových transformací. Poté použil tento symbolický počet na kombinatorickou analýzu, Bernoulliho čísla, diferenční rovnice, diferenciální rovnice a faktory sčítatelnosti. V roce 1951 vydal další dvě krátké práce Sur l'inversion des transformateurs a Sur une théorie ensembliste des jeux alternifs, které oznamovaly různé výsledky, které budou plně diskutovány v jeho práci. V roce 1953 mu byl udělen doktorát za diplomovou práci Sur une théorie ensembliste des jeux alternifs. V této práci zkoumal hry, kde jsou k dispozici dokonalé informace, ve kterých je při každém pohybu možná nekonečné množství možností. Hry nemusí být nutně konečné, je povoleno jejich neomezené pokračování. Berge důkladně analyzoval vlastnosti těchto her. V roce 1953 byl publikován 55stránkový dokument vycházející z jeho diplomové práce se stejným názvem.

Berge se oženil s Jane Gentazovou (narozenou 7. ledna 1925) dne 29. prosince 1952; měli jedno dítě Delphine, narozené 1. března 1964. V roce 1952, před udělením doktorátu, byl Berge jmenován výzkumným asistentem v Centre National de la Recherche Scientifique. V roce 1957 pobýval ve Spojených státech jako hostující profesor na Princetonské univerzitě. Zúčastnil se tam výzkumného ekonomického projektu, který byl na základě smlouvy s Úřadem pro námořní výzkum. Zatímco v Princetonu se ujal práce, která byla prezentována v příspěvku Dvě věty v teorii grafů publikovaném ve sborníku Národní akademie věd Spojených států amerických. To byl jeden z jeho prvních článků o teorii grafů, jeho dřívější práce byla o teorii her a kombinatorice. V této době psal svou slavnou knihu Théorie des graphes et ses applications and a právě vydal knihu o teorii her Théorie générale des jeux à n personnes Ⓣ (1957). Po návratu do Francie ze Spojených států nastoupila Berge na pozici ředitele výzkumu v Centre national de la recherche scientifique. Také v roce 1957 byl jmenován profesorem na Statistickém institutu pařížské univerzity. Aplikace Théorie des graphes et ses Ⓣ vyšla v roce 1958 a pozoruhodně v následujícím roce vyšla jeho třetí kniha Espaces topologiques, fonctions multivoques Ⓣ. Pro matematika, kterému je něco přes třicet, je vydat tři hlavní knihy za tolik let, což je opravdu vynikající úspěch.

V roce 1994 napsal Berge pro Oulipa „matematickou“ záhadu vraždy. V této povídce Kdo zabil vévodu z Densmoru (1995) byl vévoda z Densmoru zavražděn jednou z jeho šesti milenek a Holmes a Watson jsou povoláni k vyřešení případu. Watson je poslán Holmesem na vévodský hrad, ale po jeho návratu jsou informace, které sděluje Holmesovi, velmi zmatené. Holmes využívá informace, které mu Watson dává, ke konstrukci grafu. .^[1]

Počínaje rokem 1952 působil jako asistent výzkumu na Francouzské národní centrum pro vědecký výzkum (CNRS) a od roku 1957 do roku 1964 působil jako profesor na statistickém ústavu University of Paris. V letech 1965 až 1967 řídil Mezinárodní výpočetní středisko v Římě. Byl také spojován s Center d'Analyse et de Mathématique Sociales (CAMS), výzkumným centrem École des hautes études en sciences sociales. Zastával hostující pozice v Univerzita Princeton v roce 1957, Pennsylvania State University v roce 1968 a Newyorská univerzita v roce 1985 a byl častým návštěvníkem Indický statistický úřad, Kalkata.^[2][1]

Období kolem roku 1960 se zdá být pro Berge obzvláště důležité a plodné. Prostřednictvím knihy Th´eorie des graphes et ses applications si vytvořil matematické jméno. V roce 1959 se zúčastnil první konference o teorii grafů v maďarském Dobogok˝u a setkal se s maďarskými teoretiky grafů. Publikoval průzkumnou práci o zbarvení grafů. Představila myšlenky, které brzy vedly k dokonalým grafům. V březnu 1960 o tom hovořil na schůzce ve východním Německu v Halle. V listopadu téhož roku byl jedním z deseti zakládajících členů OuLiPo (Ouvroir de Litt´erature Potentiel). A v roce 1961 zahájil se svým přítelem a kolegou Marcem Sch¨utzenbergerem iniciativu S´eminaire sur les probl`emes combineatoires de l’Universit´e de Paris (která se později stala Equipe combineatoire du CNRS). Zároveň Berge dosáhl úspěchu jako sochař.

V roce 1994 napsal Berge pro Oulipa „matematickou“ záhadu vraždy. V této povídce Kdo zabil vévodu z Densmoru (1995) byl vévoda z Densmoru zavražděn jednou z jeho šesti milenek a Holmes a Watson jsou povoláni k vyřešení případu. Watson je poslán Holmesem na vévodský hrad, ale po jeho návratu jsou informace, které sděluje Holmesovi, velmi zmatené. Holmes využívá informace, které mu dává Watson, ke konstrukci grafu. Poté použije teorém o Györgyi Hajósovi na graf, který vytváří jméno vraha. Další chytré příspěvky Berge Oulipovi jsou popsány v [6].

Dalším zájmem Berge bylo umění a sochařství. Ve své knize Sculptures multipètres (1962) popsal své rané sochy vyrobené částečně z kamenů nalezených v řece Seině. Bjarne Toft píše [21]: -

"V našem moderním každodenním životě jsme obklopeni a bombardováni (příliš) krásnými, bezchybnými obrázky, sochami a vzory." V tomto proudu nás sochy Clauda Bergeho upoutají svou autenticitou a poctivostí. Nepředstírají, že jsou víc než oni. Berge opět zachytí něco obecného a zásadního, jak to udělal ve své matematice. Sochy se na první pohled mohou zdát vtipné a určitě mají i humornou stránku. Ale mají silné osobnosti v jejich jedinečném stylu - budete se jim líbit, když se na ně budete neustále dívat - to, zda by s nimi někdo mohl žít, kdyby ožili, je jiná věc! “

Matematické příspěvky

Berge napsal pět knih herní teorie (1957), teorie grafů a její aplikace (1958), topologické prostory (1959), principy kombinatoriky (1968) a hypergrafy (1970), přičemž každý je přeložen do několika jazyků. Tyto knihy pomohly vyvrátit předměty teorie grafů a kombinatoriky z dobré pověsti zdůrazněním úspěšných praktických aplikací předmětů.^[3] Zvláště si ho pamatují dva dohady perfektní grafy které vytvořil na začátku 60. let, ale byly prokázány až výrazně později:

• Graf je dokonalý, právě když je doplněk je perfektní, prokázáno László Lovász v roce 1972 a nyní známý jako dokonalá věta o grafu,^[4] a
• Graf je dokonalý právě tehdy, pokud ani on, ani jeho doplněk neobsahuje indukovaný cyklus liché délky nejméně pět, prokázáno Maria Chudnovsky, Neil Robertson, Paul Seymour, a Robin Thomas v práci publikované v roce 2006 a nyní známé jako silná dokonalá věta o grafu.^[5]

Hry byly po celý život vášní Clauda Bergeho, ať už jejich hraní - jako v oblíbených jako šachy, vrhcáby a hex - nebo zkoumání dalších teoretických aspektů. Tato vášeň řídila jeho zájmy v matematice. Teorii hry začal psát již v roce 1951, rok strávil na Institutu pro pokročilé v Princetonu v roce 1957 a ve stejném roce vytvořil svou první významnou knihu Th´eorieg´en´erale des jeux `a n personnes [1]. Zde se setkáváme nejen se jmény jako von Neumann a Nash, jak by se dalo očekávat, ale také se jmény jako K¨onig, Oreand Richardson. Kniha skutečně obsahuje mnoho teorií grafů, konkrétně teorii grafů užitečných pro teorii her. Obsahuje také mnoho topologie, jmenovitě topologie relevantní pro teorii her. Bylo tedy přirozené, že Berge na tuto práci rychle navázal dvěma většími objemy, Th´eorie des graphes et ses applications [2] a Espaces topologiques, fonctions multivoques [3]. Th´eorie des graphes et sesapplications [2] je mistrovské dílo s jedinečnou kombinací obecné teorie, vět - snadných a obtížných, důkazů, příkladů, aplikací, diagramů. Jedná se spíše o osobní manifest teorie grafů než o úplný popis, jak se o to pokusil Kbookonig v knize [31]. Bylo by zajímavým projektem porovnat první dvě dřívější knihy o teorii grafů, autorů Sainte-Lagu¨e [34] a K¨onig [31], s knihou Berge [2]. Je jasné, že Bergeova kniha je především zábavnější a hravější než K¨onigova. Řídí se chutí Bergeho a může dobře označovat „svádění do teorie grafů“ (použít slova Rota z úvodního anglického překladu [13]). Mezi hlavní témata v [2] patří faktorizace, párování a střídání cest. Zde se Berge opírá o základní dokument Gallai [25]. Tibor Gallai je jedním z největších teoretiků grafů - je to někdy přehlédnuto - ale ne Berge. Gallai byl mezi prvními, kteří zdůrazňovali věty o maximu a LP-dualitě v kombinatorice.

On je také známý pro jeho maximální věta v optimalizaci a pro Bergeovo lemma, který uvádí, že shoda M v grafu G je maximální právě tehdy, pokud existuje v G Ne rozšiřující cesta s ohledem na M.

Umění

Kromě matematiky měl Claude Berge rád literaturu, sochařství a umění. Berge spoluzaložil francouzskou literární skupinu Oulipo s romanopisci a dalšími matematiky v roce 1960 za účelem vytvoření nových forem literatury. V této asociaci napsal záhadnou vraždu na základě matematické věty: Kdo zabil vévodu z Densmoru? V adaptaci tohoto příběhu je vévoda z Densmoru zabit výbuchem. O 10 let později jsou povoláni Sherlock Holmes a Watson, aby vyšetřili tento nevyřešený případ. S využitím svědectví sedmi vévodových bývalých manželek a jeho znalostí o intervalové grafy, Holmes je schopen určit, který z nich provedl několikanásobné návštěvy vévody a byl schopen umístit bombu.^[6][7]

Ceny a vyznamenání

Berge vyhrál Zlatá medaile EURO z Asociace evropských společností pro operační výzkum v roce 1989,^[1][8] a (s Ronald Graham ) inauguračníEulerova medaile z Ústav kombinatoriky a jeho aplikací v roce 1993.^[1]

Recenze jeho knih

Recenze: Frank Harary.

The American Mathematical Monthly 70 (1) (1963), 106-107.

Toto je anglický překlad „Théorie des graphes et ses applications,“ Dunod, Paříž, 1958. Blahopřeji Alison Doig z London School of Economics and Political Science k nejkompetentnější překladatelské práci. Občas jsou patrné kulturní rozdíly mezi Francouzi a Brity, jako v úvodu, kde se „II est tres remarquable ...“ překládá: „Je to záležitost společného pozorování ...“ (že různé disciplíny často používají analogické věty). Francouzskou knihu recenzoval R A Good v The American Mathematical Monthly 68 (1961) 76-77. První a poslední věta Goodova přehledu uvádějí: „Chapadla teorie grafů se neustále zvětšují a pronikají hlouběji do mnoha fází matematiky. Celkově vzato v této knize máme aktuální výklad, jeden z vývojářů sám, zajímavé teorie schopné zvládnout fascinující potpourri situací. “

V naší recenzi francouzské knihy v Mathematical Reviews 21 (1960), 309, jsme si všimli: „Toto je druhá kniha o teorii grafů, která kdy byla napsána. Předchozí kniha je již klasická: Denes König, Theorie der endlichen und unendlichen Graphen "(Akademische Verlag, Leipzig, 1936; Chelsea Publishing Company, New York, 1950). Existuje však několik knih o kombinatorické analýze a topologii, které obsahují kapitolu o teorii grafů. V poslední době došlo k obnovení zájmu o teorii i aplikace grafů, odkud autor získá název své knihy. Kniha obsahuje značný počet nových výsledků v teorii grafů, které byly objeveny od knihy Denese Königa, a proto jsou velmi vítaným doplňkem matematické literatury. “ Nejnápadnější změnou je, že přílohy III, IV a V byly v překladu vynechány. Příloha IV v původní knize uvádí 14 nevyřešených problémů. Z nich byl problém 4 nedávno vyřešen Chong-Yun Chao, problém 11 byl vyřešen v našem předchozím přehledu a Problémy 12-14 žádají čtenáře, aby urovnal Four-Color-Conjecture. Přesnost odkazů byla vylepšena. Některé z nich bohužel stále odkazují na několik článků. Zahrnutí rejstříku autorů do tohoto anglického překladu by bylo velmi vítané. V současné době jsou existující nebo oznámené knihy o teorii grafů následující: 1. Denes König, originál v němčině, přeložený do angličtiny. 2. Claude Berge, originál ve francouzštině, anglický překlad s tímto přezkoumáním. 3. 0ystein Ore, Theory of Graphs, American Mathematical Society Colloquium Publications 38, 1962. 4. 0ystein Ore, Graphs and their usage, coming coming in the School Mathematics Study Group (SMSG) series. Kromě toho se několik dalších teoretiků grafů aktivně zabývá psaním vlastních verzí základů, základů a prvků teorie grafů. Je třeba doufat, že se všemi těmito příspěvky do oboru, stejně jako s knihami o teorii grafů napsaných primárně pro publikum elektrotechniků, provozních výzkumníků nebo sociálních vědců, se dva vývojové trendy zvýrazní: (i) každý vědec, který považuje za vhodné použít strukturální nebo kombinatorické koncepty ve svém vlastním výzkumu, nebude mít povinnost znovu objevit teorii grafů sám pro sebe, ab initio. (ii) tato elegantní teorie se svými aplikacemi v matematice na topologii, logiku, algebru a kombinatorickou analýzu se nakonec stane vysokoškolským kurzem na většině moderních univerzit.

Recenze: Rufus Isaacs.

Operations Research 7 (5) (1959), 681-682.

Pojem graf, který je předmětem této knihy, nemá běžnou konotaci zápletky nebo křivky, ale odkazuje na ustálené, ale esoterické matematické použití. Graf je sada bodů, jejichž určité páry jsou spojeny oblouky. Tyto oblouky mohou nebo nemusí být orientovány, to znamená, že mají přidružený určitý směr od jednoho koncového bodu k druhému. Možná nový název, který by rozptýlil zmatek, by byl vhodný. Nabízíme teorii vazeb. Geometrický aspekt výše uvedené definice samozřejmě není jádrem věci; grafy mohou být symbolickými diagramy nejrůznějších situací. Body mohou představovat téměř jakýkoli druh objektu a oblouky téměř jakýkoli druh vzájemného vztahu. Měli bychom tedy očekávat, že téma bude oplývat různými aplikacemi, a Bergeova kniha to dělá. Při procházení svazkem je člověk fascinován pestrou řadou ilustrací a rozmanité příklady svědčí o velmi eklektickém obsahu. Analytik výzkumu zjistí, že ho hodně okouzlí a poučí. Dosud standardní prací byla „Theorie der endlichen und unendlichen Graphen“ od Denese Königa (Lipsko, 1936). Jeden si zde přečetl odvětví klasické matematiky, které udeřilo mnoha směry, ale do několika proniklo hluboce, drobné úsilí mnoha významných matematiků. Pohled na předmět lze získat pohledem na ukázku více proslulých problémů. Eulerova čára [pojmenovaná podle Leonharda Eulera] je čára, která pokrývá každý oblouk grafu a lze ji kreslit bez zvedání tužky nebo zpětného pohybu. Vychází ze slavného problému sedmi mostů Königsbergu, jak je popsán ve většině dějin matematiky, a je populárně popisován jako výchozí bod topologie. Hamiltonova linie [pojmenovaná podle Williama Rowana Hamiltona] je téměř dvojí koncept: nemusí pokrývat všechny oblouky, ale musí projít každý vrchol jednou a pouze jednou. V obou případech je problém zjistit podmínky, za kterých je možné nakreslit příslušnou čáru. Eulerův problém je poměrně snadný, ale Hamiltonův problém stále není vyřešen. Jedním z nejslavnějších ze všech nevyřešených problémů je zbarvení mapy: ukázat, že k vybarvení libovolné rovinné mapy postačují čtyři barvy, takže sousední země mají vždy výrazný odstín. Teorií grafů se stává otázka, pokud necháme každý vrchol představovat zemi a spojíme je obloukem, když mají odpovídající země vzájemnou hranici. Krém takových starších problémů je elegantně zpracován v Bergeově knize. Ale spolu s nimi jsou aktuální pokroky v předmětu. Žák operačního výzkumu pozná mnoho hmotného a mnoho jmen; dobrý podíl je americký. Například je zde kapitola o dopravních sítích. Zahrnuje algoritmy Ford-Fulkerson [pojmenované podle Lestera Randolpha Forda (1886-1967), Delberta Ray Fulkersona (1924-1976)] a věty Hoffmana [Alan Jerome Hoffman (1924-)] a Gale [David Gale (1921) -2008)]. Jako obvykle jsou aplikace neuvěřitelně rozmanité. Kromě otázek optimalizace dopravy a směrování jsou stejné techniky přizpůsobeny problému minimálního pokrytí, některým kombinatorickým ukázkám, problémům v teorii množin a lineárnímu programování. Metody pokračují v řešení problémů v některých následujících kapitolách; v jednom o spojkách najdeme problém typický pro aplikovaný rozsah této teorie. V takzvaných jednoduchých grafech jsou vrcholy rozděleny do dvou sad, takže všechny oblouky spojují pouze členy jedné sady s body druhé. Spojka je podmnožinou těchto oblouků, přičemž žádné dva nemají společný koncový bod. Problém: najít maximální propojení. Co je to aplikace? Nechť jedna ze dvou sad vrcholů výše představuje množinu pracovníků a druhou úkoly, které je třeba udělat. Spojovací oblouk se nakreslí, když je pracovník schopen tuto úlohu splnit. Pak maximální vazba odpovídá maximálnímu schématu přiřazování pracovníků k vhodným pracovním místům. Druhá, ale triviální aplikace si zaslouží být citována z méně technických důvodů:

"Dans un collège mixte américain, toute jeune fille a mm" boy-friends, "et tout garçon a mm" girl-friends "; Est-il possible de faire danser simultanément chaque jeune fille avec un de ses boy-friends et chaque garçon avec une de ses girl-friends? “

Existuje kapitola o teorii her (autor k tomuto tématu vytvořil samostatnou monografii); jiní se zabývají maticemi a stromy. K dispozici je dodatek o teorii elektrických obvodů a některých souvisejících neelektrických problémech. Vždy existuje stimulující rozmanitost. V kapitole nazvané Facteurs například běží tři po sobě jdoucí příklady: Cesta kolem světa (William Rowan Hamilton); Rytířská prohlídka šachovnice (Leonhard Euler); a - rychlé ponoření se do moderní doby a problémy s řadou front - Bookbinding Problem [Selmer Martin Johnson (1916-1996)]. Provozní analytik bude těžit z této práce (kromě toho, že si užije) při získávání arzenálu nových a nápaditých technik. I když by nikdy neměl příležitost je použít, jeho důvtip nelze vyostřit kvůli pozoruhodnému způsobu, jak jsou zdánlivě nesourodé koncepty propojeny společnými základními myšlenkami.

Vybrané publikace

Hlavní matematické práce

(Poznámka: Hrubý anglický překlad v závorkách)

• Théorie générale des jeux à n personnes (General theory of games for n players), 1957, trans. v ruštině, 1961
• Théorie des graphes et ses applications, Wiley, 1958, trans. Angličtina, ruština, španělština, rumunština, čínština. Anglický překlad: Teorie grafů a její aplikace, Wiley, 1964
• Topologie jazyka Espaces, mnohoznačnosti písem, 1959, trans. v angličtině, 1963. Anglický překlad Topologické prostory: Včetně zpracování vícehodnotových funkcí, vektorových prostorů a konvexity, Dover Books, 2010.
• Programy, doprava a přeprava, s A. Ghouila-Houri, Wiley, 1962, trans. Angličtina, španělština, němčina, čínština. Anglický překlad: Programování, hry a dopravní sítě, Wiley, 1965
• Grafy parfaits (Perfektní grafy), 1963
• Principes de Combinatoire, Wiley, 1968. Anglický překlad: Principy kombinatoriky, Academic Press, 1971^[9]
• Grafy a hypergrafy, v letech 1969 a 1970, trans. v angličtině, japonštině. Anglický překlad: Grafy a hypergrafy, North-Holland Publishing Company, 1973.
• Hypergrafy. Combinatoires des ensembles finis (Hypergraphs. Combinatorial finite sets), Gauthier-Villars, 1987, trans. Angličtina

Literární dílo

• Sochy Multipètres, 1961
• La Reine Aztèque (Aztec Queen), 1983
• Qui a tué le Duc de Densmore? (Kdo zabil vévodu z Densmoru?) 1994
• Raymond Queneau et la combineatoire (Raymond Queneau a kombinatorika), 1997

Reference

externí odkazy

• Claude Berge na Matematický genealogický projekt
• Fotografie Clauda Bergeho
• Matematická díla Clauda Bergeho
• Stránka Claude Berge na University of Montreal (G. Hahn)
• Nekrolog autor: S. Bhogle
• Nekrolog podle V. Chvatal
• Tvorba a rekreace: Pocta paměti Clauda Bergeho v diskrétní matematice, svazek 306, 6. října 2006
• Chvátal, Vašek (15. března 1997), „Ve chvále Clauda Bergeho“, Diskrétní matematika, 165-166: 3–9, doi:10.1016 / s0012-365x (96) 00156-2