Frank Harary - Frank Harary
Frank Harary | |
|---|---|
 Frank Harary (vasemmalla) ja Klaus Wagner elokuvassa Oberwolfach, 1972
| |
| Syntynyt |
11. maaliskuuta 1921 |
| Kuollut | 4. tammikuuta 2005 (83 -vuotias)
Las Cruces, New Mexico , Yhdysvallat
|
| Kansalaisuus | amerikkalainen |
| Alma mater |
Brooklyn College University of California, Berkeley |
| Tunnettu |
Goldner – Harary-kuvaaja Hararyn yleinen tic-tac-toe |
| Tieteellinen ura | |
| Kentät | Matematiikka |
| Toimielimet |
Michiganin yliopisto New Mexico State University |
| Tohtorin neuvonantaja | Alfred L.Foster |
Frank Harary (11. maaliskuuta 1921 - 4. tammikuuta 2005) oli yhdysvaltalainen matemaatikko , joka oli erikoistunut graafiteoriaan . Hänet tunnustettiin laajalti yhdeksi modernin graafiteorian "isistä". Harary oli selkeän esittelyn mestari ja yhdessä monien jatko -opiskelijoidensa kanssa standardisoi kaavioiden terminologian. Hän laajensi tämän alan ulottuvuutta kattamaan fysiikan, psykologian, sosiologian ja jopa antropologian. Hyvin huumorintajuisena lahjakas Harary haastoi ja viihdytti yleisöä kaikilla matemaattisen hienostuneisuuden tasoilla. Erityinen temppu, jota hän käytti, oli muuttaa lauseet peleiksi - esimerkiksi opiskelijat yrittivät lisätä punaisia reunoja kuuden kärjen kuvaajaan punaisen kolmion luomiseksi, kun taas toinen opiskelijaryhmä yritti lisätä reunoja sinisen kolmion luomiseksi (ja kaavion jokaisen reunan on oltava joko sininen tai punainen). Ystäviä ja tuntemattomia koskevan lauseen vuoksi yhden tai toisen joukkueen olisi voitettava.
Elämäkerta
Frank Harary syntyi New Yorkissa , Syyriasta ja Venäjältä tulevien juutalaisten maahanmuuttajien perheen vanhin lapsi . Hän suoritti kandidaatin ja maisterin tutkinnot Brooklyn Collegessa vuonna 1941 ja 1945 sekä Ph.D. , Jossa ohjaaja Alfred L. Foster , mistä University of California, Berkeley vuonna 1948.
Ennen opettajauransa hänestä tuli tutkimusavustaja Michiganin yliopiston yhteiskuntatutkimusinstituutissa .
Hararyn ensimmäinen julkaisu "Atomic Boolean-like rings with finite radical" kävi paljon vaivaa päästäkseen Duke Mathematical Journaliin vuonna 1950. Tämä artikkeli toimitettiin ensin American Mathematical Societyille marraskuussa 1948 ja lähetettiin sitten Duke Mathematicalille Lehteä, jossa sitä tarkistettiin kolme kertaa ennen kuin se lopulta julkaistiin kaksi vuotta sen alkuperäisen toimittamisen jälkeen. Harary aloitti opettajauransa Michiganin yliopistossa vuonna 1953, jossa hän oli ensin apulaisprofessori, sitten vuonna 1959 apulaisprofessori ja vuonna 1964 nimitettiin matematiikan professoriksi .
Vuodesta 1987 hän oli professori (ja erottaa emeritusprofessori ) tietojenkäsittelytieteen osaston New Mexico State University in Las Cruces . Hän oli yksi Journal of Combinatorial Theory ja Journal of Graph Theory perustajista .
Vuonna 1949 Harary julkaisi Solmujen algebrallisesta rakenteesta . Pian tämän julkaisun jälkeen vuonna 1953 Harary julkaisi ensimmäisen kirjansa (yhdessä George Uhlenbeckin kanssa) Husimi -puiden määrästä . Tämän tekstin jälkeen hän alkoi rakentaa maailmanlaajuista mainetta työstään graafiteoriassa. Vuonna 1965 ensimmäisen kirjansa Rakenteelliset mallit: Johdatus teorian suunnattuja graafeja julkaistiin, ja loput elämästään hänen kiinnostuksensa olisi alalla Graafiteoria .
Aloitettuaan kuvaajateoriansa noin vuonna 1965, Harary alkoi ostaa kiinteistöjä Ann Arborista täydentääkseen perheensä tuloja. Harary ja hänen vaimonsa Jayne saivat kuusi yhteistä lasta, Miriam, Natalie, Judith, Thomas, Joel ja Chaya.
Vuosina 1973–2007 Harary kirjoitti yhdessä viisi muuta kirjaa, joista jokainen oli graafiteorian alalla. Ennen kuolemaansa Harary matkusti ympäri maailmaa tutkien ja julkaisemalla yli 800 artikkelia (noin 300 eri tekijän kanssa), matemaattisissa aikakauslehdissä ja muissa tieteellisissä julkaisuissa enemmän kuin kukaan muu matemaatikko kuin Paul Erdos. Harary kirjoitti, että hän luennoi 166 eri kaupungissa ympäri Yhdysvaltoja ja noin 274 kaupungissa yli 80 eri maassa. Harary oli erityisen ylpeä siitä, että hän oli pitänyt luentoja kaupungeissa ympäri maailmaa, joka alkoi aakkosten jokaisella kirjaimella, myös "X", kun hän matkusti Xanteniin , Saksaan. Hararyllä oli myös utelias rooli palkitussa elokuvassa Good Will Hunting . Elokuva esitti kaavoja, jotka hän oli julkaissut puiden laskemisesta, joiden piti olla pirullisen vaikeita.
Vuonna 1986 65 -vuotiaana Harary jäi eläkkeelle professuuristaan Michiganin yliopistossa. Harary ei kuitenkaan suhtautunut eläkkeelle kevyesti eläkkeelle jäämisen jälkeen Harary nimitettiin arvostetuksi tietojenkäsittelytieteen professoriksi New Mexicon osavaltion yliopistossa Las Crucesissa. Hän toimi tässä tehtävässä kuolemaansa asti vuonna 2005. Samana vuonna eläkkeelle siirtymisestä Harary tehtiin Intian kansallisen tiedeakatemian kunniajäseneksi, hän toimi myös toimittajana noin 20 eri lehdessä, jotka keskittyivät pääasiassa graafiteoriaan ja yhdistelmäteoriaan. . Hänen eläkkeelle jäämisensä jälkeen Harary valittiin Kalkuttan matemaattisen seuran ja Etelä -Afrikan matemaattiseuran kunniajäseneksi.
Hän kuoli Memorial Medical Center in Las Cruces, New Mexico . Hänen kuolemansa aikaan Las Crucesissa muut tietojenkäsittelytieteen osaston jäsenet tunsivat menetyksen suurelle mielelle, joka kerran työskenteli heidän vieressään. Tietojenkäsittelytieteen osaston johtaja Hararyn kuoleman aikaan Desh Ranjan sanoi näin: "Tohtori Harary oli todellinen tutkija, jolla oli aito rakkaus graafiteoriaan, joka oli loputon uusien löytöjen, kauneuden, uteliaisuuden, yllätysten lähde ja iloa hänestä elämänsä loppuun asti. "
Matematiikka
Hararyn työ graafiteoriassa oli monipuolista. Jotkut häntä kiinnostavat aiheet olivat:
- Kaavio laskentaa , eli laskenta kuvaajat tietyn laatuaan. Hän kirjoitti aiheesta kirjan (Harary ja Palmer 1973). Suurin ongelma on se, että kahta isomorfista kuvaajaa ei tule laskea kahdesti; näin ollen on sovellettava Pólyan teoriaa laskemisesta ryhmätoiminnan alla. Harary oli asiantuntija tässä asiassa.
- Signeeratut kaaviot . Harary keksi tämän graafiteorian haaran, joka kasvoi teoreettisen sosiaalipsykologian ongelmasta, jota tutkivat psykologi Dorwin Cartwright ja Harary.
- Graafiteorian sovelluksia monilla aloilla, erityisesti yhteiskuntatieteissä, kuten tasapainoteoria ja turnausteoria . Harary oli John Wileyn ensimmäisen e-kirjan , Graph Theory and Geography, kirjoittaja .
Hararyn kirjoittamien yli 700 tieteellisen artikkelin joukosta kaksi kirjoitettiin Paul Erdősin kanssa , jolloin Hararyn Erdős-luku oli 1. Hän luennoi laajasti ja piti aakkosjärjestyksessä kaupunkeja, joissa hän puhui.
Hararyn tunnetuin klassikkokirja Graph Theory julkaistiin vuonna 1969 ja tarjosi käytännön johdannon kuvaajan teoriaan. On ilmeistä, että Harary keskittyi tässä kirjassa ja muiden julkaisujensa joukossa graafin teorian monipuoliseen ja monipuoliseen soveltamiseen muilla matematiikan, fysiikan ja monilla muilla aloilla. Ote esipuheen Graafiteoria, Harary toteaa ...
" ... graafisten teorioiden sovelluksia on joillekin fysiikan, kemian, viestintätieteen, tietotekniikan, sähkö- ja maanrakennustekniikan, arkkitehtuurin, operatiivisen tutkimuksen, genetiikan, psykologian, sosiologian, taloustieteen, antropologian ja kielitieteen aloille. "
Harary alkoi nopeasti edistää tutkimukseen perustuvaa oppimista tekstiensä kautta, mikä ilmenee viittaamalla Mooren menetelmän perinteeseen . Harary teki monia ainutlaatuisia panoksia graafiteoriaan, kun hän tutki yhä useampia eri tutkimusaloja ja yritti onnistuneesti yhdistää ne kaavioteoriaan. Hararyn klassinen kirja Graph Theory alkaa antamalla lukijalle suuren osan vaadittavista perusgraafien tiedoista ja sukeltaa sitten suoraan todistamaan graafiteorian sisällön monimuotoisuuden. Jotkut muut matemaattiset kentät, jotka Harary liittyy suoraan kirjassaan graafiteoriaan, alkavat ilmestyä luvun 13 ympärille. Näitä aiheita ovat lineaarinen algebra ja abstrakti algebra .
Puu neliöjuuri
Yksi motivaatio graafiteorian tutkimukselle on sen soveltaminen Jacob L. Morenon kuvaamiin sosiogrammeihin . Esimerkiksi Leon Festinger käytti sosiogrammin vierekkäismatriisia . Festinger tunnisti graafiteorian klikin sosiaalisen klikin kanssa ja tutki ryhmien vierekkäismatriisin kuution diagonaalin klikkien havaitsemiseksi. Harary liittyi Ian Rossiin parantaakseen Festingerin klikin havaitsemista.
Viereisyysmatriisin valtuuksien hyväksyminen sai Hararyn ja Rossin huomaamaan, että täydellinen kuvaaja voidaan saada puun vierekkäismatriisin neliöstä . Luottaen tutkimukseensa klikkien havaitsemisesta he kuvailivat kuvaajaluokkaa, jonka vierekkäismatriisi on puun vierekkäismatriisin neliö.
- Jos kuvaaja G on puun neliö, sillä on ainutlaatuinen puun neliöjuuri
- Jotkut sanastot, jotka ovat tarpeen tämän todistuksen ja tässä käytettyjen menetelmien ymmärtämiseksi, ovat Hararyn puun neliössä: (Cliqual, unicliqual, multicliqual, cocliqual, naapuruus, naapuruus, leikkauspiste, lohko)
- Kuinka määrittää, onko jokin kuvaaja G puun neliö .
- Jos kuvaaja G on täydellinen tai täyttää seuraavat 5 ominaisuutta, niin G = T 2
- (i) Jokainen G: n piste on naapurimainen ja G on yhteydessä.
- (ii) Jos kaksi klikkiä kohtaavat vain yhdessä pisteessä b, on olemassa kolmas klikki, jonka kanssa he jakavat b ja täsmälleen toinen piste.
- (iii) Klikkien ja G: n moniklikalisten pisteiden b välillä on 1-1 vastaavuus siten, että b: tä vastaava klikki C (b) sisältää täsmälleen yhtä moniklikalisia pisteitä kuin b: n sisältävien klikkien määrä.
- (iv) Kaksi klikkiä ei leikkaa enempää kuin kaksi pistettä.
- (v) Kahdessa pisteessä kohtaavien klikkiparien määrä on yksi vähemmän kuin klikkien määrä.
- Algoritmi kaavion G puun neliöjuuren löytämiseksi.
- Vaihe 1: Etsi kaikki G: n klikit.
- Vaihe 2: Olkoon G: n napsautukset C 1 , ..., C n , ja harkitse kokoelmaa moniklikalisia pisteitä b 1 , ..., b n, jotka vastaavat näitä napsautuksia ehdon iii mukaisesti. Tämän kokoelman elementit ovat T: n ei -päätepisteet. Etsi kaikki n -napsautusten parilliset leikkauspisteet ja muodosta kuvaaja S yhdistämällä pisteet b i ja b j suoralla, jos ja vain jos vastaavat napsautukset C i ja C j leikkaavat kahdessa pisteessä. S on sitten puu ehdolla v.
- Vaihe 3: Kunkin nurkkakunta C i G, olkoon n i on määrä unicliqual pistettä. Liitä vaiheessa 2 saatuun puuhun S, liitä n i päätepistettä b i: hen ja hanki etsimämme puu T.
Kun meillä on kyseinen puu, voimme luoda puulle T vierekkäismatriisin ja tarkistaa, että se todellakin on oikea puu, jota etsimme. T: n vierekkäismatriisin neliöimisen pitäisi tuottaa kuvaajan vierekkäismatriisi, joka on isomorfinen kuvaajalle G, jolla aloitimme. Todennäköisesti yksinkertaisin tapa havaita tämä lause toiminnassa on tarkkailla tapausta, jonka Harary mainitsee puun aukiolla. Tarkasteltava esimerkki kuvaa erityisesti puuta, joka vastaa K 5: n kaaviota
" Tarkastellaan puuta, joka koostuu yhdestä pisteestä liitettynä kaikkiin muihin. Kun puu on neliö, tulos on täydellinen kaavio. Haluamme havainnollistaa ... T 2 K 5 "
Kun neliöidään aiemmin mainitun puun vierekkäismatriisi, voimme havaita, että tämä lause pitää itse asiassa paikkansa. Voimme myös havaita, että tämä malli puun asettamisesta, jossa "yksi piste on liitetty kaikkiin muihin", tuottaa aina oikean puun kaikille täydellisille kaavioille.
Bibliografia
- 1965: (Robert Z. Normanin ja Dorwin Cartwrightin kanssa), Structural Models: An Introduction to the Theory of Directed Graphs . New York: Wiley MR 0184874
- 1967: Graafiteoria ja teoreettinen fysiikka , Academic Press MR 0232694
- 1969: Graafiteoria , Addison-Wesley MR 0256911
- 1971: (toimittaja Herbert Wilfin kanssa ) Mathematical Aspects of Electrical Networks Analysis , SIAM-AMS Proceedings, Volume 3, American Mathematical Society MR 0329788
- 1973: (toimittaja) New Directions in the Theory of Graphs: Proceedings of the 1971 Ann Arbor Conference on Graph Theory , Michiganin yliopisto, Academic Press. MR 0340065
- 1973: (Edgar M. Palmerin kanssa) Graphical Enumeration Academic Press MR 0357214
- 1979: (toimittaja) Graph Theoryn aiheita , New Yorkin tiedeakatemia MR 557879
- 1984: (Per Hagen kanssa) Rakennemallit antropologiassa , Cambridge Studies in Social and Cultural Anthropology, Cambridge University Press MR 0738630
- 1990: (Fred Buckleyn kanssa) Etäisyys kaavioissa , Perseus Press MR 1045632
- 1991: (Per Hagen kanssa) Vaihto Oseaniassa: Graph Theoretic Analysis , Oxford Studies in Social and Cultural Anthropology, Oxford University Press .
- 2002: (Sandra Lach Arlinghaus & William C.Arlinghaus) Kaavion teoria ja maantiede: interaktiivinen e-kirja , John Wiley and Sons MR 1936840
- 2007: (Per Hagen kanssa) Island Networks: Communication, Kinship, and Classification Structures in Oceania (Structural Analysis in the Social Sciences) , Cambridge University Press.