Graafiteoria

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Graafiteoria on diskreetin matematiikan haara , joka tutkii kaavioita . Yleisimmässä mielessä graafi on joukko pisteitä ( pisteitä , solmuja), jotka on liitetty joukkoon viivoja (reunat, kaaret) [1] . Graafeiden teoria (eli tiettyjä pisteitä yhdistävät suorat) on sisällytetty aloittelevien matemaatikoiden opetussuunnitelmiin, koska [2] [3] [4] [5] :

kuten geometria , on näkyvyyttä;
kuten lukuteoria , se on helppo selittää ja siinä on monimutkaisia ratkaisemattomia ongelmia;
sillä ei ole raskasta matemaattista laitteistoa ("kombinatoriset menetelmät objektien halutun järjestyksen löytämiseksi eroavat merkittävästi klassisista menetelmistä järjestelmien käyttäytymisen analysoimiseksi yhtälöiden avulla" [6] );
on selkeä sovellettu merkki.

Yli sadan vuoden ajan graafiteorian kehitystä on hallinnut neliväriongelma . Tämän ongelman ratkaisu vuonna 1976 osoittautui käännekohdaksi graafiteorian historiassa, minkä jälkeen se kehittyi nykyaikaisen soveltavan matematiikan perustaksi . Graafeiden universaalisuus on välttämätön viestintäverkkojen suunnittelussa ja analysoinnissa [7] .

Graafiteoriaa matemaattisena työkaluna voidaan soveltaa sekä käyttäytymistieteisiin ( informaatioteoria , kybernetiikka , peliteoria , systeemiteoria , liikenneverkot ) että puhtaasti abstrakteihin tieteenaloihin ( joukkoteoria , matriisiteoria , ryhmäteoria jne .) 8 ] [9] .

Monimuotoisista, monimutkaisista, epäselvistä ja erikoistuneista termeistä huolimatta monet malli- (kaavio-, rakenteelliset) ja konfiguraatioongelmat muotoillaan uudelleen graafiteorian kielellä, mikä helpottaa niiden käsitteellisten vaikeuksien tunnistamista [10] . Eri tietoaloilla käsite "kaavio" löytyy seuraavilla nimillä:

rakenne ( tie- ja vesirakentaminen );
verkko ( sähkötekniikka );
sosiogrammi ( sosiologia ja taloustiede );
molekyylirakenne ( kemia );
merikartta ( kartografia );
jakeluverkko ( energia )

ja niin edelleen [11] .

Kaavioiden varhaiset käyttötavat ja löydöt

Graafiteoria soveltavan matematiikan haarana on ”löydetty” useita kertoja. Avain graafiteorian ja sen kombinatorisen olemuksen ymmärtämiseen heijastuu James Sylvesterin sanoista : "Offsots teoria ( englanniksi haarautuminen ) on yksi puhtaan yleistyksen teorioista, sen koko tai sijainti ei ole oleellinen sille. ; se käyttää geometrisia viivoja, mutta ne eivät ole merkityksellisempiä kuin samat rivit sukutauluissa, jotka auttavat selittämään lisääntymisen lakeja .

Kaaviokaavion ensimmäinen käyttö tieteessä

Kaavio yhdestä kaavion lajikkeesta - puusta - on käytetty pitkään (tietenkin ymmärtämättä, että tämä on "kaavio"). Sukupuuta käytettiin visualisoimaan sukusiteitä . Mutta vain muinainen Aristoteleen teosten kommentaattori , foinikialainen filosofi ja matemaatikko Porfyrius , käytti puun kuvaa tieteen havainnollistamiseksi kaksijakoisesta jaosta teoksessaan "Johdatus" ( kreikaksi Εἰσαγωγή , lat . Isagoge ) filosofinen aineen käsite [13] .

Graafiteorian ensimmäinen käyttö ja "löytö"

Sveitsiläinen , preussilainen ja venäläinen matemaatikko Leonhard Euler vuonna 1736 julkaisemassaan artikkelissa ( latinaksi , Pietarin tiedeakatemian julkaisema ) kuuluisan Königsbergin siltaongelman ratkaisusta sovelsi ensimmäisenä graafiteorian ajatuksia. joidenkin väitteiden todistamisessa. Samaan aikaan Euler ei käyttänyt itse termiä "graafi", ei mitään graafiteorian termejä eikä graafien kuvia [14] . Leonhard Euleria pidetään graafiteorian (sekä topologian ) isänä, joka löysi graafin käsitteen [15] , ja 1736 on nimetty graafiteorian syntymävuodeksi [16] .

Toinen kaavioiden "löytö"

Vuonna 1847 saksalainen fyysikko Gustav Kirchhoff itse asiassa kehitti puiden teorian ratkaisemalla yhtälöjärjestelmän virran määrän löytämiseksi jokaisessa sähköpiirin piirissä . Sähköpiirin sijasta Kirchhoff itse asiassa tutki sitä vastaavaa kuvaajaa ja osoitti, että yhtälöjärjestelmän ratkaisemiseksi ei tarvitse analysoida kutakin kaavion sykliä , riittää, että otetaan huomioon vain itsenäiset syklit, jotka määritellään millä tahansa virityksellä . graafin puu [15] .

Esimerkki sähköpiiristä, sitä vastaava kaavio ja virittävä puu
Sähköpiiri 'n
Laske G vastaa sähköpiiriä
Kuvaajan G virittävä puu T

Kolmas kaavioiden "löytö"

Vuonna 1857 englantilainen matemaatikko Arthur Cayley löysi orgaanisen kemian käytännön ongelmien parissa tärkeän luokan kuvaajia - puita . Cayley yritti luetella tyydyttyneiden (tyydyttyneiden) hiilivetyjen C n H 2n+2 kemialliset isomeerit, joissa on kiinteä määrä n hiiliatomeja [ 15] .

Ensimmäiset neljä lineaarista alkaania (tyydyttyneet hiilivedyt)
Metaani CH 4
Etaani C 2 H 6
Propaani C 3 H 8
Butaani C 4 H 10

Neljäs kaavioiden "löytö"

Vuonna 1859 irlantilainen matemaatikko Sir William Hamilton keksi pelin Around the World. Tässä pelissä käytettiin dodekaedria , jonka jokainen 20 kärjestä vastasi kuuluisaa kaupunkia. Pelaajan piti kulkea "ympäri maailmaa", eli kulkea dodekaedrin reunoja pitkin siten, että se kulki jokaisen kärjen läpi täsmälleen kerran [15] .

Hamiltonin peli "Around the World"
Dodekaedrin kärkien kulkeminen polyhedronilla
Dodekaedrin tasolle projektion kärkien ohittaminen

Viides kaavioiden "löytö"

Vuonna 1869, Arthur Cayleysta riippumatta , ranskalainen matemaatikko Camille Jordan (erityisesti "Sur les assemblages de lignes" -paperissa) keksi ja tutki puita puhtaan matematiikan puitteissa. Samaan aikaan Jordan käytti graafiteorian termejä "vertex" ( fr. sommet ) ja "edge" ( fr. arête ), mutta termin "graafi" sijaan oli "reunojen yhteys" ( fr. assemblage d 'arêtes ) tai yksinkertaisesti "liitäntä" ( fr kokoonpano ). Jordan ei käyttänyt piirustuksia [17] . Samaan aikaan Jordan ei epäillyt löytönsä merkitystä orgaaniselle kemialle [15] .

Soient x , y , z , u , … des points en nombre quelconque ; xy , xz , yu , … des arêtes droites ou courbes, mais non bifurquées, dont chacune joint ensemble deux de ces points. Nous appellerons un semblable système un assemblage d'arêtes , dont x , y , z , u , … sont les sommets.

- M. Camille Jordan. Sur les assemblages de lignes) [17]

Sanan "count" alkuperä

Sana "graph" esiintyi ensimmäisen kerran graafiteorian merkityksessä vuonna 1878 englantilaisen matemaatikon James Sylvesterin lyhyessä muistiinpanossa ( englanniksi ) Nature -lehdessä, ja sillä on graafinen alkuperä käsitteiden yleistyksenä " Kekulen kaavio " ja "kemikografi" [18] [19] .

Jokainen invariantti ja kovariantti tulee siten ilmaistavaksi graafilla , joka on täsmälleen identtinen Kekuléan-kaavion tai kemikografin kanssa.

— Silvester JJ Kemia ja algebra (kursivointi kuten alkuperäisessä) [20]

Käännöksessä:

Siten jokainen invariantti ja kovariantti ilmaistaan jollakin graafilla , joka on täsmälleen identtinen Kekulen diagrammin tai kemograafin kanssa.

- Sylvester J. J. Chemistry and Algebra, 1878 (kursivointi alkuperäistä)

Sanan "kaavio" ja kaavioiden systemaattisen käytön alku

Piirrämme tavallisesti pisteitä, jotka edustavat ihmisiä, siirtokuntia, kemiallisia molekyylejä jne., ja yhdistämme nämä pisteet suhteita kuvaavilla viivoilla. Näitä ovat sosiogrammit ( psykologiassa ), yksinkertaistukset ( topologiassa ), sähköpiirit ( fysiikassa ), organisaatiokaaviot ( taloudessa ), viestintäverkot , sukupuut jne. 1900-luvun alussa unkarilainen matemaatikko Denes König oli ensimmäinen, joka ehdotti näiden kaavioiden kutsumista "kaavioiksi" ja tutki niiden yleisiä ominaisuuksia [8] . Vuonna 1936 Denes Königin kirjoittama maailman ensimmäinen graafiteoriaa käsittelevä kirja ( saksan kielellä ) "The Theory of Finite and Infinite Graphs" julkaisi suurimman osan tuloksista viimeisten 200 vuoden ajalta, alkaen vuodesta 1736 - ensimmäisen julkaisun julkaisupäivästä. Leonhard Eulerin kirja graafiteoriasta Königsbergin siltojen ratkaisuongelmilla [16] . Erityisesti Koenigin kirjassa on yleinen kappale Koenigsbergin siltaongelmalle ja dominoongelmalle (suljetun ketjun rakentaminen kaikista dominoista pelisääntöjen mukaisesti) [21] [22] .

Graafiteorian historia

Graafiteoria (eli tiettyjä pisteitä yhdistävät suorajärjestelmät) on erittäin aloittelijaystävällinen [3] :

on geometrinen selkeys;
on matemaattista sisältöä;
sillä ei ole hankalaa matemaattista laitteistoa.

"Kuten lukuteoria, myös graafiteoria on käsitteellisesti yksinkertainen, mutta herättää monimutkaisia ratkaisemattomia ongelmia. Kuten geometria, se on visuaalisesti miellyttävä. Nämä kaksi näkökohtaa sekä niiden monipuoliset sovellukset tekevät graafiteoriasta ihanteellisen aineen sisällytettäväksi matematiikan opetussuunnitelmiin .

Tämän matematiikan haaran synty 1700-luvulla liittyy matemaattisiin pulmiin. Graafiteoria oli melko pitkään "ei vakavaa" ja se liittyi kokonaan peleihin ja viihteeseen. Tämä graafiteorian kohtalo toistaa todennäköisyysteorian kohtaloa , joka myös löysi ensimmäisen kerran sovelluksensa vain rahapeleissä [3] .

Lyhyt kronologia tapahtumista graafiteorian kehityksessä [23]

vuosi	Tapahtuma
1735	Eulerin esitys graafiteoriaa käsittelevästä artikkelista Pietarin tiedeakatemiassa
1736	Vuotta pidettiin graafiteorian syntymävuotena
1741	Eulerin graafiteoriaa käsittelevän artikkelin julkaisu (päivätty 1736) Pietarin tiedeakatemiassa
1852	Francis Guthrie raportoi neliväriongelmasta Augustus de Morganille
1879	1879 historiallinen julkaisu, joka selittää Arthur Cayleyn neliväriongelman
1879	Alfred Kempen virheellinen "todiste" neliväriongelmasta
1890	Percy John Heawood havaitsi virheen Kempen "todistuksessa", osoitti lauseen olevan totta, jos "neljä" korvataan "viidellä", yleisti "maakartan" käsitteen tasosta suljettuihin pintoihin ja muotoili Heawoodin olettamuksen.
1927	Lev Semjonovitš Pontrjagin todisti (mutta ei julkaissut) Pontrjagin-Kuratovsky-lauseen
1930	Kazimierz Kuratowski julkaisi (Pontryaginista riippumatta) Pontryagin-Kuratovsky-lauseen
1936	Maailman ensimmäinen Denes Koenigin kirja graafiteoriasta "The Theory of Finite and Infinite Graphs" on julkaistu.
1968	Ryhmä matemaatikkoja eri maista osoitti Heawoodin oletuksen
1976	Ryhmä matemaatikoita on suorittanut neljän värin lauseen ensimmäisen tietokonetodistuksen
1977	Frank Harari perusti Graph Theory -lehden

Sijaintigeometria

Graafiteorian (sekä topologian ) isä on sveitsiläinen matemaatikko ja mekaanikko Leonhard Euler (1707-1783) [12] , joka kirjoitti artikkelin ratkaisusta Königsbergin siltaongelmaan . Euler kirjoitti [24] :

Sen suuruuksia käsittelevän geometrian haaran lisäksi, johon on aina kiinnitetty eniten huomiota, on toinen, tähän asti lähes tuntematon haara, jonka Leibniz mainitsi ensimmäisenä kutsuen sitä paikan geometriaksi [geometria situs]. Tämä haara käsittelee vain sijainnin ja sen ominaisuuksien määritystä, se ei sisällä niihin liittyviä mittauksia tai laskelmia ...

- Leonhard Euler. Yhden asemageometriaan liittyvän ongelman ratkaiseminen

Lisäksi Euler kirjoittaa, että ei ole selvää, mitkä ongelmat ja menetelmät niiden ratkaisemiseksi liittyvät paikkageometriaan. Siitä huolimatta Euler piti Königsbergin siltoja juuri sellaisena tehtävänä, kuten artikkelin otsikko osoittaa. Itse asiassa Gottfried Leibniz kirjoitti viimeistään vuonna 1679 kirjeessään Christian Huygensille [24] :

En ole tyytyväinen algebraan siinä mielessä, että sen avulla ei voi saada lyhimpiä todisteita tai kauneimpia geometrian konstruktioita. Siksi tämän vuoksi uskon, että tarvitsemme toisen analyysitavan, geometrisen tai lineaarisen, joka toimisi suoraan sijainnin kanssa samalla tavalla kuin algebra toimii määrän kanssa ...

Leibniz ottamalla käyttöön termin analyysisituus (sijaintianalyysi) ei luonut perustaa uudelle matemaattiselle tieteelle, mutta osoitti tulevaisuuden tutkimuksen suunnan [24] .

Königsbergin siltaongelma

Leonhard Eulerin artikkelin "Sijaintigeometriaan liittyvän ongelman ratkaisu" Königsbergin siltojen ongelman ratkaisusta julkaisulla on seuraava historia:

26. elokuuta ( 6. syyskuuta ) 1735 [25] Euler esitti artikkelin Pietarin tiedeakatemian konferenssissa [16] ;
vuonna 1736 Euler lähetti kaksi kirjettä:

13. maaliskuuta ( 24 ), 1736 - kirje Johann Jacob Marinonille , itävaltalaiselle tähtitieteilijälle ja matemaatikolle, joka on kokonaan omistettu Königsbergin siltojen ongelmalle [26] ;
3. huhtikuuta ( 14 ), 1736 - kirje Carl Leonard Gottlieb Oehlerille , saksalaiselle poliitikolle ja tähtitieteilijälle, jonka lopussa on puhe artikkelin pääajatuksista [26] ;

vuonna 1741 Pietarissa lopulta julkaistiin Eulerin artikkeli latinaksi päivämäärällä 1736 [26] :

Leonhardi Euleri. Solutio problematis ad geometriam situs pertiminentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. S. 128-140.

Käännetty [27] :

Leonard Euler. Yhden paikkageometriaan liittyvän ongelman ratkaisu / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, s. 128-140.

Koska Eulerin julkaisu on päivätty 1736 (ja molemmat kirjaimet myös), tämä vuosi on nimetty graafiteorian syntymäpäiväksi [16] .

Euler muotoili artikkelissaan seitsemän Königsbergin sillan ongelman [27] seuraavasti:

Königsbergin kaupungissa, Preussissa, on saari nimeltä Kneiphof ; sitä ympäröivä joki jakautuu kahteen haaraan, mikä näkyy kuvassa. Tämän joen oksia ylittää seitsemän siltaa a , b , c , d , e , f ja g . Näiden siltojen yhteydessä heräsi kysymys, voidaanko niiden yli kävellä siten, että jokaisen sillan yli ja täsmälleen kerran.

- Leonhard Euler. Yhden asemageometriaan liittyvän ongelman ratkaiseminen

Artikkelin loppuun Euler kirjoitti johtopäätökset melko nykyaikaisella kielellä [28] :

20. Näin ollen seuraava sääntö mahdollistaa kaikissa mahdollisissa tapauksissa suoraan ja vaikeuksitta selvityksen, onko mahdollista suorittaa kävely kaikkien siltojen yli ilman toistoa:

Jos on enemmän kuin kaksi aluetta, joille pariton määrä siltoja johtaa, voidaan varmuudella sanoa, että tällainen kävely on mahdotonta.

Jos kuitenkin on vain kaksi aluetta, joille pariton määrä siltoja johtaa, niin kävely on mahdollista edellyttäen, että se alkaa jommastakummasta näistä kahdesta alueesta.

Jos lopulta ei ole aluetta, jolle pariton määrä siltoja johtaa, on kävely vaadituin edellytyksin mahdollinen ja se voi alkaa miltä tahansa alueelta.

Siksi tämän säännön avulla esitetty ongelma voidaan ratkaista täysin.

- Leonhard Euler. Yhden asemageometriaan liittyvän ongelman ratkaiseminen

Neljän värin lause

Neljän värin lause on graafiteorian (ja ehkä koko matematiikan) tunnetuin väite, jota ei ole todistettu pitkään aikaan (tai ehkä ei koskaan todistettu). Kuka tahansa matemaatikko voi selittää tämän legendaarisen ongelman kenelle tahansa ohikulkijalle viidessä minuutissa, minkä jälkeen kumpikaan ei pysty ratkaisemaan ongelmaa ymmärtäessään ongelman. Seuraava lainaus on amerikkalaisen matemaatikon Kenneth O. Mayn nyt historiallisesta vuodelta 1965 ilmestyneestä artikkelista [29] :

[Oletetaan, että] mikä tahansa pallon tasolla tai pinnalla oleva kartta voidaan värjätä vain neljällä värillä siten, että kaksi vierekkäistä maata ei ole samanvärisiä. Jokaisen maan on koostuttava yhdestä yhdistetystä alueesta , ja maita kutsutaan vierekkäisiksi, jos niillä on yhteinen raja viivan muodossa (eikä vain yksi yhteinen piste). Tämä olettamus liittyy läheisesti graafiteorian muodikkaimpiin alueisiin, ja matematiikan alalla, jota kutsutaan kombinatoriseksi topologiaksi, se toimi katalysaattorina. Yli puolen vuosisadan ajan monet matemaatikot (jotkut sanovat kaikki) ovat yrittäneet ratkaista tätä ongelmaa, mutta ovat kyenneet todistamaan olettamuksen vain yksittäisissä tapauksissa... On yksimielisesti myönnetty, että olettamus on totta, mutta se on epätodennäköistä että se todistetaan yleisessä tapauksessa. Näyttää siltä, että sen on määrä säilyttää jonkin aikaa ero, että se on matematiikan yksinkertaisin ja houkuttelevin ratkaisematon ongelma.

— Toukokuu KO Nelivärisen arvelun alkuperä / Isis. 56 (1965). s. 346-348

Neljän värin lause liittyy graafiteoriaan, koska jokainen kartta luo kaavion seuraavasti:

maat (mukaan lukien ulompi alue) ovat huippuja;
naapurimaiden kärjet on yhdistetty reunalla.

Tämä kuvaaja on piirretty tasolle ilman, että se risteää reunoja. Nelivärilause on todistettu, jos todistetaan, että minkä tahansa sellaisen graafin kärjet voidaan värjätä neljällä värillä siten, että vierekkäisillä pisteillä on eri värit [30] .

Neljän värin lauseella on legendaarinen historia, mielenkiintoinen ja joskus käsittämätön [29] [31] :

on vahvistamattomia raportteja, että August Möbius oli tietoinen tästä ongelmasta vuonna 1840;
tiedetään varmasti, että eteläafrikkalainen matemaatikko ja kasvitieteilijä Francis Guthrie ilmoitti 23. lokakuuta 1852 skotlantilaiselle matemaatikolle ja loogikolle August de Morganille tästä ongelmasta, minkä jälkeen keskusteluja käytiin kapeissa matemaatikoiden ja amatöörien piireissä. ;
1879 historiallinen julkaisu, joka selittää ongelman

Cayley Arthur. Karttojen värjäyksestä // Proceedings of the Royal Geographical Society. 1879 Voi. 1, ei. 4. S. 259–261

omistaa Arthur Cayley , englantilainen matemaatikko. Nyt ongelma on saamassa enemmän julkisuutta;

samassa vuonna 1879 ongelmasta julkaistiin virheellinen "todiste".

Kempe AB Neljän värin maantieteellisestä ongelmasta // American Journal of Mathematics. 1879 Voi. 2, ei. 3. S. 193–200

Englantilainen kirkkolakimies ja matemaatikko Alfred Kempe . Tämä ei ollut vain ensimmäinen monista virheellisistä "todistuksista", vaan myös "oikein": tämän artikkelin ideoiden perusteella oli mahdollista ensin todistaa, että viisi väriä riittää, ja sitten suorittaa täydellinen tietokone todiste neljän värin lauseesta;

Englantilainen matemaatikko Percy John Heawood havaitsi virheen Kempen "todistuksessa" 11 vuoden jälkeen vuonna 1890 , ja tässä yhteydessä julkaistussa artikkelissa

Heawood PJ Map värilauseet // Quarterly Journal of Pure and Applied Mathematics. 24 (1890). s. 332-338

osoitti myös, että lause on totta, jos "neljä" korvataan "viidellä", ja lisäksi yleisti "maakartan" käsitteen tasosta suljetuille pinnoille ja muotoili Heawoodin arvelun ;

vuonna 1968 ryhmä matemaatikoita eri maista osoitti Heawoodin olettamuksen;
Vuonna 1976 amerikkalaiset matemaatikot suorittivat ensimmäisen tietokonetodistuksen nelivärilauseesta.

Pontrjagin-Kuratovsky-lause

Graafiteoria sisältää topologisia näkökohtia. Ensimmäinen tulos tähän suuntaan on Eulerin graafiteorian kaava , jonka hän sai vuonna 1736. Seuraava tulos Pontrjagin-Kuratovsky-lauseen muodossa saatiin vasta 191 vuotta myöhemmin: vuonna 1927 Neuvostoliiton matemaatikko Lev Semjonovich Pontryagin todisti (mutta ei julkaissut) tämän tuloksen, ja vuonna 1930 puolalainen matemaatikko Kazimierz Kuratowski julkaisi sen (riippumatta Pontryagin). Pontrjagin-Kuratovsky-lausetta kutsutaan myös Pontrjagin-Kuratovsky-kriteeriksi [32] :

Tasograafi on graafi, joka voidaan piirtää tasolle risteämättä reunoja. Graafia, jota ei voida piirtää tällä tavalla, kutsutaan ei-tasomaiseksi . Alla on kaksi tärkeää ei-tasomaista kuvaajaa, jotka on merkitty ja , joita ei voida piirtää tasoon ylittämättä reunoja. Nämä kaksi kuvaajaa eroavat muista sillä, että vain niitä käytetään Pontryagin-Kuratovsky-kriteerissä [33] . $K_{5}$ $K_{{3,3}}$

Legendaariset ei-tasokaaviot
Täydellinen graafi , jossa on viisi kärkeä $K_{5}$
Täydellinen kaksiosainen kaavio (3, 3) $K_{{3,3}}$

Ennen Pontryagin-Kuratovsky-kriteerin tuloa graafien tasomaisten vai ei-tasoisten osoittaminen oli erittäin vaikea ongelma graafiteoriassa [33] .

Pontryagin-Kuratovsky lause. Graafi on tasomainen silloin ja vain, jos se ei millään tavalla sisällä kaavioita ja . $K_{5}$ $K_{{3,3}}$

Oikealla on kaksi yksinkertaista todistetta ilman sanoja, että neliulotteisen hyperkuution ( tesseraktin ) luuranko graafina on ei-tasomainen. Ylempi kuva näyttää, että tesseraktissa on täydellinen graafi, jossa on viisi kärkeä , kun taas alempi kuva esittää täydellisen kaksiosaisen graafin (3, 3) . $K_{5}$ $K_{{3,3}}$

Tärkeimmät legendaariset versiot

Varhainen graafiteoria - graafien teoria ennen vuotta 1936, ennen Koenigin kirjan [24] julkaisemista .

Vuonna 1936 unkarilaisen matemaatikon Denes Königin maailman ensimmäinen graafiteoriaa käsittelevä kirja The Theory of Finite and Infinite Graphs julkaistiin saksaksi:

Kőnig, Denes. Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaf, 1936.

Tämä kirja koostui 248 sivusta (ilman esipuhetta, sisällysluetteloa ja bibliografiaa) ja suurimmasta osasta graafiteorian tuloksista 200 vuoden ajalta - Leonhard Eulerin Königsbergin siltaongelman ratkaisun sisältävän artikkelin julkaisupäivästä [16] .

Moderni graafiteoria - graafiteorioita vuodesta 1936, Koenigin kirjan julkaisusta lähtien. Koenigin kirjan julkaisusta lähtien, mutta pääasiassa toisen maailmansodan päättymisen jälkeen, graafiteoria on kehittynyt nopeasti. Tämä kasvu ei koostunut pelkästään graafiteoriaa koskevien kirjojen määrän kasvusta, vaan myös graafiteorian erityisnäkökohtien kehittymisestä [16] :

topologinen graafiteoria ;
algebrallinen graafiteoria ;
algoritminen graafiteoria.

Yksi modernin graafiteorian isistä on Frank Harari , joka perusti vuonna 1977 Graph Theory -lehden [34] [16] .

Frank Hararin kirjasta Graph Theory on tullut de facto klassikko [35] [36] .

Reinhard Distelin kirjalla "Theory of Graphs" (kesti 5 painosta) ei ole kilpailijoita venäjänkielisessä bibliografiassa. Tämä graafiteorian johdantokurssin kaanoni aloitti tiettyjen opiskelu- ja tutkimusalueiden tunnistamisen [2] [37] .

Varhaisen graafiteorian kuvaus

Varhainen graafiteoria kesti tasan 200 vuotta Leonhard Eulerin ensimmäisestä graafiteoriaa käsittelevästä paperista vuonna 1736 Denes Königin ensimmäiseen graafiteoriaa käsittelevään kirjaan vuonna 1936. Kirjan esipuheessa kirjoitetaan, että graafiteorian esittäminen rajoittuu absoluuttisten graafien alaan ( nykyaikaisessa terminologiassa abstraktit graafit ), eikä suhteellista graafiteoriaa ( modernin terminologian topologinen graafiteoria ) ja enumeratiivista graafiteoriaa oteta huomioon . . Alla on Denes Koenigin kirjan koko nimi ja sen lyhyt sisällysluettelo, joka koostuu lukujen otsikoista [16] [38] [39] .

Äärillisten ja äärettömien graafien teoria. Yksiulotteisten kompleksien kombinatorinen topologia ( saksa: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe , englanniksi: Theory of finite and infinite graphs ).

Luku I. Säätiöt ( saksaksi die Grundlahen , englanniksi Foundations ). Luku II. Euler- ja Hamiltonin kävelylenkit ( saksaksi Eulersche und Hamiltonsche Linien , englanniksi Euler - polut ja Hamiltonin pyörät ). III luku. Labyrinth Problem ( saksa das Labyrinthproblem , englanniksi the Labyrinth Problem ). Luku IV. Asykliset graafit ( saksa kreislose Graphen , englanniksi acyclic graphs ). Luku V. Puiden keskukset ( saksaksi Zentren der Bäume , englanniksi centers of trees ). Luku VI. Erikoismenetelmät äärettömien graafien tutkimiseen ( saksa Spezielle Untersuchungen über unendliche Graphen , englanniksi infinite graphs ). Luku VII. Suunnattujen graafien perustehtävät ( saksaksi Basisprobleme für gerichtete Graphen , englanniksi suunnattujen graafien perusongelmat ). Luku VIII. Joitakin suunnattujen graafien sovelluksia ( logiikka - peliteoria - ryhmäteoria ) _ _ Luku IX. Syklit , tähdet ja vastaavat lineaarimuodot ( saksaksi Zyklen und Büschel und die entsprechenden linearen Formen , englanniksi (suunnatut) syklit ja tähdet ja vastaavat lineaarimuodot ). Luku X. Jaksojen ja tähtien koostumus ( saksaksi Komposition der Kreise und der Büschel , englanniksi syklien ja tähtien kokoonpano ). XI luku. Säännöllisten äärellisten graafien faktorointi ( saksa Faktorenzerlegung regulärer endlicher Graphen , englanninkielinen säännöllisten äärellisten graafien faktorointi ). XII luku. Asteen 3 säännöllisten äärellisten graafien kertoimia _ _ _ Luku XIII. Säännöllisten äärettömien graafien kertoimia _ _ _ XIV luku. Erotuspisteet ja kärkijoukot ( saksaksi trennende Knotenpunkte und Knotenpunktmengen , englanniksi separating vertices and sets vertices ).

Graafiteorian esitysongelmat

Terminologian ongelmat

Yleisesti mainittu tosiasia graafiteorian monimuotoisesta ja sekavasta terminologiasta ja merkinnöistä on osittain seurausta siitä, että hyvin erilaisten tietoalojen asiantuntijat ovat kiinnostuneita tästä tieteestä [40] . Lisäksi itse graafiteorian terminologiassa on vastareaktiota , mikä vaikeuttaa hieman graafiteorian tutkimista ja esittämistä. Erityistä varovaisuutta noudattaen tulee soveltaa sellaisia käsitteitä kuin "reitti", "polku" ja "ketju", jotka tarkoittavat lähes samaa asiaa, voivat saada eri tekijöille erilaisia erityismerkityksiä [36] .

Tässä on mitä Frank Harari kirjoitti klassikkokirjansa alussa (julkaistu uudelleen vuonna 2003) [41] [42] .

Useimmat graafiteoreetikot käyttävät omaa terminologiaansa kirjoissa, artikkeleissa ja luennoissa. Graafiteoriaa käsittelevissä konferensseissa jokainen puhuja pitää väärinkäsitysten välttämiseksi välttämättömänä määrittää ensin kieli, jota hän käyttää. Edes sana "count" ei ole pyhä. Jotkut kirjoittajat itse asiassa määrittelevät "graafin" graafiksi, kun taas toiset tarkoittavat sellaisia käsitteitä kuin multigrafi, pseudografi, suunnattu graafi tai verkko. Meistä näyttää siltä, että graafiteorian terminologian yhtenäisyys ei koskaan tule olemaan

ei saavuteta, mutta ehkä se on hyödytöntä.

- Harary Frank. Graafiteoria, 2003

Radikaalisin näkemys on konstruktiivisen matematiikan näkökulmasta [43] [44] .

... meille ei näytä liian tärkeältä, kuinka kutsua viivoilla yhdistettyjä pisteitä: "kaavio", "kaksikuvaaja", "multigrafi", "pseudograafi". Todellisten rakenteiden pohjalta rakennetut graafit ovat liian monipuolisia luokiteltaviksi niiden piirteiden mukaan, joista tämän tieteen perustajat puhuivat. Olemme epävarmoja: onko tarpeen erottaa ollenkaan sellaisia käsitteitä kuin "reuna" - "kaari", "ääriviiva" - "sykli", "polku" - "reitti", "keskus" - "keskipiste" jne. , on Käytännössä (ja kaavioita käytetään pääasiassa) kaikki nämä termit unohdetaan ja korvataan millä tahansa sanalla: "kaavio", "reuna", "kierto", "polku", "keskus". Tietojenkäsittelytieteilijän on vaikea ymmärtää, miksi silmukalla varustettu graafi ei ole enää täysimittainen graafi, vaan vain "pseudografi". ... Eikö tietojenkäsittelytieteilijä tai muu asiantuntija osaa itse päättää, mitä sanaa käyttää - "polku" tai "reitti" - ja millä kirjaimilla hänen reitti-polkunsa on parempi osoittaa? Kaavio on visuaalinen kuva, jonka ansio on juuri siinä, että se vaatii vähän sanoja ja symboleja.

- Akimov O. E. Diskreetti matematiikka: logiikka, ryhmät, kaaviot, 2003

Ohjelmoijat edistävät myös terminologian leviämistä [45] .

Ohjelmointimaailmassa ei ole yksimielisyyttä siitä, kumpi termistä "kaavio" tai "verkko" on yleisempi. Olemme valinneet termin "verkko", koska se näyttää olevan yleisempi sovellusalueilla.

- Goodman S., Hidetniemi S. Johdatus algoritmien kehittämiseen ja analysointiin, 1981

Mutta viime vuosien painoksissa puhumme jo "enimmäkseen standardista" terminologiasta [46] [47] .

Tässä kirjassa käytetty terminologia on enimmäkseen vakiomuotoista. Vaihtoehtoja on tietysti olemassa, ja osa niistä on annettu käsitteen ensimmäisessä määritelmässä.

- Diestel R. Graph Theory, 2002. Reinhard Diestel. Graafiteoria, 2016

Esimerkiksi kybernetiikan alan perustyössä "Algoritmit: rakentaminen ja analyysi" käytetään standarditerminologiaa [48] .

Kun kuvataan algoritmin ajoaikaa tietyllä graafilla , määritämme syötegraafin koon yleensä sen kärkien lukumäärän ja graafin reunojen lukumäärän perusteella, eli syötetietojen kokoa kuvataan kahdella pikemminkin kuin yksi parametri. $G=(V,E)$ $|V|$ $|E|$

- Kormen T. H. et al. Algoritmit: rakentaminen ja analyysi, 2009

Graafisen piirustusongelmat

Abstraktit graafit voidaan esittää tasossa eri tavoin. Kysymys siitä, ovatko nämä graafikuvat isomorfisia , eli ovatko nämä graafikuvat isomorfisia yksittäisen abstraktin graafin suhteen, voi olla ei-triviaali. Joskus tämä ongelma on helppo ratkaista. Esimerkiksi seuraavat kaksi kuvaajaa eivät ole isomorfisia, koska niillä on eri määrä pisteitä [49] .

Ei-nisomorfiset graafit: eri määrä pisteitä
kolme huippua
neljä huippua

Seuraavat kaksi kuvaajaa ovat myös ei-isomorfisia, koska niillä on eri määrä reunoja [49] .

Ei-nisomorfiset graafit: erilainen määrä reunoja
viisi kylkiluuta
kuusi kylkiluuta

Mutta sen osoittamiseksi, että kaksi seuraavaa kuvaajaa eivät ole isomorfisia, tarvitaan hienovaraisempi argumentti. Ensimmäisessä graafissa on kaikkien pisteiden suljettu läpikulku kerran ( Hamiltonin sykli ):

1-2-3-4-8-7-6-5-1,

kun taas toinen kaavio ei. Toisin sanoen minkä tahansa toisen graafin kärkien numeroinnille on mahdotonta saada sille Hamiltonin sykliä, joka vastaa ensimmäisen graafin Hamiltonin sykliä [49] .

Ei-nisomorfiset graafit: eri huippupisteiden läpikäymiset
On Hamiltonin sykli
Ei Hamiltonin sykliä

Jos ei ole heti selvää, kuinka osoittaa, että graafit eivät ole isomorfisia, kysymys isomorfismin olemassaolosta voi osoittautua vaikeaksi. Seuraavat kaksi isomorfista kuvaajaa eivät ole ensisilmäyksellä isomorfisia [49] .

Isomorfiset kuvaajat Näennäisesti ei-nisomorfisia
Pyöreä kaavio $C_{7}(1,2)$
Pyöreä kaavio $C_{7}(1,3)$

Kirjallisuuden ongelmat

Mihin lähteisiin kannattaa keskittyä graafiteoriaa esitettäessä? Tässä muutamia kirja-arvosteluja.

Harary Frank. Graafiteoria, 2003.

Frank Hararin kirjasta on tullut de facto klassikko [35] [36] .

F. Hararin monografian "Graph Theory" julkaisemisesta on kulunut 30 vuotta, mutta sen houkuttelevat ominaisuudet eivät ole haihtuneet ollenkaan. Kirjoittajan toteuttama ja tämän kirjan ansiosta laajalti levitetty terminologian yhdistäminen on tullut yleisesti hyväksytyksi. Graafiteorian opetusta F. Hararin kirjalla tapahtuu monissa maamme yliopistoissa.

- V.P. Kozyrevin esipuhe (2002) kirjaan: Harari Frank. Graafiteoria, 2003 Herbert Fleischnerin Euler Graphs and Related Topics tarjoaa luettelon kirjoista, joita suositellaan johdatukseksi graafiteoriaan. Nämä ovat englanninkielisiä kirjoja, joista vain ensimmäinen on käännetty venäjäksi: tämä on Frank Hararin kirja Theory of Graphs [50] .

Distel R. Graafiteoria, 2002.

Reinhard Distelin kirjalla "The Theory of Graphs" (kesti 5 painosta) ei ole kilpailijoita venäjänkielisessä bibliografiassa. Tämä graafiteorian johdantokurssin kaanoni aloitti tiettyjen opiskelu- ja tutkimusalueiden tunnistamisen [2] [37] .

... nyt on tarpeeksi käännöksiä venäjäksi graafiteorian oppikirjoista, ensisijaisesti Distelin upeasta kirjasta. Ja valitettavasti vain Distelin kirjat.

...Distelin kirjan 5. painoksen käännöstyö kannusti jatkamaan kirjani parissa vuonna 2017 pitkän tauon jälkeen. Huomasin kuinka suuri " symmetrinen ero " hänen kirjansa ja minun kirjani välillä on.

- Karpov D.V. Graafiteoria . 2017 tai myöhemmin

Graafiteorian luokitus

Graafiteorian luokitus on kerättävä eri lähteistä.

Graafiteoria [16] :

abstraktit graafit ("tavalliset" graafit);
topologinen graafiteoria ;
kaavioiden luettelointi ;
algebrallinen graafiteoria ;
algoritminen graafiteoria.

Graafiteoria [51] :

alkeis-kombinatorinen graafiteoria;
looginen graafiteoria;
algebrallinen graafiteoria ;
matroidit ;
kaavioiden toistuvat ominaisuudet;
satunnaiset kaaviot ;
äärettömät graafit.

Analyyttinen graafiteoria [52] :

Graafiteorian perustermit

Graafiteoria, kuten mikä tahansa moderni matemaattinen malli , käyttää lyhennettyjä symboleja, jotka säästävät ajattelua ja tekevät matemaattisesta mallista joustavan ja tehokkaan [53] .

Tässä annetaan hienovaraisesti ja ytimekkäästi graafiteorian pääosan ensimmäiset termit. Useimmat vakiotermit ovat niin kuvailevia, että ne ovat helposti ymmärrettäviä. On välttämätöntä määritellä useita käsitteitä riittävän tiukasti, jotta niitä voidaan käyttää laajasti tulevaisuudessa [41] [54] [55] .

Kaaviot ( englanninkieliset kaaviot )

Lyhyt mutta edustava yhteenveto oikean graafin käsitteeseen liittyvistä graafiteorian tärkeimmistä määritelmistä. Näitä käsitteitä esitellään yksi toisensa jälkeen melko systemaattisesti, vaikkakin hieman tylsästi [56] [57] [58] .

Graafi on kaksi äärellistä disjunktijoukkoa , ja toinen koostuu ensimmäisen 2 - alkioisista osajoukoista . Merkintä: [59] , missäja. $G=(V,E)$ $E\subseteq V\times V$ $V\cap E=\varnothing$

Graafin kärkipiste (solmu, piste) on graafijoukon elementti. Nimitys:.

V

v\in V(G)

Kuvaajan reuna (viiva, kaari) on kaaviojoukon elementti. Nimitys:.

E

e\in E(G)

Vanhemmissa versioissa reunaa voitaisiin kutsua myös haaraksi , linkiksi [60] tai käyräksi [61] . Tyypillisesti kuvaaja esitetään kaaviolla , jota usein kutsutaan kaavioksi. Graafin järjestys on graafin kärkien lukumäärä . Nimitys: . Kuvaajan reunojen lukumäärä on merkitty .

G

|G|

\|G\|

Tyhjä graafi on graafi ilman pisteitä. Nimitys: .

G(\varnothing ,\varnothing )\equiv \varnothing

Triviaalikaavio on graafi, jonka luokka on 0 tai 1.

Esimerkkejä kaavioista
Vasemmalta oikealle: järjestys 1 graafi, järjestys 2 graafi 1 reunalla, järjestys 4 graafi 4 reunalla, 8 graafi 12 reunalla

Reunan päätypisteet tai päät ovat kaksi kärkeä, jotka määrittävät reunan. Reuna yhdistää sen päätypisteet. Reuna ja sen päätepiste ovat sattuvia tai toinen on toisen vieressä . Huippupisteen kaikkien reunojen joukko on merkitty . $v\in V(G)$ $E(v)$

Vierekkäiset tai vierekkäiset kärjet ovat kaksi kärkeä, jotka osuvat samaan reunaan. Vierekkäiset reunat ovat reunoja, joilla on yhteinen pää. Täydellinen graafi on graafi, jonka kaikki kärjet ovat pareittain vierekkäin, eli mitkä tahansa kaksi kärkeä on yhdistetty reunalla. Täydellisen graafin merkintäpisteillä: [62] (joskus). Kaaviotakutsutaan kolmioksi .

n

K_n

K^n

K_{3}

Esimerkkejä täydellisistä kaavioista
Ensimmäiset viisi täydellistä kaaviota

Kaksiosainen graafi tai bigraph on graafi, joka mahdollistaa pistejoukon jakamisen kahdeksi osajoukoksi siten, että :

minkä tahansa reunan päät kuuluvat osion eri osajoukkoon;
osion kunkin osajoukon kärjet eivät ole pareittain vierekkäisiä.

Täydellinen kaksiosainen graafi on kaksiosainen graafi, jossa jokainen kaksi kärkeä osion eri osajoukoista ovat vierekkäin. Täydellisen kaksiosaisen graafin merkintä osion osajoukkojen kärkien lukumäärällä ja : [62] .

n

m

{\näyttötyyli K_{n,m))

Erilaisia kaavioita täydellisestä kaksiosaisesta graafista (3, 3)
Kaavio $K_{{3,3}}$
Kaavio $K_{{3,3}}$
Kaavio $K_{{3,3}}$
Kaavio $K_{{3,3}}$

Graafin kärjen aste tai valenssi on kärkeen osuvien reunojen lukumäärä. Vertex-astemerkintä: [63] . $v$ $\deg v\equiv d(v)$

Graafin eristetty kärkipiste on piste, jonka aste on nolla. Kuvaajan perässä oleva tai riippuva kärkipiste on ensimmäisen asteen kärki. Graafin kärkien minimiaste on merkitty , maksimiaste - .

G

{\näyttötyyli \min \deg G\equiv \delta (G)}

\max \deg G\equiv \Delta (G)

Säännöllinen tai homogeeninen graafi on graafi, jonka kaikilla kärjeillä on sama aste. Toisin sanoen tällaisen graafinaste on.

G

\delta (G)=\Delta (G)

R-säännöllinen tai r-uniforminen graafi on graafi , jossa on . Tällaisia kuvaajia kutsutaan myös yksinkertaisesti säännöllisiksi tai homogeenisiksi . 3-säännöllistä kuvaajaa kutsutaan kuutioksi .

G

\delta (G)=\Delta (G)=r

Kukin graafin reuna osuu kahteen kärkeen, ja jokainen reuna antaa kaksi graafin kärkien asteiden summaan. Saamme historiallisesti ensimmäisen graafiteorian lauseen , jonka Leonhard Euler on todistanut vuodelta 1736 päivätyssä artikkelissa ( saman artikkelin graafiteorian ensimmäinen tulos on Königsbergin siltaongelman ratkaisu). Lause. Graafin kärkien asteiden summa on kaksi kertaa sen reunojen lukumäärä. Johtopäätös 1. Missä tahansa graafissa parittomat pisteet ovat parillisia. Seuraus 2. Jokaisella kuutiograafilla on parillinen määrä pisteitä.

Esimerkki säännöllisistä kaavioista
Kuutiograafi, jossa on 4 kärkeä
4-säännöllinen graafi, jossa on 6 kärkeä
5-säännöllinen graafi, jossa on 12 kärkeä

Kaavioiden tyypit _ _

Jatkoa lyhyelle mutta edustavalle yhteenvedolle graafin käsitteeseen liittyvistä tärkeimmistä graafiteoreettisista määritelmistä. Täydellisyyden vuoksi luettelemme useita erilaisia kaavioita [64] [65] [66] .

Kahden graafin isomorfismi on yksi yhteen vastaavuus niiden kärkijoukkojen välillä, joka säilyttää vierekkäisyyden. Nimitys:. $G\simeq H$

On selvää, että isomorfismi on graafien ekvivalenssisuhde . Yleensä isomorfisia kuvaajia ei eroteta ja ne kirjoitetaan tilalle , isomorfismin käsite on laajalti käytössä graafien kuvaamisessa.

G=H

G\simeq H

Kuvaajan invariantti on luku, joka saa saman arvon isomorfisissa kaavioissa. Täysi joukko invariantteja määrittelee graafin isomorfismiin asti . Esimerkiksi graafin kärkien lukumäärä ja reunojen lukumäärä on täydellinen joukko invariantteja mille tahansa graafille, jossa on enintään 3 kärkeä.

Esimerkki isomorfisista kaavioista
Vertex Crossing Chart $K_{4}$
Kaavio ilman risteyksiä $K_{4}$

Graafin aligraafi on graafi, jonka kaikki kärjet ja reunat kuuluvat alkuperäiseen graafiin. Alkuperäinen graafi on sen aligraafin ylikuvaaja . Toisin sanoen kaavio sisältää kaavion : . $G$ $G'$ $G\subseteq G'$

Graafin ydinosagraafi on osagraafi, joka sisältää kaikki sen epigrafin kärjet. Graafin generoitu tai indusoitu aligraafi on aligraafi, joka sisältää kaikki epigrafin reunat sen kärkijoukolle, eli generoidun aligraafin kaksi kärkeä ovat vierekkäin silloin ja vain, jos ne ovat vierekkäin epigrafissa.

Esimerkki kaaviosta ja aligraafista
Lähdekaavio
Varsi, mutta ei luotu alikaavio
Luotu, mutta ei kattava aligraafi

Multigrafi on äärellinen disjunktijoukko ja multijoukko , ja monijoukko koostuu joukon 2-alkioisista osajoukoista. Merkintä: [67] , jossa mikä tahansamonijoukonja. $G=(V,E)$ $e\in E$ $e\in V\times V$ $V\cap E=\varnothing$

Multigrafissa pistepari voidaan yhdistää useammalla kuin yhdellä reunalla. Useat reunat ovat reunoja, jotka yhdistävät saman pisteparin. Toisin sanoen multigrafi on graafi, jossa on useita reunoja, ja graafi on multigrafi ilman useita reunoja. Yksinkertainen tai tavallinen graafi on graafi ilman useita reunoja, jos monigraafia kutsutaan graafiksi. Pseudografi on äärellinen disjunktijoukko ja monijoukko, ja monijoukko koostuu sekä joukon 1- että 2-alkioisista osajoukoista. Merkintä:, missä on multisetja.

G=(V,E)

E\subseteq V\cup (V\times V)

V\cap E=\varnothing

Pseudografissa reuna voi yhdistää kärjen itseensä. Silmukka on reuna, jonka päätypisteet ovat samat. Joskus pseudografia kutsutaan multigrafiksi. Hypergrafi on äärellinen disjunktijoukko ja monijoukko, ja monijoukko koostuu kaikista joukon osajoukoista. Merkintä:, jossa mikä tahansamonijoukon elementti kuuluu Boolen :, ja.

G=(V,E)

e\in E

e\in P(V)

V\cap E=\varnothing

Toisin sanoen hypergraafissa reuna voi yhdistää yhden tai kahden kärjen lisäksi mielivaltaisen määrän pisteitä. Suunnattu graafi tai digraafi on pseudografi, jonka reunat ovat orientoituneita , eli niillä on alkupiste ja loppupiste . Merkintä: [68] , jossa multisetkoostuu järjestetyistä pareista ja.

D=(V,E)

E

v,u\in V

V\cap E=\varnothing

Suunnattu reuna tai kaari on digraafin reuna.

Esimerkkejä kaaviotyypeistä
Monikuva Königsbergin siltaongelmasta
pseudografi
hypergrafi , $V=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ $E=\{e_{1},e_{2},e_{3},e_{4}\}=$ $=\{\{v_{1},v_{2},v_{3}\},\{v_{2},v_{3}\},$ ${\displaystyle \{v_{3},v_{5},v_{6}\},\{v_{4}\}\))$
digrafi

Polut liitettävyys muokkaa _

Graafin ominaisuus, jota pidetään yhtenä yksinkertaisimmista ja samalla perusominaisuuksista, on liitettävyysominaisuus. Tässä on tämän yhteysominaisuuden lähin käsitepiiri [69] [70] [71] .

Graafissa oleva polku tai yksinkertainen polku on aligraafi, joka on erillisten pisteiden sarja, jossa jokainen kärki on kytketty seuraavaan reunaan. Polun merkintä ( englanniksi polku ):, missä $P=(V,E)$

V=\{x_{0},x_{1},x_{2},\dots ,x_{k}\}

. _

{\displaystyle E=\{x_{0}x_{1},x_{1}x_{2},x_{2}x_{3},\dots ,x_{k-1}x_{k}\))

jokainen on erilainen.

x_{i}

Teoreettisessa ja käytännön työssä polkua voidaan kutsua eri tavalla, esimerkiksi yksinkertaiseksi ketjuksi . Polun loppupisteet tai päät ovat kärjet ja . Vertices ja ovat yhteydessä .

x_{0}

x_k

x_{0}

x_k

P

Polun sisäpisteet ovat kärjet .

{\displaystyle x_{1},x_{2},\dots ,x_{k-1))

Polun pituus on polun reunojen lukumäärä. Polun pituuden merkintä : .

k

P_{k}

Graafin sykli tai yksinkertainen sykli on aligraafi, joka on eri pisteiden suljettu sarja, jossa jokainen kärki on kytketty seuraavaan reunaan. Syklin nimitys ( englanniksi cycle ):, missä

C=(V,E)

{\displaystyle V=\{x_{0},x_{1},x_{2},\dots ,x_{k},x_{0}\))

. _

E=\{x_{0}x_{1},x_{1}x_{2},x_{2}x_{3},\dots ,x_{k-1}x_{k},x_{ k}x_{0}\}

jokainen on erilainen.

x_{i}

Jakson pituus on syklin reunojen lukumäärä. Jakson pituuden merkintä : .

k

C_{k}

Jakson sointu on reuna, joka ei kuulu sykliin ja yhdistää sen kaksi kärkeä. Lause. Mikä tahansa graafi , jolla on minimipisteiden aste, sisältää syklin, jonka pituus on vähintään .

G

\delta (G)\geqslant 2

{\näyttötyyli \delta (G)+1}

Polku esimerkki
Kaksi polkua : keltainen ja sininen $P_{4}$
Punainen sykli . Katkoviivat - kiertosoinnut $C_{12}$

Yhdistetty graafi on graafi, jossa mitkä tahansa kaksi kärkeä on yhdistetty polulla.

Kuvaajan yhdistetty komponentti tai komponentti on kaavion suurin yhdistetty osagraafi. Irrotettu graafi koostuu vähintään kahdesta yhdistetystä komponentista. Kytketty komponentti ei ole tyhjä; joten tyhjällä kaaviolla ei ole komponentteja.

Esimerkki yhdistetystä ja irrotetusta graafista
Yhdistetty graafi 5 kärjessä
Irrotettu graafi, jossa on 2 komponenttia 5 kärjessä

Erotuspiste eli graafin artikulaatiopiste on graafin kärki, jonka poistamisen jälkeen graafin toisiinsa liittyvien komponenttien määrä kasvaa. Graafin silta on graafin reuna, jonka poistaminen lisää graafin yhdistettyjen komponenttien määrää. Sillan päätypisteet ovat erotuspisteitä. On selvää, että graafin siltoja ovat ne ja vain ne reunat, jotka eivät kuulu mihinkään sykliin. Erottamaton graafi on ei-tyhjä yhdistetty graafi ilman erottavia pisteitä.

Split Vertices ja Bridge Esimerkkejä
e - silta. Vertex a ja sillan päät ovat erottavia pisteitä

Graafin reitti on aligraafi, joka on kärkijono, jossa jokainen kärki on kytketty seuraavaan reunaan. Reitin nimi: , missä $(V, E)$

V=\{x_{0},x_{1},x_{2},\dots ,x_{k}\}

, .

{\displaystyle E=\{x_{0}x_{1},x_{1}x_{2},x_{2}x_{3},\dots ,x_{k-1}x_{k}\))

Reitti voi sisältää yhteneviä kulmia ja kärkipisteitä. On selvää, että jos kaikki polun kärjet ovat erillisiä, tämä on polku. Reitti on suljettu , jos muuten reitti on auki .

{\displaystyle x_{0}=x_{k))

Kuvaajan Eulerin sykli tai Eulerin kiertomatka on graafin suljettu polku, joka kulkee graafin kaikki reunat tarkalleen kerran. Euler-graafi on graafi, jolla on Eulerin sykli. On selvää, että Euler-graafi on yhdistetty. Lause (Euler, 1736). Yhdistetty Euler-graafi jos ja vain jos kaikilla graafin kärjeillä on parillinen aste. Seuraus. Yhdistetyssä graafissa, jossa on kaksi parittoman asteen kärkeä, on avoin polku, joka kulkee kaikki reunat tarkalleen kerran. Lisäksi tämä reitti alkaa yhdestä parittoman asteen kärjestä ja päättyy toiseen.

Esimerkkejä Euler-graafista
Täydellinen kaavio , reunan läpikulku ei ole mahdollista kerran $K_{4}$
Ei-Euler-graafi, jolla on avoin polku, joka kulkee kaikkien reunojen läpi tarkalleen kerran
Eulerin graafi. Eulerin sykli - kuljetaan reunat aakkosjärjestyksessä

Puut ( englantilaiset puut )

Yllä on esitetty neljä graafiperhettä, nämä ovat täydellisiä, kaksiosaisia, säännöllisiä ja Euler-graafia. Toista kaavioperhettä eri tieteenaloilla kutsutaan samaksi - puiksi. Puut löytävät käyttökohteita useilla tiedon aloilla ja niillä on erityinen asema itse graafiteoriassa rakenteensa äärimmäisen yksinkertaisuuden vuoksi, ja graafitehtävää ratkaistaessa sitä voidaan ensin tutkia puilla [72] [73] [74] .

Metsä on kaavio ilman syklejä.

Puu on yhdistetty metsä. Puun nimitys ( eng. tree ):.

T

Toisin sanoen metsä on graafi, jonka komponentit ovat puita. Lehti on puun asteen 1 kärki. Missä tahansa ei-triviaalissa puussa on vähintään kaksi lehteä. Kun lehti poistetaan, puu jää takaisin. Lause. Kaaviolle seuraavat lauseet ovat vastaavia: (i) graafi on puu; (ii) graafin jokainen kaksi kärkeä on yhdistetty ainutlaatuisella polulla; (iii) graafi on minimaalisesti yhdistetty , eli graafi on yhdistetty ja katkeaa, kun jokin reuna poistetaan; (iv) graafi on maksimaalinen asyklinen , eli graafissa ei ole sykliä ja sykli syntyy, kun mitkä tahansa kaksi ei-viereistä kärkeä on yhdistetty reunalla. Seuraus 1. Jokaisella yhdistetyllä graafilla on virittävä puu. Todiste. Lauseen ehtojen (i) ja (iii) ekvivalenssista seuraa, että mikä tahansa minimivirittävä osagraafi on puu. Johtopäätös 2. Yhdistetty -vertex- graafi on puu silloin ja vain, jos sillä on täsmälleen reuna.

n

n-1

Kaikki puut, joissa on 5 kärkeä

Puun juuri on kiinteä puun latva. Juurimerkintä : . _ _ $r$

Juurtunut puu on puu, jolla on juuri. Puujärjestys on puun ja sen juuren määräämä osittaisjärjestys puun kärjessä: kahdelle pisteelle ja puulle , jos polku , jonka päät ja kuuluu .

x

y

x \leqslant y

x

r

y

Puun järjestyksessä:

puun juuri on pienin elementti; $r$
mikä tahansa puun lehti muu kuin juuri on suurin alkuaine;
minkä tahansa puun reunan päät ovat vertailukelpoisia.

Ketju tai lineaarisesti järjestetty joukko on osittain järjestetty joukko, jossa mikä tahansa elementtipari on vertailukelpoinen. Lause. Puun polun kärjet päillä ja muodostavat ketjun, jossa on mikä tahansa puun kiinteä kärkipiste kuin juuri .

r

y

y

r

Esimerkkejä juurtun puun ketjuista
Puu, jonka juuret 3 ja maksimiketjut 3-1-2, 3-7-6-5, 3-7-10

Graafin normaali virittävä puu on graafin juurtunut virittävä puu siten, että mitkä tahansa kaksi vierekkäistä graafin kärkeä ovat vertailukelpoisia.

Normaalia virittävää puuta kutsutaan myös syvyyshakupuuksi sen mukaan, miten niitä käytetään tietokonehaussa. Lause. Jokaisella yhdistetyllä graafilla on normaali virittävä puu, ja mikä tahansa graafin kärki voi olla puun juuri. Alla olevassa kuvassa on kaksi mahdollista virittävää puuta täydelliselle kuvaajalle . Virtaavat puita edustavat lihavoitut reunat. Vasemmanpuoleinen virittävä puu on normaali, jos sen juuri on kärki A tai D; juurilla B tai C, normaaliutta ei saada, koska silloin reunan päät, esimerkiksi AD, ovat vertaansa vailla. Oikealle virittävä puu ei voi olla normaali minkä tahansa juurensa valinnan suhteen; aina tulee olemaan reuna, jolla on vertaansa vailla olevat päät.

K_{4}

Täydellisen 4-kärkisen graafin kaksi virittävää puuta
Lihavoidut reunat ovat normaalia virittävää puuta, jonka juuret ovat A:sta tai D:stä
Lihavoidut reunat ovat virittävä puu, joka ei voi olla normaalia millekään juurivalinnalle

Graafiteorian nykytila

Graafiteorian nykyaikainen tila vastaa tavanomaista oppikirjaa, jossa yhdistyvät klassikot ja aktiivinen matematiikka ja joka kattaa aiheen päämateriaalin. Tällaisen kirjan sisällysluettelo antaa lyhyen kuvan graafiteorian nykytilasta, josta tämä osa koostuu [75] .

Sovitus, peittäminen ja pakkaus ( englanniksi matching, covering and packing )

Kuinka löytää graafista suurin mahdollinen määrä riippumattomia reunoja? Voidaanko graafin kaikki kärjet jakaa pareiksi? Vastaukset alkavat seuraavilla käsitteillä [76] [77] [78] .

Sovittava tai itsenäinen graafin reunojen joukko on joukko graafin reunoja, joilla ei ole yhteisiä pisteitä.

Osumat kaavioissa (näkyy punaisella)
Kahden reunan yhteensopivuus
Kolmen reunan yhteensopivuus

Täsmäys kattaa joukon graafin kärkipisteitä, jos jokainen joukon kärki on sisällytetty johonkin sovituksen reunaan.

Graafin kärkien peittäminen sovituksilla (näkyy punaisella)
Vastaavuus kattaa 8 graafin kärkeä 9:stä
Vastaavuus kattaa graafin kaikki 8 kärkeä

Avioliittolause ( Hall , 1935). Kaksiosainen graafi sisältää sovituksen, joka kattaa yhden osan, jos ja vain, jos mikä tahansa määrä tämän osan pisteitä on kytketty vähintään yhtä moneen toisen osan kärkeen.

Graafi voidaan osioida (tai graafi voidaan pakata tai graafi voidaan peittää tai hajottaa) useisiin virittäviin puihin tai kattaviin metsiin , joilla ei ole yhteisiä reunoja.

Puuisuus on metsien vähimmäismäärä, joihin graafi voidaan jakaa. Esimerkiksi graafissa on 5 kärkeä, joten sen virittävän puun enimmäiskoko on 4. Toisaalta graafissa on 10 reunaa, joten niiden peittämiseen tarvitaan vähintään 3 puuta. Siksi kaavion osio kolmeen alla näkyvään metsään on minimaalinen.

K_{5}

K_{5}

K_{5}

Täydellisen kaavion, jossa on viisi kärkeä, vähintään ulottuva metsä
Täydellinen kaavio $K_{5}$
1st Count Spanning Forest $K_{5}$
2nd Count Spanning Forest $K_{5}$
Kuvaajan 3. virittävä puu $K_{5}$

Yhteydet _ _ _

Graafin liitettävyyttä tutkitaan syvemmälle käyttämällä käsitteitä -liitettävyys, lohko ja polkujen riippumattomuus [79] [78] . $k$

$k$ -yhdistetty graafi (vertex - yhdistetty) $k$ on yhdistetty graafi, joka:

on enemmän pisteitä; $k$
pysyy kytkettynä, kun on poistettu vähemmän kuin yksikään kärki. $k$

Esimerkiksi mikä tahansa ei-tyhjä graafi on 0-yhdistetty, ja mikä tahansa yhdistetty graafi, jolla on useampi kuin yksi kärki, on 1-kytketty. Kaksinkertaisesti yhdistetty graafi pysyy yhdistettynä, kun mikä tahansa kärkipiste poistetaan. Graafin liitettävyys tai kärkiliitettävyys

\kappa

on suurin kokonaisluku , jolle graafi on -kytketty.

k

k

Esimerkiksi jos ja vain jos kaavio:

\kappa =0

tai ei ole yhteydessä;
tai koostuu yhdestä kärjestä.

Yhdistetyn graafin ja artikulaatiopisteen liitettävyys on 1. Täydellinen graafi pysyy yhdistettynä, kun mikä tahansa määrä pisteitä poistetaan, ja sillä on yksi kärki kärjen poistamisen jälkeen , joten kaikille .

K_n

n-1

\kappa (K_{n})=n-1

n\geqslant 1

Reunoihin yhdistetty graafi

k

ja graafin reunaliitettävyys

\lambda

määritellään samalla tavalla . Esimerkiksi jos ja vain jos kaavio:

\lambda=0

tai ei ole yhteydessä;
tai koostuu yhdestä kärjestä.

Yhdistetyn graafin reunaliitettävyys sillan kanssa on 1. Liitettävyys , reunaliitettävyys ja pisteiden minimiaste liittyvät toisiinsa seuraavalla epäyhtälöllä.

\lambda

\delta

Lause (Whitney, 1932). Jokaiselle graafille , jolla on useampi kuin yksi kärki

G

\kappa (G)\leqslant \lambda (G)\leqslant \delta (G)

Esimerkki kaaviosta, jonka yhteysarvot eivät ole keskenään samanarvoisia
Laske kanssa $\kappa =2,\lambda =3,\delta =4$

Graafilohko on maksimaalinen yhdistetty osagraafi ilman artikulaatiopisteitä.

Lohkolla ei ole omia artikulaatiopisteitä, mutta siinä voi hyvinkin olla alkuperäisen graafin artikulaatiopisteitä. Yhden lohkon graafia voidaan yksinkertaisesti kutsua lohkoksi . Aligraafi on lohko silloin ja vain, jos se:

maksimaalinen kaksinkertaisesti yhdistetty osagraafi;
silta huipuineen;
eristetty toppi.

Kuvaajan eri lohkot voivat maksimaalisuudestaan johtuen leikkiä vain yhdessä artikulaatiopisteessä. Näin ollen:

kaavion jokainen reuna koostuu yhdestä lohkosta;
itse graafi on lohkojen liitto.

Tässä mielessä lohkot ovat kytkettyjen komponenttien kaksinkertaisesti kytkettyjä analogeja. Vain liitetyt komponentit eivät leikkaa toisiaan, kun taas lohkot voivat leikata. Lohkot yhdessä niiden leikkaamistapojen kanssa määrittelevät kaavion karkean rakenteen - lohkojen ja nivelpisteiden kuvaajan . Graafin lohkojen ja nivelpisteiden graafi on kaksiosainen graafi, jossa on sarja kärkipisteitä ja , joka on rakennettu seuraavasti:

a

B

kärjet vastaavat kaikkia alkuperäisen graafin artikulaatiopisteitä, kärjet vastaavat lohkoja; $a$ $B$
Reuna yhdistää kärjen kärkeen, jos artikulaatiopiste kuuluu lohkoon . $a$ $B$ $a$ $B$

Lause. Yhdistetyn graafin lohkokaavio on puu.

Esimerkki kuvaajasta ja sen lohkojen ja nivelpisteiden kaaviosta
Lähdekaavio
Alkuperäisen kaavion lohkojen ja nivelpisteiden kuvaaja

Useat polut ovat itsenäisiä tai disjunkteja , jos mikään niistä ei sisällä toisen sisäpistettä.

-Yhteyden määritelmä liittyy kärkien poistamiseen. Ehkä seuraava määritelmä on havainnollistavampi: graafi on -kytketty, kun mitkä tahansa kaksi sen kärkeä voidaan yhdistää itsenäisillä poluilla. Nämä kaksi määritelmää ovat samanarvoisia, ne ovat saman ominaisuuden kaksoisformulaatioita.

k

k

k

k

Klassinen Menger -lause on yksi graafiteorian peruskivistä. Lause (Menger, 1927). Kaikille graafin kärkipisteiden osajoukolle ja pisteestä erottuvien pisteiden vähimmäismäärä on yhtä suuri kuin riippumattomien polkujen enimmäismäärä välillä - .

A

B

A

B

A

B

Globaali versio Mengerin lauseesta. (i) Graafi on -kytketty, jos ja vain jos sen kahden kärjen välillä on itsenäisiä polkuja.

k

k

(ii) Graafi on reunakytketty silloin ja vain, jos minkä tahansa sen kahden kärjen välillä on reuna-hajaantuneita polkuja.

k

k

Seuraavassa kuvassa on graafi, jonka kaksi ei vierekkäistä valkoista kärkeä voidaan erottaa poistamalla vähintään kaksi pistettä. Mengerin lauseesta seuraa, että suurin määrä riippumattomia polkuja näiden kärkien välillä on 2.

Kaavio kuvaamaan Mengerin lausetta
Valkoisia pisteitä erottaa vähintään kaksi kärkeä, ja valkoiset kärjet voidaan yhdistää enintään kahdella itsenäisellä polulla.

Planar graphs ( englanniksi planar graphs )

On toivottavaa, että paperille piirretty kaavio havaitaan mahdollisimman helposti. Yksi tapa vähentää monien linjojen kaaosta on välttää niiden ylittämistä. Onko mahdollista piirtää graafia siten, että reunat eivät leikkaa, eli leikkaavat vain yhteiset päätypisteet [80] [81] [82] ?

Tasograafi on graafi, joka on piirretty tasolle ilman risteäviä reunoja, eli reunat leikkaavat vain yhteisissä päätypisteissä.

Tasokuvaajan pinta on yksi avoimista alueista, joka syntyy, kun kuvaaja poistetaan tasosta. Ulkopinta on kaavion ainoa rajaton pinta; muita kasvoja kutsutaan sisäisiksi . Lause. Tasaisella metsällä on vain yksi kasvo - ulompi. Lause ( Eulerin kaava , 1736). Jokaiselle yhdistetylle tasograafille, jossa on kärkipisteitä, reunoja ja kasvoja, kaava on tosi

n

m

l

{\näyttötyyli n-m+l=2}

. Eulerin kaavan seuraus. Tasograafissa, jossa on vähintään kolme kärkeä, on enintään reunat.

3n-6

Tasokaavio, Eulerin kaava ja kasvot
Alkuperäinen tasograafi: 4 kärkeä, 5 reunaa ja 3 pintaa, ${\näyttötyyli 4-5+3=2}$
Alkuperäisen kaavion kolme pintaa: ulompi (punainen) ja kaksi sisäpuolta

Tasograafi on graafi, joka voidaan piirtää tasolle ikään kuin se olisi tasomainen.

Esimerkiksi täydellinen graafi, jossa on neljä kärkeä, on tasomainen.

K_{4}

Neljän kärjen sisältävän täydellisen graafin tasoisuus
Kaavio piirretty ei-tasomaiseksi $K_{4}$
Kaavio piirretty tasaiseksi $K_{4}$

Kaksi legendaarista kuvaajaa ovat ei-tasoisia:

täydellinen graafi viidellä pisteellä ; $K_{5}$
täydellinen kaksiosainen kaavio . $K_{3},3$

Osoitetaan, että graafi on epätasoinen. Päinvastoin. Oletetaan, että se on tasomainen. Sitten Eulerin kaavan seurauksena sillä on enintään reunat. Mutta siinä on 10 reunaa. Tuloksena oleva ristiriita todistaa, että graafi ei ole tasomainen.

K_{5}

K_{5}

K_{5}

3\cdot 5-6=9

K_{5}

K_{5}

Legendaariset ei-tasokaaviot
Täydellinen graafi, jossa on viisi kärkeä $K_{5}$
Täydellinen kaksiosainen kaavio $K_{{3,3}}$

Graafin reunan supistuminen tarkoittaa reunan poistamista graafista ja tämän reunan päätypisteiden yhdistämistä yhdeksi kärjeksi sen reunojen kanssa.

Kylkiluiden supistuminen
Reunan supistuminen päätepisteillä u ja v

Pontryagin-Kuratovsky-lause (1927, 1930) tai Kuratovskin lause (1930). Graafi on tasomainen silloin ja vain, jos siitä ei saada graafia eikä graafia poistamalla reunat ja kärjet niiden reunoilla ja sitten supistamalla reunoja .

K_{5}

K_{{3,3}}

Esimerkiksi ei-tasoisesta Petersen-graafista voidaan saada samalla tavalla:

graafi supistamalla pienet ulkoreunat, jotka on suunnattu graafin keskustaan: 0-5, 1-6, 2-7, 3-8, 4-9; $K_{5}$
kuvaaja seuraavan animaation mukaisesti. $K_{{3,3}}$

Todistus Petersenin graafin epätasaisuudesta
Graafin saaminen Petersen-graafista $K_{{3,3}}$

Väritys ( englantilainen väritys )

Kuinka monella värillä voidaan värittää maat kartalla niin, että vierekkäisillä mailla on eri värit? Kuinka monta päivää eduskunnan valiokunta istuu, jos kukin valiokunta kokoontuu yhden päivän ja jotkut kansanedustajat toimivat useammassa kuin yhdessä valiokunnassa? Mikä on koulun aikataulun vähimmäispituus, jos tiedetään, kuinka usein kukin opettaja opettaa kussakin luokassa [83] [84] ?

Graafin väritys tai graafin kärkiväritys on graafin kärkien värjäystä siten, että vierekkäisillä pisteillä on eri väri.

Graafisen värityksen esimerkkejä
Täydellinen kaavion väritys $K_{4}$
Täydellinen kaavion väritys $K_{6}$
Kreivi Petersenin värityssivu

Graafin k -värjäys tai pisteen k -väritys graafin k -väritys eli k -värittävyys on graafin kärkiväritys k värissä .

Erilainen k - 5 kärjen tähtigraafin väritys
Tähtikaavio, jossa on 5 pistettä, jotka on väritetty kahdella värillä
Tähtikaavio, jossa on 5 kärkeä, jotka on väritetty 3 värillä
Tähtikaavio, jossa on 5 pistettä, jotka on väritetty 4 värillä

Graafin kromaattinen luku tai graafin kärkikromaattinen numero eli k - kromaattisuus on minimi k , jolle graafilla on k -väritys. Nimitys:.

\chi

Esimerkiksi graafi on 1-kromaattinen, kun siinä on vähintään yksi kärki ja ei kulmia. Täydellinen graafi on n -kromaattinen. Tähtigraafi, jossa on 5 kärkeä, on 2-kromaattinen. Ja kaikki tähtikaaviot ovat 2-kromaattisia. Lisäksi graafi on kaksiosainen , jos ja vain jos se on 2-kromaattinen.

K_n

Lause. Graafille, jossa on m reunaa

\chi \leqslant {\frac {1}{2}}+{\sqrt {2m+{\frac {1}{4}}}}

. Todiste. Olkoon kaavio -värinen. Sitten kahdelle värille on vähintään yksi reuna, jonka päät on värjätty näillä väreillä. Tällaisia reunoja on siis vähintään yhtä monta kuin , eli . Ratkaisemalla epäyhtälön suhteessa , saamme lauseen väitteen.

\chi

{\frac {1}{2}}\chi (\chi -1)

m\geqslant {\frac {1}{2}}\chi (\chi -1)

\chi

Neljän värin lause. Mikä tahansa tasograafi on 4-värinen.

Ehkä tämä on ainoa tulos graafiteoriasta, joka väittää olevansa kuuluisa kaikkialla maailmassa. Tästä seuraa, että jokainen maantieteellinen kartta voidaan värittää enintään neljällä värillä, jotta naapurimaiden värit vaihtelevat. Tällä hetkellä tämän lauseen todistus on monimutkainen tietokoneluonteinen.

Maantieteellisen kartan väritys 4 värillä
Kartta Venäjän federaation aiheista , väritetty neljällä värillä

Seuraavan heikentyneen väitteen todistaminen on paljon helpompaa. Viiden värin lause. Mikä tahansa tasograafi on 5-värinen. Myös seuraava väite on laajalti tunnettu. Lause (Gröch, 1959) . Mikä tahansa tasograafi ilman kolmioita on 3-väritettävä.

Tasokaavion väritys ilman kolmioita 3 värillä
Bidiakis- kuution 3-värjäys , esimerkki tasograafista ilman kolmioita
Tasograafin 3-värjäys ilman kolmioita

Graafin reunojen värjäys on graafin reunojen värjäys siten, että vierekkäiset reunat ovat erivärisiä.

Esimerkkejä graafien reunojen värjäyksestä
Koko kaavion reunojen väritys $K_{4}$
Koko kaavion reunojen väritys $K_{8}$
Petersen-graafin reunojen väritys

Graafin reunan k -värjäys eli reunan k -värityvyys on graafin reunaväritys k värissä.

Täydellisen graafin, jossa on 4 huippua, eri reunan k -värjäys
Koko kaavio on reunaväritetty 3 värillä $K_{4}$
Täydellinen kaavio on reunaväritetty 4 värillä $K_{4}$
Täydellinen kaavio on reunaväritetty 5 värillä $K_{4}$

Graafin kromaattinen indeksi tai graafin reunan kromaattinen luku tai reunan k - kromaattisuus on minimi k , jolle graafilla on reunan k -värjäys. Nimitys:.

\chi '

Graafin kromaattiselle luvulle on todistettu vain hyvin karkeita arvioita, kun taas graafin kromaattiselle indeksille se on joko graafin kärkien maksimiaste tai .

\chi

\chi '

\Delta

\Delta +1

On selvää, että mille tahansa kaaviolle .

\chi '\geqslant \Delta

Lause ( König , 1916). Jokaiselle kaksiosaiselle graafille .

\chi '=\Delta

Lause (Vizing, 1964) . Kaikille kaavioille.

\Delta \leqslant \chi '\leqslant \Delta +1

Viziningin lause jakaa äärelliset graafit kahteen luokkaan: ottaa ja ottaa .

\chi '=\Delta

\chi '=\Delta +1

Eri luokkien kaavioiden reunojen värjäys
Täydellisessä kaaviossa on $K_{4}$ $\chi '=\Delta =3$
Täydellisessä kaaviossa on $K_{3}$ $\chi '=\Delta +1=3$

Flows ( englanniksi flows )

Graafia voidaan pitää verkkona, kun reunat kuljettavat jonkin verran virtausta, kuten veden, sähkön tai datan virtausta ja niin edelleen. Miten tällainen tilanne mallinnetaan matemaattisesti [85] [86] ?

Joukon osio on joukko pareittain hajallaan olevia osajoukkoja, joiden yhdistäminen antaa koko joukon.

Esimerkkejä asetetuista osioista
Joukon jakaminen 6 osajoukkoon
Joukon jakaminen 7 osajoukkoon

Graafin leikkaus on joukko graafin kaikkia reunoja, jotka leikkaavat jonkin osion kaikista graafin kärkipisteistä kahdeksi joukoksi - osion sivuilla, eli leikkauksen kunkin reunan päätypisteet ovat osion eri puolille. On selvää, että osion sivut määrittävät yksiselitteisesti leikkauksen. Sidos tai kocycle on ei-tyhjä leikkaus graafissa, joka on minimaalinen reunojen lukumäärän suhteen , eli kun mikä tahansa määrä reunoja poistetaan leikkauksesta, leikkaus lakkaa olemasta leikkausta. Seuraavassa esimerkissä 5 reunan leikkaus ei ole minimileikkaus, koska 3 reunan poistaminen johtaa oikealla näkyvään vähimmäisleikkaukseen.

Esimerkkejä kaavion leikkauksista
5 reunan leikkaus 6 reunan kaaviossa (ei sidosta)
2-reuna leikkaus samassa kaaviossa (sidos)

Kaavion vuo on joukko kokonaislukuja , jotka on määritetty verkon (kaavion)kullekin järjestetyllevierekkäisten solmujen (pisteiden) $f(x,y)$ $(x, y)$

virtaus on antisymmetrinen ; $f(x,y)=-f(y,x)$
solmuissa, joissa virtaus ei tule verkkoon tai poistu siitä, ensimmäinen Kirchhoffin sääntö täyttyy , jossa summaus suoritetaan kaikille viereisille . $x$ $\sum f(x,y)=0$ $y$ $x$

Lähde on solmu, jossa virtaus tulee verkkoon. Nimitys: .

s

Nielu on solmu, jossa virta poistuu verkosta. Nimitys: .

t

Esimerkki virtauksesta, jossa on lähde s ja nielu t kaaviossa
Vuokaaviossa ei ole (Kirchhoffin sääntö ei täyty pisteiden u ja v osalta)
Virtaus kaaviossa

Virtausteoria:

simuloi todellisia virtauksia;
on vuorovaikutuksessa muiden graafiteorian alojen kanssa (etenkin liitettävyyden ja värjäysten kanssa).

Multigrafin reunaa ei määrittele yksiselitteisesti pari tai .

(x, y)

(y,x)

Multigrafin suunnattu reuna on kolmio , jossa on multigrafin kärjestä alkava ja kärkeen päättyvä reuna .

{\näyttötyyli (e,x,y)}

e

x

y

Reunassa c on kaksi suuntaa ja . Silmukalla on yksi suunta .

e

x\ney

{\näyttötyyli (e,x,y)}

{\näyttötyyli (e,y,x)}

{\näyttötyyli (e,x,x)}

Graafisen kierto on funktio, joka:

f(e,x,y)

(F1) kierto on antisymmetrinen kaikille graafin suunnatuille reunoille ;

f(e,x,y)=-f(e,y,x)

{\näyttötyyli (e,x,y)}

x\ney

(F2) kaikissa solmuissa täyttyy ensimmäinen Kirchhoffin sääntö , jossa summaus suoritetaan kaikille solmuille .

v

\sum f(e,v,w)=0

w

v

Lause. Liikkeessä kokonaisvirtaus minkä tahansa osan läpi on nolla:

\sum f(e,v,w)=0

, jossa summaus menee graafin mielivaltaisen osan kaikkien reunojen yli.

{\näyttötyyli (e,v,w)}

Esimerkki kierrätyksestä kaaviossa (ei lähteitä tai nieluja)
Kiertograafissa ei ole (pisteille s, t ja v Kirchhoffin sääntö ei täyty)
Kierto kaaviossa
Kierroksessa virtaus minkä tahansa leikkauksen läpi on 0

Kuvaajan kapasiteettifunktio tai graafin reunojen kapasiteetti on joukko luonnollisia lukuja (nollalla), jotka on määritetty monigraafin jokaiselle suunnatulle reunalle.

Kuvaajan kapasiteettifunktio määritellään itsenäisesti reunan molemmille suunnille.

Esimerkki kaistanleveydestä kaaviossa
Kaavio lähteellä s ja nielulla t. Suunnattujen reunojen kapasiteetit on ilmoitettu

Verkko on multigrafi, jossa on kaksi erillistä solmua (kärkipistettä)jakapasiteettifunktiojokaisessa suunnatussa reunassa.

s

t

c(e,x,y)

{\näyttötyyli (e,x,y)}

Verkkoleikkaus on verkon multigrafin leikkaus siten, että valitut solmut sijaitsevat leikkauksen eri puolilla.

s

t

Verkkoleikkauksen kapasiteetti on summa , jossa summa menee verkon kaikkien reunojen yli .

{\näyttötyyli \sum c(e,v,w)}

{\näyttötyyli (e,v,w)}

Verkon virtaus on reaaliarvoinen funktio verkossa siten, että:

f(e,x,y)

(F1) virtaus on antisymmetrinen kaikille verkon (graafin) suunnatuille reunoille ;

f(e,x,y)=-f(e,y,x)

{\näyttötyyli (e,x,y)}

x\ney

(F2') kaikissa solmuissa (pisteissä) paitsi ja , ensimmäinen Kirchhoffin sääntö täyttyy , jossa summaus suoritetaan kaikille ;

v

s

t

\sum f(e,v,w)=0

w

v

(F3) verkon kaikille suunnatuille reunoille .

f(e,x,y)\leqslant c(e,x,y)

{\näyttötyyli (e,x,y)}

Verkon katkaisuvirran arvo on summa , jossa summa menee verkon kaikkien reunojen yli .

{\näyttötyyli \sum f(e,v,w)}

{\näyttötyyli (e,v,w)}

Verkon katkaisuvirran arvo on sama kaikille verkkokatkoille ja sitä kutsutaan verkon virtausarvoksi . Lause (Ford, Fulkerson, 1956) . Missä tahansa verkossa maksimivirtaus on yhtä suuri kuin leikkausten pienin läpijuoksu.

Esimerkki verkon maksimivirtauksesta
Verkko lähteen s ja nielun t kanssa. Kullekin suunnatulle reunalle on määritetty virtaus (1. numero) ja suoritusteho (2. numero). Virtaus minkä tahansa osan läpi on suurin ja yhtä suuri kuin 18 - osien pienin läpijuoksu

Extremal teoria muokkaa _

Se, mikä reunatiheys tarvitaan tietyn aligraafin olemassaoloon, on tyypillinen graafien äärimmäinen ongelma. Takaako riittävän korkea keskimääräinen kärkien aste tai suuri kromaattinen luku , että haluttu alirakenne esiintyy varmasti graafissa? Mikä on suurin mahdollinen määrä reunoja, jotka -vertex-graafilla voi olla ilman toista, pienempää graafia aligraafina [87] [88] ? $n$

Ekstreemigraafi — tietylle luonnolliselle luvulleja graafilletämä on-vertex-graafi, jossa on suurin mahdollinen määrä reunoja ja joka ei sisällä aligraafia:. Tämä reunojen enimmäismäärä on merkitty. $n$ $H$ $n$ $G$ $H$ $G\nsupseteq H$ ${\näyttötyyli \operaattorin nimi {ex} (n,H)}$

Maksimaalinen graafi - tietylle luonnolliselle luvulle ja graafille on -vertex-graafi , joka on sellainen, että , mutta johon on lisätty uusi reuna .

n

H

n

G

G\nsupseteq H

G\supseteq H

On selvää, että äärimmäinen graafi on maksimaalinen. Mutta ei päinvastoin, kuten alla olevasta kuvasta näkyy.

Esimerkki äärimmäisestä graafista ja maksimaalisesta ei-äärimmäisestä graafista
Täydellinen 3. asteen kaavio $K_{3}$
4. asteen äärimmäinen graafi täydelliselle graafille $K_{3}$
Suurin, mutta ei äärimmäisen luokan 4 kaavio $K_{3}$

$r$ -Osainen graafi tai moniosainen graafi on graafi, jonka kärkijoukot voidaan jakaaosajoukkoihin , jotka ovat: $r$

kunkin reunan päätypisteet ovat eri suhteissa;
yhden osan kärjet eivät ole pareittain vierekkäisiä.

Täydellinen -osittainen graafi

r

on-osainen graafi, jossa jokainen kaksi kärkeä eri osista on vierekkäin. Nimitys:.

r

K_{n_{1},n_{2},\dots ,n_{r))

Esimerkki kaksiosaisista kaavioista
Epätäydellinen kaksiosainen kaavio
Täydellinen kaksiosainen kaavio $K_{{3,3}}$

Esimerkki 3-osaisista kaavioista
Epätäydellinen 3-osainen kaavio
Täydellinen 3-osainen kaavio $K_{3,2,2}$

Turana- graafi on-vertex-graafi, jolla on seuraavat ominaisuudet: $n$

tämä on osittainen kuvaaja ; $r$ $r\leqslant n$
osakkeiden kärkien lukumäärä eroaa toisistaan enintään 1.

Merkintä: Turana-graafissa on reunat.

T_{r}(n)

t_{r}(n)

Turan-graafi on tiheä (eli lähellä täydellistä graafia), koska siinä on lähellä reunoja, tarkemmin

T_{r}(n)

n^{2}

t_{r}(n)\leqslant n^{2}{\frac {r-1}{2r))

, ja tasa-arvo saavutetaan jakamalla .

r

n

Lause (Turan, 1941) . Turan-graafion ainoa äärimmäinen graafi funktioilleja, ja.

T_{r-1}(n)

n

{\näyttötyyli K_{r))

\operaattorin nimi {ex} (n,K_{r})=t_{r-1}(n)

Esimerkki kaavioista, jotka eivät ole Turan-kaavioita
Epätäydellinen kaksiosainen kaavio
Täydellinen kaksiosainen kaavio , mutta osien koko vaihtelee kahdella $K_{5,3}$

Esimerkki Turan-kaaviosta
Täydellinen kaksiosainen graafi : Turana-graafi $K_{{3,3}}$ $T_{2}(6)$
Täydellinen 4-osainen laskenta : Turana-laskenta $K_{4,3,3,3}$ $T_{4}(13)$

Äärettömät kaaviot _ _

Ääreiden graafien tutkiminen on houkuttelevaa, mutta tämä graafiteorian osa jätetään usein huomiotta. Terminologia on yhtäpitävä äärellisten graafien terminologian kanssa, lukuun ottamatta täysin uusia äärettömien graafien käsitteitä. Tyypillisimpiä tällaisia käsitteitä esiintyy jo "äärettömyyden minimissä", kun graafissa on vain laskettava määrä pisteitä ja vain äärellinen määrä särmiä pisteissä [89] .

Paikallisesti äärellinen graafi on graafi, jossa äärellinen määrä kulmia suppenee kussakin kärjessä.

Säde on graafi, jossa on äärettömät kärkijoukot ja reunat, jotka on numeroitu seuraavasti:

\{x_{0},x_{1},x_{2},\dots \},\{x_{0}x_{1},x_{1}x_{2},x_{2}x_ {3},\pisteet\}.

Kaksoisäde on graafi, jossa on äärettömät kärkijoukot ja reunat, jotka on numeroitu seuraavasti:

\{\dots ,x_{-1},x_{0},x_{1},\dots \},\{\dots ,x_{-1}x_{0},x_{0}x_{ 1},x_{1}x_{2},\pisteet\}.

Kaksoispalkki esimerkki
Ääretön graafi, jossa on laskettava määrä pisteitä, 2 reunaa konvergoi jokaisessa kärjessä

On selvää, että isomorfismiin asti on vain yksi säde ja yksi kaksoisäde. Kaksoisäde, jonka kaikissa kärjeissä kohtaa täsmälleen kaksi reunaa, on ääretön 2-säännöllinen yhdistetty graafi. Polku on joko viimeinen polku tai säde tai kaksoisäde. Häntä on säteen tai kaksoispalkin osa. Säteellä on äärettömän monta häntää, jotka eroavat vain alkupäässä. Harjanne on säteen liitto, jossa on ääretön määrä ei-leikkaavia äärellisiä polkuja, joilla on säteen ensimmäinen kärki. Kamman hampaat ovat kamman viimeisten polkujen viimeiset kärjet.

kampa esimerkki
Kampa, jossa valkoiset hampaat ja palkki $R$

Königin Lemma äärettömällä polulla . Päästää:

graafi - äärettömän määrän ei-leikkaavia ei-tyhjiä äärellisiä joukkoja ; $V_{0},V_{1},V_{2},\dots$
jokaisella pisteellä osoitteesta at on naapuri kohteesta . $v$ $V_{n}$ $n\geqslant 1$ $f(v)$ $V_{n-1}$

Sitten kuvaaja sisältää säteen c kaikille .

v_{0}v_{1}v_{2}\dots

v_{n}\in V_{n}

n

Königin Lemma äärettömällä polulla
Kuva Königin äärettömän polun lemmasta

Todiste. 1. On olemassa ääretön joukko äärellisiä polkuja, joiden muoto päättyy numeroon . Koska se on äärellinen, niin siellä on sellainen kärki , jossa äärettömän monta tällaista polkua päättyy.

vf(v)f(f(v))\dots

V_{0}

V_{0}

v_{0}

V_{0}

2. Äärettömän monella polulla, joka päättyy numeroon, on toiseksi viimeinen kärkipiste . Polkuja on äärettömän monta , ja siksi tietysti on sellainen kärkipiste , joka kuuluu äärettömään joukkoon sellaisia polkuja.

v_{0}

V_{1}

V_{1}

v_{1}

V_{1}

3. Äärettömän monen läpi kulkevan polun kärkipiste on , joten osoitteessa on kärkipiste , joka kuuluu näiden polkujen äärettömään joukkoon.

v_{1}

V_{2}

v_{2}

V_{2}

4. Ja niin edelleen loputtomiin. Rakennettu ääretön palkki .

v_{0}v_{1}v_{2}\dots

Tämän äärettömän polun lemman sovellukset perustuvat siihen tosiasiaan, että laskettavaa graafia voidaan pitää äärettömänä jaksona äärellisiä aligraafia.

Kuvaajan loppu ongraafin säteidenekvivalenssiluokkaGraafin kaksi sädettä ovat ekvivalentteja, jos sen jälkeen, kun graafista on poistettu äärellinen kärkijoukko, molemmilla säteillä on häntä samassayhdistetyssä komponentissa.

Määritellään tikkaiden päät , jotka ovat äärettömät kahdessa suunnassa. Jokainen tämän graafin säde sisältää kärkipisteitä mielivaltaisesti kaukana joko vasemmalla tai oikealla, mutta ei sekä vasemmalla että oikealla. Nämä kaksi sädetyyppiä muodostavat kaksi ekvivalenssiluokkaa, joten tikkailla on kaksi päätä. Alla olevassa kuvassa kaavion nämä päät on merkitty pisteillä.

2-puolinen päätön portaikko
2-puolinen päätön portaikko, jonka päät on merkitty pisteillä

Puun päät ovat erityisen yksinkertaisia :

kaksi puusädettä ovat samanarvoisia, jos ja vain jos niillä on yhteinen häntä;
jokaista puun kiinteää kärkeä kohden jokainen pää sisältää täsmälleen yhden säteen, joka alkaa kyseisestä kärjestä.

Jopa paikallisesti rajallisella puulla voi olla jatkumo päitä. Esimerkiksi binääripuu , jonka kärjet on merkitty äärellisillä 0-1 sarjoilla, ja tyhjä joukko on juurina . Silloin tällaisen puun päät vastaavat sen säteitä, jotka alkavat juuresta ja siten äärettömien sekvenssien 0-1 jatkumoa.

\emptyset

\emptyset

Esimerkki binaaripuusta
Binääripuu, jolla on jatkumo päitä, yksi jokaiselle äärettömälle sekvenssille 0-1

Ramseyn kaavioille [ edit

Sisältääkö jokainen riittävän suuri graafi joko täydellisen graafin vai indusoidun komplementin ? Huolimatta samankaltaisuudesta äärimmäisten ongelmien kanssa, kun ne etsivät globaalien oletusten paikallisia seurauksia, viimeinen kysymys johtaa hieman toisenlaiseen matematiikkaan. Itse asiassa Ramseyn teorian lauseilla ja todistuksilla on enemmän yhteistä samojen algebran tai geometrian tulosten kanssa . Graafeiden kieli on luonnollista Ramseyn ongelmissa, ja aineistossa on erilaisia ideoita ja menetelmiä, jotka riittävät välittämään tämän teorian viehätyksen kokonaisuutena [90] [91] [92] ? ${\näyttötyyli K_{r))$ ${\displaystyle {\overline {K_{r))))$

Graafin komplementti on graafi, jolla on:

kärkijoukko on sama kuin alkuperäisen graafin kärkijoukko;
kärjet on yhdistetty reunalla silloin ja vain, jos niitä ei ole yhdistetty reunalla alkuperäisessä graafissa. Kuvaajan nimitys : . $G$ $\overline{G}$

Täydellisen graafin komplementti on täysin irrallinen graafi , joka sisältää vain pisteitä.

{\näyttötyyli K_{r))

{\displaystyle {\overline {K_{r))))

Kaaviot ja niiden täydennykset
Neliö (vasemmalla) ja sen täydennys (oikealla)
Täydellinen kaavio $K_{6}$
Lisäys ${\displaystyle {\overline {K_{6))))$

Itseään täydentävä graafi on graafi, joka on isomorfinen komplementtinsa kanssa. Pienimmät ei-triviaalit itsetä täydentävät graafit sisältävät 4 ja 5 kärkeä.

Pienimmät ei-triviaalit itseään täydentävät kaaviot
Itseään täydentävä graafi, jossa on 4 kärkeä
Itseään täydentävä graafi, jossa on 5 pistettä
Itseään täydentävä graafi, jossa on 5 pistettä

Ramseyn ongelma on tunnettu palapeli:

todistaa, että kuuden ihmisen joukossa on aina joko kolme pareittain tuttua tai kolme pareittain vierasta.

Ramseyn ongelman muotoilu graafiteoriassa:

graafin kuusi kärkeä ovat ihmisiä, reunat ovat tuttavia. Todista, että on joko kolme kärkeä, jotka ovat pareittain yhdistettyjä reunoilla, tai kolme pistettä, jotka eivät ole pareittain kytkettyjä.

Tarkka muotoilu käyttämällä graafin komplementtia. Lause. Mikä tahansa graafi, jossa on kuusi kärkeä, sisältää joko kolmion tai sen komplementti sisältää kolmion. Todiste. 1. Olkoon graafi , jossa on kuusi kärkeä. Ota mikä tahansa sen huippupisteistä . Vertex on yhdistetty reunalla mihin tahansa viidestä muusta kärjestä joko sisään tai sisään . Siksi, ilman yleisyyden menetystä, oletetaan, että se on kytketty kärkipisteisiin .

G

v

v

G

\overline{G}

v

{\displaystyle u_{1},u_{2},u_{3))

G

2. Jos mitkä tahansa kaksi kärkeä on yhdistetty reunalla, niin c on kolmio . Jos kaksi kärkiä ei ole yhdistetty reunalla, ne muodostavat kolmion vuonna .

{\displaystyle u_{1},u_{2},u_{3))

v

G

{\displaystyle u_{1},u_{2},u_{3))

\overline{G}

Lauseen yleistys. Lause (Ramsey, 1930) . Jokaiselle luonnolliselle luvulle on olemassa luonnollinen luku, joka sisältää graafin, jolla on vähintäänkärkipisteet tai sen täydennys.

r

n

n

{\näyttötyyli K_{r))

Ramseyn lauseen muotoilussa on kätevää käyttää väritystä:

jokaiselle täydelliselle graafille on olemassa täydellinen graafi , jossa mikä tahansa sen kaksivärinen reunaväritys sisältää yksivärisen . ${\näyttötyyli K_{r))$ $K_n$ ${\näyttötyyli K_{r))$

Ramseyn luku on pieninRamseyn lauseessaannettuNimitys:.

n

r

R(r)

Ramseyn lauseen standarditodiste sisältää Ramseyn luvun ylärajan: . Todennäköisyyspohjaisella menetelmällä voit löytää alemman arvion : .

{\displaystyle R(r)\leqslant 2^{2r-3))

{\displaystyle R(r)\geqslant 2^{r/2))

Esimerkiksi :

R(3)=6

Ramseyn ongelman ratkaisusta seuraa, että ; $R(3)\leqslant 6$
todistetaan se . Riittää, kun annetaan yksi esimerkki graafista, jossa on 5 kärkeä ja joka ei täytä Ramseyn lausetta . Tässä yllä esitetyssä itseään täydentävässä viisikulmiossa on 5 kärkeä, eikä siinä ole kolmioita, eikä myöskään kolmioita sen komplementissa, joka vastaa sitä; $R(3)>5$ $K_{3}$
$R(3)\leqslant 6$ ja , eli . $R(3)>5$ $R(3)=6$

Kuva kaavasta R(3) = 6. Punaiset reunat ovat kuvaaja, siniset ovat sen komplementteja
Kuvaaja 6 kärjellä, on vain punaisia kolmioita
Kuvaaja 6 kärjellä, on vain sinisiä kolmioita
Kaavio, jossa on 5 huippua, ei punaisia tai sinisiä kolmioita

Ramseyn lause pätee koko graafin lisäksi myös mille tahansa graafille yksinkertaisesti siksi, että se on täydellisen graafin alagraafi , jossa on pisteiden lukumäärä . ${\näyttötyyli K_{r))$ $H$ $H$ $K_{h}$ $h$ $H$

Minkä tahansa graafin Ramsey-luku on pienin luonnollinen luku , jonka mikä tahansa -vertex-graafi tai sen komplementti sisältää . Nimitys: .

H

n

n

H

R(H)

Jos graafissa on vähän reunoja, niin se on helpompi sisällyttää toiseen graafiin, ja voimme odottaa , missä on pisteiden lukumäärä .

R(H)<R(h)=R(K_{h})

h

H

Yleistetään vähän lisää. Graafiparin Ramsey-luku ja on pienin luonnollinen luku siten, että mille tahansa -vertex-graafille joko itse graafi sisältää tai sen komplementti sisältää . Merkintä: , täydellisille kaavioille .

H_1

H_2

n

n

H_1

H_2

R(H_{1}, H_{2})

R(K_{r},K_{s})\equiv R(r,s)

On selvää, että .

R(H,H)=R(H)

R(r,r)=R(r)

Useimmissa kaavioissa tunnetaan vain erittäin karkeat arviot Ramsey-luvuista; tarkat ei-triviaalit Ramsey-luvut tunnetaan vain harvoista kaavioista. Esimerkiksi , , , .

R(3)=6

R(4)=18

R(3,4)=R(4,3)=9

R(4,5)=R(5,4)=25

Kuva kaavasta R(3, 4) = 9. Punaiset reunat ovat kuvaaja, siniset ovat sen komplementteja
Graafi, jossa on 9 kärkeä, jotkut punaisia , ei sinisiä $K_{3}$ $K_{4}$
Graafi, jossa on 9 pistettä, ei punaisia , vain sinisiä $K_{3}$ $K_{4}$
Kaavio, jossa on 8 pistettä, ei punaista tai sinistä $K_{3}$ $K_{4}$

Hamiltonin syklit _ _

Ongelma siitä, sisältääkö kuvaaja suljetun polun, joka kulkee kunkin reunan läpi täsmälleen kerran, on helppo ratkaista käyttämällä Eulerin yksinkertaista lausetta (1736). Paljon vaikeampi on sama kysymys kärkipisteistä : milloin graafi sisältää suljetun polun, joka kulkee kunkin kärjen läpi tasan kerran [93] [94] [95] ?

Hamiltonin sykli on suljettu polku, joka kulkee graafin jokaisen kärjen läpi tarkalleen kerran.

Hamiltonin graafi on graafi, jolla on Hamiltonin sykli. On selvää, että jokaisessa Hamiltonin graafin kärjessä on vähintään kaksi reunaa.

Esimerkkejä Hamiltonin sykleistä
Hamiltonin kierto tasomaisella dodekaedrilla
Hamiltonin sykli tilavuusdodekaedrissa

Lause. Mikä tahansa Hamiltonin graafi on kaksinkertainen. Toisin sanoen hamiltonilaisuuden välttämätön edellytys on olla kaksinainen. Jokainen kaksoisliitetty graafi ei ole Hamiltonin.

Esimerkkejä yksittäin yhdistetyistä kaavioista
Kreivi "Dart" ei-hamiltonilaisia
Laske "kalat" ei-hamiltonilaisille

Theta-graafi on graafi, joka sisältää vain seuraavat kärjet:

kaksi kärkeä, jotka sisältävät kolme reunaa;
kärjet, joilla on kaksi reunaa.

Toisin sanoen theta-graafissa on kaksi kärkeä, joiden aste on 3, ja kolme ei-leikkautuvaa yksinkertaista polkua, jotka yhdistävät nämä kaksi kärkeä, kunkin pituus vähintään 2.

Theta Graph -esimerkkejä
Yksinkertaisin theta-graafi on täydellinen kaksiosainen graafi $K_{2,3}$
Theta-graafi, jossa on 7 pistettä
Theta-graafi, jossa on 9 pistettä

Theta-kaavio ei-Hamiltonilaisista. Yksinkertaisin ei-Hamiltonin kaksinkertaisesti yhdistetty graafi on täydellinen kaksiosainen graafi .

K_{2,3}

Lause. Jokaisella ei-Hamiltonin kaksinkertaisesti kytketyllä graafilla on theta-aligraafi. Toisin sanoen theta-aligraafin läsnäolo on välttämätön ehto ei-Hamiltonin olemiselle. Jokainen graafi, jossa on theta-aligraafi, ei ole ei-Hamiltonin. Yksinkertaisin Hamiltonin graafi, jossa on theta-aligraafi, on täydellinen kaksiosainen graafi , johon on lisätty reuna.

K_{2,3}

Yksinkertaisimmat Hamiltonin graafit
Yksinkertaisin Hamiltonin graafi
Yksinkertaisin Hamiltonin graafi, jossa on theta-aligraafi

Edellä on annettu joitain välttämättömiä ehtoja olla hamiltonilainen ja ei-hamiltonilainen . Mitkä olosuhteet voivat olla riittävät Hamiltonian syntymiselle? Vain muutama ehto kerralla.

Lause ( Dirac , 1952). Graafi, jossa on Hamiltonin kärkipisteet, jos:

n\geqslant 3

1) sen pisteiden minimiaste riippuu n:stä;

\delta

2) .

\delta \geqslant n/2

Tämä on riittävä ehto Hamiltonin syntymiselle. Tämä ehto ei täyty jokaiselle Hamiltonin graafille. Esimerkiksi yksinkertaisimmalle Hamiltonin graafille, jossa on theta-aligraafi, ehto ei täyty.

\delta \geqslant n/2

Kuutiograafi on 3-säännöllinen graafi, eli graafi, jossa täsmälleen 3 reunaa suppenee kussakin kärjessä. Tasograafien osalta Hamiltonin oleminen liittyy neljän värin ongelmaan . Neljän värin lauseen todistamiseksi riittää todistamaan Tate-oletus : millä tahansa 3-liiteisellä tasomaisella kuutiograafilla on Hamiltonin sykli. Hypoteesi ei vahvistunut. Ensimmäisen vastaesimerkin löysi Tutt vuonna 1946.

Vastaesimerkki Titen olettamukselle: Tattan graafi
3-kytkentäinen tasomainen kuutiograafi ilman Hamiltonin sykliä

Lause (Tutt, 1956). Mikä tahansa 4-kytkentäinen tasomainen Hamiltonin graafi.

Esimerkkejä 4-liitetyistä tasokaavioista
4-liitetty tasograafi: oktaedri
5-yhdistetty tasograafi: ikosaedri

Random graphs ( Englanninkieliset random graphs )

Todennäköisyyspohjainen menetelmä mahdollistaa tietyn ominaisuuden omaavan objektin olemassaolon todistamisen seuraavasti: 1) jollekin suuremmalle objektiluokalle määritellään todennäköisyysavaruus, jonka tiedetään olevan ei-tyhjä; 2) näytetään, että haluttu ominaisuus toteutuu satunnaisesti valitulle avaruuselementille positiivisella todennäköisyydellä. Probabilistisen menetelmän ydin on osoittaa ei-konstruktiivinen, että tietty väri on olemassa vai ei [96] [97] [98] .

Todennäköisyyslaskentaa havainnollistaa hyvin seuraava esimerkki: saamme Ramseyn luvulle alhaisemman arvion . $R(k)$

1. Muodostetaan todennäköisyysavaruus. Väritä koko kaavio satunnaisesti , eli värjätä jokainen reuna itsenäisesti punaiseksi tai siniseksi yhtä suurella todennäköisyydellä. Siten todennäköisyys, että reuna tulee punaiseksi, on , ja sininen on myös .

K_n

K_n

K_n

{\frac {1}{2}}=2^{-1}

2^{-1}

2. Määrittelemme satunnaisesti väritetylle tapahtumalle seuraavan tapahtuman: satunnaisesti valittu täydellinen aligraafi on yksivärinen, eli joko punainen tai sininen. Osagraafissa on reunat, joten todennäköisyys, että jo valittu osagraafi on punainen, on , sininen on myös ja yksivärinen on .

K_n

K_k

K_k

{k \choose 2}

K_k

2^{-{k \choose 2}}

2^{-{k \choose 2}}

2^{-{k \choose 2}}+2^{-{k \choose 2}}=2^{1-{k \choose 2}}

Todennäköisyys, että jo valittu osagraafi on yksivärinen, ei riipu . Esimerkiksi todennäköisyys olla yksivärinen on aina yhtä suuri kuin

K_k

n

K_{3}

2^{1-{3 \choose 2}}=2^{1-{\frac {3!}{2!1!}}}=2^{1-{\frac {6}{2 ))}=2^{-2}={\frac {1}{4}}

, todennäköisyys olla samanvärinen on aina

K_{4}

2^{1-{4 \choose 2}}=2^{1-{\frac {4!}{2!2!}}}=2^{1-{\frac {24}{4 ))}=2^{-5}={\frac {1}{32}}

. 3. Lasketaan nyt todennäköisyys, että satunnaisesti valittu osagraafi on yksivärinen. On olemassa useita tapoja valita osakuvaa täydellisestä kaaviosta . Koska tapahtumat osoittautuvat yksivärisiksi näille osagraafille voivat osoittautua toisistaan riippuviksi, niin satunnaisesti valitun osagraafin todennäköisyys muuttua yksiväriseksi on vain niiden todennäköisyyksien summa .

K_k

K_k

K_n

{n \valitse k}

K_n

K_k

{n \choose k}2^{1-{k \choose 2}}

Esimerkiksi todennäköisyys olla enintään yksivärinen

K_{3}

K_{3}

{3 \choose 3}2^{1-{3 \choose 2}}={\frac {3!}{3!0!}}2^{1-{\frac {3!}{2 !1!}}}=2^{1-{\frac {6}{2}}}=2^{-2}={\frac {1}{4}}

, todennäköisyys olla yksivärinen on korkeintaan

K_{3}

K_{4}

{4 \choose 3}2^{1-{3 \choose 2}}={\frac {4!}{3!1!}}2^{1-{\frac {3!}{2 !1!}}}=4\cdot 2^{1-{\frac {6}{2}}}=2^{2}2^{-2}=1

Arvioikaamme Ramseyn luku alhaalta. Jos tarpeeksi pieni annetuksi , niin Ramseyn numero . $n$ $k$ $R(k)>n$

Lemma. Jos , niin .

{n \choose k}2^{1-{k \choose 2}}<1

R(k)>n

Todiste. 1. Olkoon , eli todennäköisyys, että satunnaisesti valittu osagraafi on yksivärinen, on pienempi kuin 1.

{n \choose k}2^{1-{k \choose 2}}<1

K_n

K_k

2. Tällöin todennäköisyys, että kaikki osagraafit eivät ole yksivärisiä, on suurempi kuin nolla: .

K_k

1-{n \choose k}2^{1-{k \choose 2}}>0

3. Toisin sanoen on olemassa 2-väritys ilman monokromaattista , eli .

K_n

K_k

R(k)>n

Lause ( Erdős , 1947). Kaikille luonnollisille Ramsey-numeroille .

k \geqslant 3

R(k)>2^{k/2}

Tämä ala- ja yläraja ovat hyvin lähellä.

R(k)>2^{k/2}

{\displaystyle R(k)\leqslant 2^{2k-3))

Todiste. 1. Kun meillä on:

k = 3

{n \choose k}={n \choose 3}={\frac {n!}{3!(n-3)!}}={\frac {n(n-1)(n-2 )}{6}}<{\frac {n^{3}}{6}}

{\displaystyle 2^{1-{k \choose 2}}=2^{1-{3 \choose 2}}=2^{1-{\frac {3!}{2!1!)}}} = 2^{-2}={\frac {1}{2^{2))))

. Kaikesta mitä meillä on:

n\leqslant 2^{3/2}

{n \choose k}<{\frac {n^{3}}{6}}\leqslant {\frac {2^{9/2}}{6}}={\frac {2^{ 7/2}}{3}}

{n \choose k}2^{1-{k \choose 2}}<{\frac {2^{7/2}}{3}}{\frac {1}{2^{2} }}={\frac {2^{3/2}}{3}}<{\frac {2,83}{3}}<1

. Nyt, lemman mukaan, kaikille , eli .

R(3)>n

n\leqslant 2^{3/2}

R(3)>2^{3/2}

2. Anna nyt . Meillä on:

k\geqslant 4

k!=1\cdot 2\cdot 3\cdot 4\cdot \,\dots \,\cdot k=2\cdot 2\cdot 3\cdot 2\cdot \,\dots \,\cdot k> 2^{k}

. Kaikille laskelmille, kuten :

n\leqslant 2^{k/2}

k = 3

{n \choose k}2^{1-{k \choose 2}}={\frac {1}{k!)}}{\frac {n!}{(nk)!}}2^ { 1-{\frac {k!}{2!(k-2)!}}}<{\frac {n^{k}}{2^{k}}}2^{1-{\frac { k (k-1)}{2}}}\leqslant {\frac {2^{k^{2}/2}}{2^{k}}}2^{1-k^{2}/2 + k/2}=

={\frac {2^{1+k/2}}{2^{k}}}=2^{1-k/2}\leqslant 2^{1-4/2}={\ frac {1}{2}}<1

. Nyt, lemman mukaan, kaikille , eli .

R(k)>n

n\leqslant 2^{k/2}

R(k)>2^{k/2}

Satunnainen graafi on satunnaisesti saadun täydellisen kaavionosagraafi. Jos esimerkiksi kaikki reunatovat satunnaisesti värjätty punaisiksi tai sinisiksi, niin satunnainen graafi on kaikkien punaisten reunojen muodostama aligraafi. On selvää, että satunnaiset kaaviot ovat itsenäisiä tapahtumia. Merkintä: satunnaiskuvaajan todennäköisyyson merkitty. $K_n$ $K_n$ $G$ $P(G)$

Satunnaismuuttuja on ei-negatiivinen reaaliluku jokaisessa satunnaiskaaviossa. Se voi olla esimerkiksi satunnaisen graafin kärkien lukumäärä, liitettävyys, kromaattinen luku ja niin edelleen. Nimitys:.

G

X(G)

Satunnaismuuttujan matemaattinen odotus eli keskiarvo on kaikkien satunnaiskaavioiden todennäköisyyksien painotettu summa:

E(X)=\summa P(G)X(G)

. Matemaattinen odotus on lineaarinen eli yhtäläisyydet

E(X+Y)=E(X)+E(Y)

E(\lambda X)=\lambda E(X)

suoritetaan kahdelle satunnaismuuttujalle ja ja mille tahansa reaaliluvulle .

X

Y

\lambda

Jos matemaattinen odotus eli satunnaismuuttujan keskiarvo on pieni, niin satunnaismuuttujan on oltava pieni monelle satunnaiskaaviolle. Silloin on luonnollista olettaa, että jälkimmäisten joukossa on graafi, jolla on vaadittu ominaisuus. Tämä ajatus on ei-konstruktiivisten olemassaolotodistusten taustalla. Tämän ajatuksen määrällinen ilmaus on seuraava. Markovin eriarvoisuus . Minkä tahansa satunnaismuuttujanja minkä tahansa reaaliluvunosalta epäyhtälö

X\geqslant 0

a>0

P(X\geqslant a)\leqslant {\frac {E(X)}{a))

. Todiste. On selvää, että (summaus suoritetaan kaikissa satunnaisissa kaavioissa )

G

E(X)=\sum \limits _{G}P(G)X(G)\geqslant \sum \limits _{G \atop X(G)\geqslant a}P(G)X(G) )\geqslant

\geqslant \sum \limits _{G \atop X(G)\geqslant a}P(G)a=aP(X\geqslant a)

Alaikäiset, puut ja kaivojen tilaus muokkaa

Yksi syvällisimmistä matemaattisista lauseista, joka syrjäyttää minkä tahansa muun graafiteorian lauseen, on graafin mollilause : mikä tahansa ääretön graafien joukko sisältää kaksi graafia siten, että toinen on toisen ala-aste. Joitakin peruskäsitteitä selitetään alla tämän lauseen lähestymistavoissa, jonka todistus kestää 500 sivua [99] [100] .

Ennakkotilaus tai kvasiorder on refleksiivinen ja transitiivinen suhde joukossa. Nimitys:. $\leqslant$

Täydellinen ennakkotilaus tai oikea kvasijärjestyson ennakkotilaus, jossa mikä tahansaääretönsarja elementtejä sisältää kaksi ennakkotilattua elementtiä, jolloin suurempi elementti seuraa sekvenssin pienempää. Toisin sanoen mikä tahansajoukonsisältää,.

x_{0},x_{1},x_{2},\dots

X

{\displaystyle x_{i}\leqslant x_{j))

i<j

Hyvin ennakkotilatut elementit ovat hyvin ennakkotilatun sarjan elementtejä. Lause. Ennakkotilaus joukolle on valmis, jos ja vain jos sarja ei sisällä seuraavia äärettömiä elementtisarjoja:

pareittain vertaansa vailla olevilla elementeillä;
tiukasti laskeva, eli sekvenssi , jossa tarkoittaa ja . $x_{0}>x_{1}>x_{2}>\dots$ ${\displaystyle x_{i}>x_{j))$ ${\displaystyle x_{i}\geqslant x_{j))$ ${\displaystyle x_{i}\neq x_{j))$

Esimerkkejä. 1. Luonnollisten lukujen joukon jaotuvuusrelaatio on ennalta määrätty ja jopa osittain järjestetty , mutta ei täysin ennakkoon, koska ääretön alkulukujono ei sisällä ennalta määrättyä paria.

\,\vdots\,

2. Kokonaislukujoukon jaettavissa oleva relaatio on ennalta määrätty eikä osittain järjestetty (koska esimerkiksi ja , mutta ) eikä myöskään täysin ennakkotilattu.

2\,\vdots-2

-2\,\vdots \,2

2\neq -2

Jakosuhde
Hasse-kaavio luonnollisten lukujen jaollisuussuhteesta

Graafin osajako tai laajennus tai alajakograafi on graafi, joka saadaan alkuperäisestä jakamalla reunat pisteillä.

Graafin topologinen sivuluku on graafi, jonka alajako on alkuperäisen graafin aligraafi. Topologinen molli säilyttää alkuperäisen graafin aligraafin topologisen muodon.

Topologinen sivuesimerkki
Lähdekaavio $G$
Alajako - alakaavio $H$ $G$
Topologinen graafi vähäinen $H$ $G$

Graafin molli on graafi, joka saadaan alkuperäisestä graafista poistamalla kärkipisteitä ja poistamalla ja supistamalla reunoja. Suhdenimitys- sivullinen:

X

Y

X\preccurlyeq Y

Mikä tahansa graafin aligraafi on sen vähäinen. Jokainen graafi on oma mollinsa.

Pieni esimerkki
Alaikäinen saadaan poistamalla ef ja supistamalla bc

Lause. (i) Mikä tahansa graafin topologinen molli on myös sen (tavallinen) molli. Päinvastoin ei yleensä pidä paikkaansa. (ii) Graafille, jossa on enintään 3 reunaa kussakin kärjessä, mikä tahansa ala-arvo on topologinen molli. Lause. Kaikkien äärellisten graafien joukossa relaatiot, jotka ovat vähäisiä ja topologisia sivuja, ovat osittaisia järjestyksiä .

\preccurlyeq

Hasse-kaavio suhteesta on (topologinen) alaikäinen
Suhde olla neliön (topologinen) molli. Kaikki sivumerkit ovat aligraafia, paitsi kolmio. Kolmio saadaan neliöstä supistamalla kärkeä

Kielletty tai poissuljettu molli tietylle graafin ominaisuudelle on graafi, jonka esiintyminen alapuolena graafissa osoittaa tämän ominaisuuden puuttumisen jälkimmäisestä.

Edellisen lauseen mukaan kiellettyjen alaikäisten joukko on suljettu alaikäisten ottamiseen: jos graafi on kielletty alaikäinen ja , niin graafi on myös kielletty alaikäinen.

G

H\preccurlyeq G

H

Lause. Kielletyt alaikäiset voivat määritellä graafin ominaisuuden, jos ja vain, jos se on suljettu alaikäisten vuoksi. Graafi-ominaisuudet, jotka on suljettu alaikäisten ottamiseen, esiintyvät usein graafiteoriassa. Tunnetuimman esimerkin antaa Pontryagin-Kuratovsky-lause : tasomaisuuden antaa alaikäisten kielto ja .

K_{5}

K_{{3,3}}

Karakterisointi kiellettyjen kaavioiden avulla on hyvä luonnehdinta . Hyvä karakterisointi on graafien ominaisuuden karakterisointi, jonka avulla on helpompi todistaa, että ominaisuutta ei ole olemassa. Vain sen varmistamiseksi, että kaaviolla on jokin ominaisuus, riittää, että kuvaaja kuvataan tietyllä tavalla. Vaikeuksia syntyy kiinteistön puuttumisen todistamisessa. Mutta esimerkiksi kiinteistöön kiellettyjen alaikäisten läsnä ollessa, sen poissaolo voidaan helposti todistaa esittämällä joku kielletty alaikäinen. Lause. Kiellettyjen alaikäisten läsnäollessa on aina olemassa ainutlaatuinen pienin joukko heitä, joiden elementtejä ovat kaikkien kiellettyjen alaikäisten alaikäiset. On selvää, että pienimmästä joukosta kielletyt alaikäiset ovat alaikäisyyteen verrattomia . Seuraava lause sanoo, että mikä tahansa joukko verrattomia kaavioita on äärellinen.

\preccurlyeq

\preccurlyeq

Robertson-Seymour-lause (1986-2004). Äärelliset graafit ovat hyvin ennalta järjestettyjävähäpätöisyyteen nähden.

\preccurlyeq

Seuraus. Mikä tahansa graafien ominaisuus, joka on suljettu alaikäisten ottamisessa, voidaan määritellä rajallisella kiellettyjen alaikäisten joukolla. Vahva versio tästä lauseesta puille on seuraava. Lause (Kruskal, 1960) . Äärilliset puut ovat hyvin ennakkotilattuja topologisen sivuluokan suhteen.

Esimerkki kiellettyjen alaikäisten joukosta
Petersenin perhe , kielletty alaikäisiltä linkittämättömän kaavion upotuksen vuoksi

Jotain lineaarialgebraa muokkaa _

Yksinkertaiset graafien syklit ja reunaleikkaukset perustuvat algebralliseen rakenteeseen, jonka ymmärtämisen saavuttaminen mahdollistaa tehokkaiden ja kauniiden lineaarialgebran menetelmien soveltamisen, mikä puolestaan johtaa graafiteorian ja vastaavien algoritmien syvempään ymmärtämiseen. kaaviot [101] [102] [ 103] [104] .

Graafin kärkiavaruus on joukko graafin kaikkien kärkien joukon kaikista osajoukkoista , jotka on muunnettu vektoriavaruudeksi 2-alkioisen kentän kautta Graafin kärkiavaruuden merkintä $\{0,1\}.$ $G:{\mathcal {V}}(G).$

Tämän avaruuden vektori on graafin kärkien osajoukko :

kahden vektorin summa määritellään osajoukkojen summaksi modulo 2 tai symmetriseksi eroksi tai rengassummaksi ;
vektori on vastakkainen itselleen;
nollavektori on tyhjä pistejoukko;
vektoriavaruuden kanta muodostuu kaikista yksialkioisista osajoukoista - graafin pisteistä. Siksi vektoriavaruuden ulottuvuus on yhtä suuri kuin graafin kärkien lukumäärä.

Lisäystaulukko modulo 2 avaruuden vektoria 4 kärkeä

$\oplus$

Kuvaajan reuna-avaruus on joukko graafin reunajoukon kaikista osajoukkoista, jotka on muunnettu vektoriavaruudeksi 2-alkioisen kentän yli . Kuvaajan reuna-avaruuden merkintä

\{0,1\}.

G:{\mathcal {E}}(G).

Täysin analoginen kärkien avaruuden kanssa. Graafin rakenteen määräävät sen reunat, joten yleensä käsitellään reunojen tilaa. Alla on taulukko syklisen graafin reunaavaruusvektorien modulo 2 -lisäyksestä . Leikatun aliavaruuden elementit ovat sinisten kehysten sisällä, tämän aliavaruuden yhden pohjan kolme elementtiä on korostettu sinisellä. Syklien aliavaruus on tässä tapauksessa leikkausten aliavaruuden aliavaruus ja se koostuu kahdesta elementistä: tyhjästä joukosta ja graafista ; sen elementit on korostettu sinisellä.

{\mathcal {E}}(C_{4})

C_{4}

{\mathcal {B}}(C_{4})

{\mathcal {C}}(C_{4})

C_{4}

Virittävä puu, kuusi sidosta ja graafinen sykli

C_{4}


sininen ylittävä puu	Kuusi joukkovelkakirjalainaa (minimileikkaukset). Yhden pohjan kolme elementtiä on korostettu sinisellä						Kierrä

Summataulukko modulo 2 avaruuden vektoria 4 graafisen reunan

C_{4}

$\oplus$

Graafin sykliavaruus on graafin reuna- avaruuden aliavaruus , jonka muodostavat kaikki graafin yksinkertaiset syklit. Graafisen avaruusmerkintä $G:{\mathcal {C}}(G).$

Toisin sanoen syklien tila kattaa yksinkertaiset syklit, eli se koostuu:

tyhjä sarja;
kaikki kaavion yksinkertaiset syklit;
kaikista summista graafin yksinkertaisten syklien modulo 2.

Lause. Jaksojen avaruus muodostuu myös jaksoista ilman sointuja. Graafin syklomaattinen luku tai syklinen järjestys on graafin sykliavaruuden ulottuvuus. Lause. Yhdistetyn graafin syklomaattinen luku on yhtä suuri kuin graafin minkä tahansa virittävän puun sointujen lukumäärä, eli se on yhtä suuri kuin , jossa on graafin reunojen lukumäärä ja on pisteiden lukumäärä.

m-n+1

m

n

Alla on taulukko modulo 2 -lisäyksestä annetun kaavion sykliavaruusvektoreista , joka näkyy alla yhdessä virittävän puun kanssa. Tämän tilan yhden pohjan kolme elementtiä on korostettu sinisellä.

{\mathcal {C}}(G)

G

Virtaava puu ja kuusi yksinkertaista sykliä tietyn graafin


Kaavion virittävä puu $G$	Annetun graafin kuusi yksinkertaista sykliä. Yhden pohjan kolme elementtiä on korostettu sinisellä

Modulo 2:n sykliavaruusvektorien summaustaulukko

$\oplus$

Graafin leikkausten tai sidosten avaruus on graafin reunojen avaruus, jonka muodostavat tyhjä joukko ja kaikki graafin minimileikkaukset. Graafinen sidosavaruusmerkintä $G:{\mathcal {B}}(G).$

Toisin sanoen leikkausten tila kattaa minimaaliset leikkaukset, eli se koostuu:

tyhjä sarja;
kaikki kaavion minimileikkaukset;
kaikista summista graafin minimileikkausten modulo 2.

Lause. Leikkausten tilaa synnyttävät myös leikkaukset, joiden kahdesta osiojoukosta toinen on eristetty kärki. Kuvaajan leikkausarvo on graafin leikkausavaruuden mitta. Lause. Yhdistetyn graafin leikkausarvo on yhtä suuri kuin graafin minkä tahansa virittävän puun reunojen lukumäärä, eli missä on graafin kärkien lukumäärä.

n-1

n

Alla on taulukko modulo 2 -lisäyksestä annetun kaavion leikkausavaruusvektoreista , joka näkyy alla yhdessä virittävän puun kanssa. Tämän tilan yhden pohjan neljä elementtiä on korostettu sinisellä.

{\mathcal {B}}(G)

G

Virittävä puu ja kymmenen tietyn graafin sidosta

G


Kaavion virittävä puu $G$	Kymmenen sidosta (minimileikkaus) annetusta graafista. Yhden pohjan neljä elementtiä on korostettu sinisellä

Leikkattujen avaruusvektorien lisäystaulukko modulo 2

$\oplus$

Graafiteorian sovellukset

Jo 1800-luvulla käytettiin kaavioita sähkö- ja molekyylipiirien suunnittelussa; matematiikan hauskanpito ja palapelit ovat myös osa graafiteoriaa [105] .

Joitakin graafiteorian ongelmia

Königsbergin siltojen ongelma . Kulje kerrankaikkien siltojen läpi vanhan Königsbergin keskustassa. Leonhard Eulerin vuonna 1736 päivätyssä julkaisussa ratkaisemagraafiteorianensimmäinen tulos (saman julkaisun ensimmäinen lause on, että graafin kärkien asteiden summa on yhtä suuri kuin kaksi kertaa sen reunojen lukumäärä) [ 16] [106] [12] [107] [21] [108] [109] [13] [110] .

Joskus tämä tehtävä siirretään muiden kaupunkien siltajärjestelmään. Esimerkiksi Leningradin kaupungissa vuonna 1940 julkaistiin ongelma 17 sillasta Nevan suulla [110] .

Neljän värin ongelma - onko mahdollista värittää mikä tahansa kartta neljällä värillä niin, että viereisillä mailla on eri värit? Muotoiltu vuonna 1852, vuonna 1977 julkaistiin (ilmoitettiin vuonna 1976) ensimmäinen yleisesti hyväksytty positiivinen todistus tietokoneella [111] [112] [113] [114] [115] [116] [117] [118] .
Dominon ongelma. Kaikki 28 dominoa on yhdistettävä jatkuvaksi (yksinkertaiseksi) ketjuksi siten, että kahden kiven vierekkäisillä puoliskoilla on sama numero. Koska tuplausten läsnäolo ei vaikeuta ongelmaa, domino-ongelma asetetaan myös 21 noppaa varten (ilman tuplaa) yleisyyden menettämättä [21] [22] [119] .
Labyrintin tehtävä. Mene mielivaltaiseen labyrintiin ja käy läpi kaikki sen käytävät [120] [121] .
Kolmen talon ja kolmen kaivon ongelma . Aseta ei-leikkaavat polut kustakin kolmesta talosta jokaiseen kolmeen kaivoon. Tälle ongelmalle, kuten Königsbergin siltaongelmalle, ei ole ratkaisua [122] .
Ritarin liikkeen ongelma . Kävele ritari shakkilaudan ympäri , käy jokaisessa solussa täsmälleen kerran ja palaa alkuperäiseen soluun [123] .
Tehtävä ongelma . Anna yrityksen vaatia useita erilaisia töitä, joista jokainen soveltuu vain osaan ja voi suorittaa enintään yhden työn kerrallaan. Miten tehtävät tulisi jakaa, jotta mahdollisimman monta tehtävää voidaan suorittaa samanaikaisesti? Kaksiosainen graafi auttaa ratkaisemaan ongelman, jossa yhden osan kärjet ovat työntekijät, toisen työt ja jokainen reuna on sopiva työtehtävä [124] .
Kombinatorinen optimointi [125] .

Lyhimmän polun ongelma . Annettu ( suunnattu ) graafi ja jokainen sen reunan (kaari) painotus edustaa aikaa, joka kuluu sen kulkemiseen. Etsi lyhin polku (ajassa) annettujen pisteiden välillä.
Vähimmäisvirittävän puun ongelma . Oletetaan, että useita tietokoneita on liitettävä kiinteisiin paikkoihin tietokoneverkon muodostamiseksi , ja minkä tahansa tietokoneparin välisen suoran yhteyden luomisen kustannukset tunnetaan. Mitä suoria yhteyksiä tulisi rakentaa verkon kustannusten minimoimiseksi?
Steinerin minimaalinen puuongelma . Olkoon yhdistetyn painotetun graafin mielivaltainen kärkien osajoukko . Etsi aligraafi-puu, jonka reunapainojen vähimmäissumma sisältää tietyn osajoukon kaikki kärjet.
Matkamyyjän ongelma (TSP) . Anna myyjän käydä useissa kaupungeissa seuraavan kuukauden aikana. Painot edustavat matkakuluja kunkin kaupunkiparin välillä. Kuinka järjestää vierailut niin, että matkan kokonaiskustannukset saadaan minimoitua? Toisin sanoen, sinun on löydettävä Hamiltonin sykli , jonka reunan kokonaispaino on minimaalinen.
Suurin virtausongelma . Anna veden pumpata putkiverkoston kautta lähteestä viemäriin. Kaaviomalli on verkko, jossa jokainen kaaripaino on vastaavan putkilinjan läpi kulkevan virtauksen yläraja. Etsi suurin virtaus lähteestä nieluun.
Kiinalaisen postimiehen ongelma . Etsi painotetun kaavion kaikkien reunojen vähimmäispainotusjakso, jossa reunojen paino riippuu sovelluksesta (esim. etäisyys, aika, hinta jne.).
Kiinan postimies-ongelma (digrafi). Ajettaessa tietokoneohjelman virta liikkuu eri tilojen välillä ja siirtymät tilasta toiseen riippuvat syötetiedoista. Ohjelmistoja testattaessa haluamme tuottaa syötedataa, jotta kaikki mahdolliset siirtymät testataan.

Ohjelman suoritusvirtaa mallinnetaan digraafilla, jossa kärjet ovat ohjelman tiloja, kaaret ovat siirtymiä ja jokaiselle kaarelle on osoitettu vastaavan siirtymän kutsunimike. Sitten ongelma löytää syötedatan sekvenssi, joka aiheuttaa kaikki siirtymät ja minimoi niiden kokonaismäärän, vastaa kiinalaisen postinkajan minimipituisen suunnatun polun löytämistä.

RNA :n rekonstruoinnin tehtävä . Rekonstruoi tämä RNA-ketju tai täydellinen sarja sopivia RNA-ketjuja saman RNA:n epäjärjestyneiden fragmenttien perusteella.
Numerojonon rekonstruoinnin ongelma. Olkoon tietylle numerosarjalle — merkkijonon numeroiden määrä , — merkkijonon osamerkkijonojen lukumäärä . Kuinka monta eri merkkijonoa vastaa annettuja ja , , ? $f_{i}$ $i$ $f_{ij}$ $ij$ $f_{i}$ $f_{ij}$ ${\näyttötyyli i,j=1,2,\pisteet ,n}$ $f_{ii}=0$

Graafisen isomorfismin ongelma . Kehitä yleinen algoritmi graafin isomorfismin määrittämiseksi tai vaihtoehtoisesti todista, että tällaista algoritmia ei ole olemassa [126] .
Kuvaajan rekonstruktioongelma . Voiko kahdella ei-isomorfisella yksinkertaisella graafilla, jossa on kolme tai useampia kärkeä ja joissa ei ole otsikoita pisteissä, olla sama luettelo aligraafista, joista kukin saadaan poistamalla yksi kärki [127] ?
Riippumattomuusjärjestelmän osajoukon ongelma maksimipainolla. Annetaan ei-negatiivinen paino graafin kullekin reunalle. Etsi riippumattomuusjärjestelmän osajoukko, jonka reunojen painojen enimmäissumma on [128] .
Ongelma vastaamaan maksimipainoa. Edellisen ongelman erikoistapaus [129] .
Maksimointiongelma. Määritä graafista minkä tahansa kärkiparin yhdistävien kärjestä riippumattomien polkujen maksimimäärä [130] .
Minimoimisen ongelma. Määritä graafista minimimäärä pisteitä, jotka jakavat minkä tahansa perchin parin [130] .
Aligraafin homeomorfismin ongelma . Selvitä, sisältääkö ensimmäinen graafi aligraafin, joka on homeomorfinen toisen graafin kanssa [131] .
Klikkiongelma on toinen NP-täydellinen ongelma.
Graafin tasoisuus - onko mahdollista kuvata graafia tasossa risteämättä reunoja (tai vähimmäismäärällä kerroksia, jota käytetään painettujen piirilevyjen tai mikropiirien keskinäisiä liitäntöjä jäljitettäessä).

Graafiteoria sisältää myös useita matemaattisia ongelmia, joita ei ole vielä ratkaistu .

Graafiteorian sovellusten luokitukset

Graafiteorian sovellusten luokittelu matematiikkaan kohdistuvan suhteen asteen mukaan [132] :

matemaattiset kentät: ryhmäteoria , matriisiteoria , numeerinen analyysi , todennäköisyysteoria , topologia , kombinatorinen analyysi ja matemaattinen malli binäärisuhteille ;
ei-matemaattiset alat: fysiikka , kemia , viestintäteoria , tietokonesuunnittelu , sähkötekniikka , konetekniikka , arkkitehtuuri , toimintatutkimus , genetiikka , psykologia , sosiologia , taloustiede , antropologia ja kielitiede .

Graafiteorian sovellusten luokittelu vuorovaikutuksen olennaisuusasteen mukaan [133] [134] :

enemmän materiaalien vuorovaikutuksia ovat erityisesti fyysiset verkot (esim. sähköpiirit ), tiet , orgaaniset molekyylit ;
vähemmän aineellisia vuorovaikutuksia ovat erityisesti ekosysteemit , sosiologiset suhteet , tietokannat , ohjausvirta tietokoneohjelmassa .

Graafiteorian sovellusten luokittelu käytettyjen graafityyppien mukaan [135] :

yksinkertaiset graafit, toisin sanoen ei monikuvaajat, digrafit tai pseudografit;
multigrafit ja pseudografit, mutta ei digrafit;
yksinkertaiset digrafit;
(pseudo)digrafit.

Graafiteorian sovellusten luokittelu käytettyjen graafien attribuuttityyppien mukaan [136] :

käytetyn graafin reunoilla ja pisteillä ei ole attribuutteja;
käytetyn graafin reunoilla on attribuutteja, pisteillä ei;
käytetyn graafin huipuilla on attribuutteja, reunoilla ei;
sekä käytetyn graafin reunoilla että kärjeillä on attribuutteja.

Graafiteorian sovellusten luokittelu sovellusalueittain.

Luokittelu suoritetaan kirjan toisen osan sisällysluettelon mukaisesti [137] .

Sovellukset taloustieteen ja toiminnan tutkimukseen.
kombinatorisia tehtäviä.
Palapelit peleihin.
Vastaava.
Tekniset sovellukset.
Luonnontieteet.
Ihmisen ja yhteiskunnan tutkimisen tehtävät.
Lisäsovellukset.
virtaa verkoissa.

Graafiteorian sovellusten luokittelu sovellusalueittain.

Luokittelu suoritetaan saatavilla olevan tieteellisen kirjallisuuden mukaan . Luettelo joistakin graafiteorian sovellusalueista viittauksin kirjallisuuteen:

arkeologia [138] ;
lohkokaaviot [139] ;
tekoäly [140] ;
äärelliset automaatit [141] ;
logistiikka [142] ;
ohjelmointi [143] ;
sosiologia [144] ;
piirit [145] ;
algoritmien teoria [146] ;
lennonjohto [147] ;
kemoinformatiikka [148] ;
kemiallinen kinetiikka (esimerkiksi vaihesääntö ) [149] ;
kemia ( tietokonekemia ) [150] [151] [152] ;
taloustiede [153] .

Jotkut graafiteorian sovellukset

Ennen kuin sovelletaan matemaattista voimaa todellisen maailman ongelmiin, on tarpeen rakentaa ongelman matemaattinen malli. Kaaviot ovat hämmästyttävän monipuolinen matemaattinen mallinnustyökalu. Alla on useita muita graafiteorian sovelluksia kuin graafiteorian ongelmia [154] .

Kombinatorinen optimointi . Reunan paino on yksi yleisimmin käytetyistä graafin attribuuteista, erityisesti kombinatorisessa optimoinnissa. Esimerkiksi reunan paino voi edustaa:

hinta;
Matkustusaika;
spatiaalinen etäisyys;
tehohäviö;
virtauksen ylärajat ;
tulot ja lähdöt rajallisen automaatin siirtymille .

On ongelmia, jotka ratkaistaan asettamalla vertex-attribuutteja graafimallissa. Esimerkiksi kärjen paino voi edustaa:

tuotantokustannukset ; _
aikaväli aikatauluteoriassa ;
Markovin prosessin tila ;
solmun tila yhteysverkossa.

Mallit yksinkertaisilla kaavioilla.

Arkeologia . Olkoon kokoelma esineitä löydettävä kaupungin paikalta, joka oli olemassa 1000 eKr. - 1000 jKr. Sitten voit rakentaa graafin, jossa on kärkipisteitä - artefakteja, ja kärjet ovat vierekkäin, kun vastaavat artefaktit ovat samasta haudasta. Oletetaan, että samasta haudasta löydetyillä esineillä on päällekkäisiä käyttöjaksoja. Jos rakennamme intervallikaavion , niin siinä on alkuvälin (-1000, 1000) osavälien jakauma ( skaalaus on mahdollista ), joka on yhdenmukainen arkeologisen löydön kanssa.
Sosiologia . Sosiaalisessa treffiverkostossa kärjet ovat ihmisiä ja reunat osoittavat, että vastaavat ihmisparit tuntevat toisensa. Itsetuntemuksen käsitteen sisällyttäminen malliin vaatii itsetuntemuksen syklejä, jotka vastaavat graafin silmukoita .
Maantiede . Maantieteellisessä mallissa graafin kärjet voivat edustaa maita (alueita, osavaltioita) ja reunat yhteistä rajaa.
Geometria . Minkä tahansa monitahoisen kolmiulotteisen avaruuden kärkienja reunojen konfiguraatiomuodostaa yksinkertaisen graafin, jota kutsutaan sen 1-luurankoksi . Platonisten kiinteiden aineiden 1-luurankotovat säännöllisiä kuvaajia .
Tietokonesuunnittelu . _ Useita prosessoreita on kytketty yhteen yhdelle sirulle moniprosessoritietokonetta varten , joka voi suorittaa rinnakkaisia algoritmeja . Tällaisen yhteyksien verkon graafimallissa kärki on yksi prosessori, reuna on suora yhteys kahden prosessorin välillä. Specification for Parallel Architectures havainnollistaa joitain graafiteorian ja abstraktin algebran välisiä vuorovaikutuksia .
Rakentaminen . Teräspalkeista koostuvakaksiulotteinen runko , joka on yhdistetty saranoilla, jotka mahdollistavat kunkin palkin pyörimisen tasossa, on jäykkä, jos mikään sen palkeista ei voi pyöriä . Ongelma sen määrittämisessä, onko kehys jäykkä, voidaan pelkistää liitettävyydeksi kaksiosaisessa graafissa.
Fysikaalinen kemia . Hiilivety on kemiallinen molekyyli , joka koostuu vedystä ja hiiliatomeista . Se on tyydyttynyt , jos se sisältää suurimman määrän vetyatomeja hiiliatomeihinsa nähden. Kyllästyminen tapahtuu, kun läsnä on vain yksinkertaisia sidoksia , eli kun hiilivetyrakennemalli on yksinkertainen graafi. Vetyatomilla on yksi elektroni ja se on aina 1 -valentti molekyylissä. Hiiliatomi on 4-valenttinen ja sen ulkokuoressa on neljä elektronia . Tyydyttyneillä hiilivedyillä butaanilla ja isobutaanilla on sama kemiallinen kaava , mutta niiden graafit eivät ole isomorfisia , joten ne ovat isomeerejä . ${\ce {C4H10}}$
Tietojenkäsittelytiede . Tietokoneverkossa onmahdollisia tietokonepareja ,jotka voidaan liittää suoraan. Jos kaikki parit on kytketty,tietokoneet on kytketty, mutta monia yhteyksiä ei tarvita. Jos tietokoneita yhdistää vähimmäismäärä reunoja, nämä reunat muodostavat puun ja puun reunojen määrä on yksi vähemmän kuin kärkien lukumäärä. $n$ ${n\choose 2}={\frac {n^{2}-n}{2))$ $n$
Oikeustiede . Anna ABC Corporationin kehittää ja markkinoida tietokonesirua , ja pian DEF Corporation tuo markkinoille sirun, jonka toiminta on hämmästyttävän samankaltaista kuin markkinoilla. Jos ABC osoittaa, että DEF-skeema on ABC-skeeman uudelleenjärjestely, eli skeemat ovat isomorfisia , syntyy perusteita patentinloukkauskanteeseen . Jos ABC tarkistaa DEF-sirun jokaisen solmun rakenteen pysyvyyden, tehtävä voi kestää liian kauan. Mikropiirien organisoinnin tunteminenvoi säästää aikaa.
Algoritmien teoria . Anna jonkin hajautetun algoritmin toimia yhteenliittämisverkossa , jossa on taulukkoarkkitehtuuri. Ja olkoon käytettävissä oleva yhteysverkko 13-ulotteinen hyperkuutiokaavio . Jos 13-ulotteinen hyperkuutiograafi sisältää aligraafin , koon ruudukon, niin algoritmi voidaan siirtää suoraan tähän hyperkuutioon. ${\näyttötyyli 8\kertaa 8\kertaa 32}$ $Q_{13}$ ${\näyttötyyli 8\kertaa 8\kertaa 32}$
Tietojenkäsittelytiede . Vertexin k - connectivity ja edge k - connectivity arvoja k käytetään verkon selviytymisen kvantitatiivisessa mallissa, joka on verkon kyky ylläpitää yhteyksiä solmujensa välillä joidenkin reunojen tai solmujen poistamisen jälkeen.
Tietojenkäsittelytiede . Viestintäverkossa virhe on kärjen tai reunan tuhoutuminen (poistaminen) mallinnusgraafista. Näin ollen, mitä korkeampi kärkien ja reunojen liitettävyys on, sitä luotettavampi verkko on. Mitä vähemmän yhteyksiä käytetään yhteyden muodostamiseen, sitä halvempi verkko on. Saamme seuraavan optimointitehtävän: kun k on pienempi kuin n , etsi k -liitetty n - vertex-graafi, jossa on vähiten reunoja.
Koodauksen teoria . Avaruusalus lähettää jonkin verran numerokoodattua kuvaa, jossa numerot ovat kuvapisteiden tummuusarvoja. Kuvan Greyn koodauksenon, että jos "kosmisen kohinan" aiheuttama virhe johtaa luvun yhden binäärinumeron väärinlukemiseen , tämän luvun tulkinta poikkeaa hieman pimeyden todellisesta arvosta. Grayn järjestyskoodivastaaHamiltonin sykliä hyperkuutiograafissa . $n$ $Q_{n}$
Tietokonesuunnittelu . _ Eräs tapa miniatyrisoida ei-tasoinen elektroninen verkko on eristää solmut yhdistävien paljaiden johtimien tasaisten kerrosten väliin. Sirun kokoa ja hintaa pienennetään samalla kun kerrosten määrä minimoidaan. Yksinkertainen lähestymistapa monikerroksisten piirien suunnitteluun on käyttää "yhteisiä viivapiirroksia" ulottuvista osagraafista, jotka aiheuttavat reunan halkeamisen. Tämä tarkoittaa, että kunkin kerroksen solmut ovat samassa paikassa tasossa ja jokainen kerros piirretään viivasegmenteinä.
Viestintäteoria . Useiden strategisten kohteiden tarkkailemiseen vaadittavien tutka-asemien vähimmäismäärävastaavan kuvaajan dominanssiluku .
Kuljetus . Anna luonnonkatastrofin iskeä pienistä kylistä koostuvaan alueeseen. Kaavion kärjet ovat alueen kylät. Kylkirivi osoittaa, että johonkin kylään perustettu ambulanssiasema voi palvella myös toista. Sitten kaavion hallitseva minimijoukko kuvaa tapaa palvella aluetta minimimäärällä ensiapuasemia.
Tietojenkäsittelytiede . Harkitse kuningattarien asettamisen shakkilaudalle ongelmaa: jokainen laudan ruutu on joko kuningatar käytössä tai kuningatar saavuttaa sen yhdellä liikkeellä. Kuningattaren minimimäärän määrittäminen vastaa dominanssiluvun löytämistä graafista , jossa on 64 kärkeä, jossa reunat vastaavat kuningattareiden liikkeitä.

Mallit juurtuneisiin puihin .

Tietokannat . Monet tietojenkäsittelytieteen tietorakenteet perustuvat puihin . Tietokoneen käyttäjän tiedostot sisältävät hakemistot ja alihakemistot (tai kansiot ja alikansiot)esitetään yleensä käyttöjärjestelmässä juuripuun solmuina.
Tietokannat . Binäärihakupuut tallentavat erityisesti tilattuja tietoja tehokkaita hakuja varten . Erityisesti, josbinaarihakupuun solmuja käytetään asianmukaisesti nimikeavainten tallentamiseen , haku voidaan suorittaa suorituksen aikana . $n$ $n$ $O(\log(n))$
Algoritmien teoria . Monimutkaisia päätösstrategioita toteuttavien suurten tietokoneohjelmien suunnittelu perustuu usein juurtuneisiin puihin .
Tietokannat . Juurtuneita puita käytetään tietojen tallentamiseen luokkiinja alaluokkiin . Deweyn desimaaliluokitus kirjastoille onyksi tällainen esimerkki.
Kielitiede . Juurtunutta puuta voidaan käyttääluonnollisen kielen lauseen jäsentämiseen .
Algoritmien teoria . Yhdistetylle graafille , jolla on valittu kärkipiste , lyhyin polkupuu juurtuneena puuna on kompakti tapa kartoittaa lyhin polku valitusta kärjestä mihin tahansa toiseen. Leveys ensin -haku luo lyhimmän polun puun painottamattomalle kaaviolle , ja Dijkstran algoritmi luo tällaisen puun painotetulle kaaviolle .
Tietojenkäsittelytiede . Kun kuljetaan lausekepuuta [ , tuloksena oleva lauseke näytetään etuliitteenä , jälkiliitteenä tai infix-merkinnällä riippuen siitä, kumpaa läpikulkua käytetään. Infix-lauseke vaatii sulkumerkit , jotka voidaan sisällyttää rekursiiviseen läpikulkuun luomalla vasen sulkumerkki jokaisen alipuun läpikäynnin alkuun ja oikeanpuoleinen sulku jokaisen alipuun läpikäynnin loppuun.
Koodauksen teoria . Binääripuuta voidaan käyttää etuliitekoodin muodostamiseen tietylle merkistölle. Tätä varten binääripuun lopulliset kärjet merkitään näillä symboleilla, reunat - 0 ja 1 vasemmalta oikealle, sitten koodisana muodostuu reunamerkinnöistä polulla juuresta symboliin.

Mallit värillisillä kaavioilla .

Viestintäteoria . Kun lähetystaajuutta määritetään samalla alueella oleville radiolähettimille, jotkin lähetinparit vaativat eri taajuuksia häiriöiden välttämiseksi. Kaaviomallia käytetään ratkaisemaan osoitettujen eri taajuuksien määrän minimoimisen ongelma. Oletetaan, että jos kaksi lähetintä ovat alle 100 km:n päässä toisistaan, niiden tulisi lähettää eri taajuuksilla. Sitten rakennetaan graafi, jonka kärjet ovat lähettimiä ja reunat osoittavat alle 100 km:n etäisyydellä toisistaan olevia pareja. Ongelma radiotaajuuksien osoittamisessa häiriöiden välttämiseksi vastaa ongelmaa graafin kärkien värittämisessä siten, että vierekkäisillä pisteillä on eri värit. Taajuuksien vähimmäismäärä on yhtä suuri kuin värien vähimmäismäärä.
Kemia . Esittävät graafin kärjet tuotantoprosessissa käytettyjä erilaisia kemikaaleja ja reunat paria kemikaaleja, jotka voivat räjähtää sekoittuessaan. Tällöin käyrän kromaattinen luku on vähimmäismäärä varastohuoneita, jotka tarvitaan räjähdysaineparien erilliseen varastointiin.
Toimintatutkimus . Olkoon graafin kärjet yliopiston kursseja , reuna yhdistää kaksi kurssia silloin ja vain, jos molemmille kursseille on ilmoittautunut vähintään yksi opiskelija. Näitä kursseja ei voi suorittaa samanaikaisesti. Tällöin kaavion kromaattinen luku on se aikavälillä erotettu akateemisten tuntien vähimmäismäärä luokkaohjelmassa ,jolloin opiskelijoilla ei ole kurssien ristiriitaa .
Algoritmien teoria . Olkoon graafin kärkipisteet tietokoneohjelman muuttujia , reuna yhdistää kaksi muuttujaa, jotka voivat olla aktiivisia samanaikaisesti. Tällöin graafin kromaattinen luku on minimimäärä rekistereitä , jotka vaaditaan mahdollisen luisumisen välttämiseksi – jatkuvan vaihdon tila .
Toimintatutkimus . Olkoon graafin kärjet yliopiston opintokursseja , ja reuna yhdistää kaksi kurssia silloin ja vain, jos molemmille kursseille on ilmoittautunut vähintään kolme opiskelijaa. Näitä kursseja ei voi suorittaa samanaikaisesti. Mutta aikavälillä olevien akateemisten tuntien määrä luokkaohjelmassa on pienempi kuin graafin kromaattinen luku , jossa opiskelijoilla ei ole opintojaksojen ristiriitaa . Sitten sinun on suunniteltava siten, että konfliktien määrä minimoidaan. Jos graafin reunat painotetaan ristiriidan ei-toivottomuuden asteen mukaan, esimerkiksi reuna yhdistää saman opettajan koulutuskurssit, niin meidän on löydettävä väritys, jolla on pienin yhteispainoinen reuna yksivärisellä päättyy.
Tietokonesuunnittelu . _ Painetulla piirilevyllä on useita elektronisia laitteita . Laitteista tulevat liitäntäjohdot tulee olla erivärisiä, jotta ne voidaan erottaa. Pienin määrä tarvittavia värejä on mallinnusverkon reunan kromaattinen numero .

Multigrafien ja pseudografien mallit.

Maantiede . Maantieteellisessä mallissa multigrafin kärjet voivat edustaa maita (alueita, osavaltioita) ja reunat voivat edustaa teitä, jotka ylittävät yhteisen rajan.
Kemia . Esimerkiksi bentseenimolekyylissä on kaksoissidoksia joissakin atomipareissaan , joten se mallinnetaan multigrafilla. Hiiliatomilla onvalenssi 4 ja se mallinnetaan asteen 4 multigrafin kärjellä, vetyatomilla on valenssi 1 ja se mallinnetaan asteen 1 kärjellä
Kuljetus . Erityinen anturilla varustettu vaunu kulkee rataverkon osien läpi etsimään vikoja. Onko mahdollista suunnitella kärryn liike niin, että se diagnosoi jokaisen radan osan tarkalleen kerran ja palaa sitten lähtöpisteeseen? Ongelma vastaa sen määrittämistä, onko monigraafi Euler .
Tietokonesuunnittelu . _ Satunnaisvaihtokaaviot toimivat malleina rinnakkaisille arkkitehtuureille , jotka soveltuvat erilaisten hajautettujen algoritmien suorittamiseen , mukaan lukien korttien sekoitus ja nopea Fourier-muunnos . Satunnaisvaihdon pseudografin kärjet ovat pituisia bittijonoja . ${\displaystyle SE_{n))$ $n$
Tietokonesuunnittelu . _ Tietokone koostuu useista moduuleista ja niiden koskettimista . Moduulien fyysinen sijainti määritetään ja koskettimet on johdotettava . Koskettimet ovat kooltaan pieniä, eikä mihinkään aluslevyyn voi kiinnittää enempää kuin kaksi johtoa. Melun minimoimiseksi ja johdotuksen yksinkertaistamiseksi johdon kokonaispituus tulee pitää mahdollisimman pienenä. Tarvittava rakenne saadaan Hamiltonin polulla minimaalisella painolla.
Kuljetus . Joka viikonloppu yksityinen koulu kuljettaa n lasta m bussipysäkille. Vanhemmat tapaavat lapsiaan bussipysäkeillä. Koulu omistaa k linja-autoa eri kapasiteetilla. Kuinka rakentaa bussireittejä pienin kokonaiskustannuksin? Graafin kärjet ovat koulu ja pysähdykset, reunojen paino on niiden välinen etäisyys. Jokaiseen bussiin mahtuu useita eri pysäkeillä poistuvia lapsiryhmiä, jotta bussin kapasiteetti ei ylity. Bussireitin hinta on yhtä suuri kuin vähimmäispainoisen Hamiltonin syklin hinta. Tehtävänä on siis jakaa m bussipysäkkiä k osajoukkoon niin, että kaikkien linja-autojen reittikustannusten summa on minimaalinen.
Toimintatutkimus . Yliopistolla on useita luennoitsijoita useiden kurssien opettamiseen . Kaikkien kurssien suunnitteluun vaaditaan luokkasuunnitelmaan vaadittavien akateemisten tuntien vähimmäismäärä,jottasaman kurssin kahta osaa ei opeteta samanaikaisesti. Rakennamme kaksiosaisen graafin opettajien ja kurssien osuuksista, reunat yhdistävät opettajat heidän kursseihinsa (opettaja voi opettaa eri kursseja ja eri opettajat voivat opettaa samaa kurssia). Opettajien valinta kursseille voidaan suorittaa tietyn ajan. Jos reunaväri on akateeminen tunti päiväaikataulussa, niin kaksiosaisen graafin reunojen väri on mahdollinen kurssiosien aikataulu. Minimaalinen reunavärjäys käyttää vähiten akateemista tuntia.

Mallit yksinkertaisilla digrafeilla.

Kartografia . Kaupungin katukartta voidaan esittää sekakaaviona seuraavasti. Tämän graafin kärjet ovat kaupungin kohteita ja suuntautuneet ja yksinkertaiset reunat ovat katuja, joilla on yksisuuntainen ja kaksisuuntainen liikenne.
Sosiologia . Hierarkia voidaan esittää suunnattuna puuna . Esimerkiksi päätöksenteon hierarkia yrityksessä. Kaavioita ja digrafeja käytetään mallintamaan sosiaalisia suhteita , ei vain fyysisiä verkostoja.
Ekologia . Kasvi- ja eläinlajien välistä ravitsemuksellista suhdetta ekosysteemissä kutsutaan ravintoverkkoksi , ja se mallinnetaan yksinkertaisella digraafilla. Jokaista järjestelmän lajia edustaa kärkipiste, ja kaaret suunnataan syövistä lajeista lajeihin, joita ensimmäinen laji ruokkii.
Taloustiede . Suurissa projekteissa ajoitus sisältää usein tehtäviä, jotka eivät voi alkaa ennen kuin muut on suoritettu. Digraafimallin kärjet ovat tehtäviä, kaari kärjestä toiseen tarkoittaa, että toinen tehtävä ei voi alkaa ennen ensimmäisen tehtävän valmistumista. Kaavion yksinkertaistamiseksi transitiivisuudesta johtuvia kaaria ei piirretä.
Ohjelmointi . Tietokoneohjelma on joukko ohjelmointilohkoja, joihin liittyy ohjausvirta . Digrafi on luonnollinen malli tälle jaottelulle: kärki on ohjelmointilohko kytkettynä, ja jos yhden lohkon viimeisen käskyn ohjaus siirretään toisen lohkon ensimmäiseen käskyyn, niin ensimmäisestä lohkosta toiseen vedetään kaari. . Vuokaavioissa ei yleensä ole useita kaaria.
Sähkötekniikka . Määritä sähkövirta sähköpiirin jokaisessa haarassakäyttämällä Ohmin lakia , Kirchhoffin ensimmäistä sääntöä ja Kirchhoffin toista sääntöä . Tehokas ratkaisustrategia on löytää virittävän puun avulla digraafin ääriviivojen vähimmäisjoukko, jonka vastaavat yhtälöt riittävät ratkaisemaan ongelman. Syklien perusperusta on sykliavaruuden perusta ,joten sitä vastaavat yhtälöt muodostavat täydellisen joukon lineaarisia algebrallisia yhtälöitä ja ongelma ratkeaa.
Ohjelmointi . Käsitelläänn työtä yhdellä koneella . Aika, joka tarvitaan minkä tahansa työn käsittelyyn muiden jälkeen, on tiedossa. Kuinka järjestää tehtävät kokonaisajan minimoimiseksi? Piirrämme digraafin, jossa on n pistettä - tehtävää ja vastaavilla kaarien painoilla. Sitten vaadittu tehtäväsarja annetaan Hamiltonin polulla minimaalisella painolla.
Taloustiede . Kun otetaan huomioon uuden auton hinta ja vuosittainen hinnannousu, vuosittaiset käyttökustannukset ja jälleenmyyntiarvo ennustetaan. Miten minimoit auton omistamisen ja käytön nettokustannukset, kun lähdet uuteen autoon? Rakennamme digraafin, jonka kärkien lukumäärä on 1 enemmän kuin käyttövuosien lukumäärä, jonka kaaret menevät pienemmistä suurempiin vuosiin ja joiden paino on yhtä suuri kuin uuden auton ostokustannukset vuoden alussa. kaari ja sen ylläpito kaaren loppuvuoden alkuun asti. Ongelma tiivistyy lyhimmän polun löytämiseen ensimmäisestä kärjestä viimeiseen.
Radio . Hakuverkkoa mallinnetaan digraafilla : digraafin yläosassa on henkilö, kaari on yksisuuntainen suora yhteys henkilöstä toiseen. Ilmoituksen lähettämiseen henkilöltä henkilölle ei tarvitse olla suoraa yhteyttä, on oltava vain suunnattu polku. Digraafin transitiivinen sulkeminen määrittelee kaikki pisteparit, joille on olemassa polku kärjestä toiseen.
Ohjelmointi . Tehdäänyhdelle koneelleuseiden operaatioiden proseduuri ja siinä on luonnollinen toimintojen osajärjestys . Tämän toimintosarjan lineaarinen laajennus ratkaisee toimintojen lineaarisen järjestyksen ongelman koneessa.
Taloustiede . Digrafimalliakäytetään suurten monimutkaisten hankkeiden suunnittelussa kahden tavoitteen saavuttamiseksi: ajoittaa toiminnot niin, että projektin valmistumiseen kuluu mahdollisimman vähän aikaa ; tunnistaa toimet, joiden viivästyminen viivästyttää hanketta. Jos jokaisen tapahtuman kesto on tiedossa, näiden ongelmien ratkaisemiseen käytetään kriittisen polun menetelmää (CPM)

Mallit (pseudo)digrafioilla.

Markovin ketju . Markovin prosessissa tilasta toiseen siirtymisen todennäköisyys riippuu vain nykyisestä tilasta. Markovin ketjun graafimallissa jokainen kaari on merkitty siirtymän todennäköisyydellä alkupisteen tilasta loppupisteen tilaan, ja kustakin kärjestä lähtevien kaarien todennäköisyyksien summa on 1. A Markov diagrammi on esimerkki painotetusta kaaviosta .
Leksinen analyysi . Tietokoneohjelman lähdekoodia voidaan pitää merkkijonona. Leksikaalisen skannerin on skannattava nämä merkit yksi kerrallaan ja tunnistettava, mitkä merkit "yhdistyvät" muodostaen syntaktisen merkin tai lekseemin . Tällainen skanneri voidaan mallintaa merkityllä digrafilla . Ensimmäinen kärkipiste on alkutila ennen merkkien skannausta. Toinen huippu on hyväksymistila, jossa skannattujen merkkien osamerkkijono on kelvollinen tunniste. Kolmas huippu on hylätty tila - alimerkkijono hylättiin virheellisenä tunnisteena. Valokaarimerkit osoittavat, mitkä symbolit aiheuttavat siirtymisen aloitustilasta lopputilaan.
Pelin teoria . Anna pelaajan, alkaen 3 dollarista, pelata seuraava peli. Kaksi kolikkoa heitetään. Jos kaksi päätä nousee, pelaaja voittaa 3 dollaria, muuten hän häviää 1 dollarin. Pelaaja pelaa, kunnes hän joko menettää kaikki rahansa tai hänellä on vähintään 5 dollaria. Graafimalli on Markovin ketjugraafi .

Eulerin syklin ja kiinalaisen postimiehen ongelman soveltaminen .

Koodauksen teoria . Pyörivässä rummussa on 16 eri sektoria. Anna kullekin sektorille 0 tai 1 asettamalla sähköä johtavaa materiaalia joihinkin sektoreihin ja johtamatonta toisiin. Sitten kiinteillä antureilla "luimme" 4-bittisen merkkijonon, joka vastaa neljää sektoria, jotka putosivat antureille. Jos rumpusektorien 16-bittinen merkkijono on (2, 4) de Bruijn-sekvenssi , rummun sijainti voidaan määrittää 4-bittisen alijonon perusteella, jonka anturit sieppaavat. Tämä on taloudellisempaa kuin 4-bittinen koodi sektoria kohti. (2, 4)-de Bruijn-sekvenssi konstruoidaan käyttämällä (2,4)-de Bruijn- digrafiaa .
Kaupunkitalous . Digrafi on yksisuuntaisten katujen verkosto, paksut kaaret ovat lakaisettavia katuja, reunan paino on aika, joka kuluu kadun ohittamiseen lakaisematta, ja kadun lakaisemiseen kuluva aika on kaksinkertainen. Mikä reitti minimoi kaikkien vaadittujen katujen lakaisemiseen kuluvan kokonaisajan, joka alkaa ja päättyy tiettyyn kärkeen?
Tietojenkäsittelytiede . Piirrä useita tuhansia kopioita verkosta, jos vaakasuuntaisen reunan rakentaminen kestää kaksi kertaa kauemmin kuin pystysuoran. Tehtävä reitittää plotteri niin, että kokonaisaika pysyy minimissä, on mallinnettu kiinalaisen postimiehen tehtäväksi.
Sosiologia . Joidenkin kuuden hengen osastolla olevien parien on tavattava yksityisesti samassa kokoushuoneessa. Onko mahdollista järjestää kahden hengen konferensseja niin, että yksi osallistujista kussakin konferenssissa (paitsi viimeinen) osallistuu myös seuraavaan, mutta kukaan ei osallistu kolmeen peräkkäiseen konferenssiin?
Genetiikka . RNA: n (ribonukleiinihappo) ketjussa jokainen linkki edustaa yhtä neljästä mahdollisesta nukleotidista . Kun yritetään tunnistaa RNA-juoste tuntemattomasta näytteestä, nykyinen tekniikka ei salli pitkien juosteiden suoraa tunnistamista. On olemassa menetelmä pitkän RNA-ketjun fragmentoimiseksi ja alifragmentoimiseksi tunnistettavissa oleviksi osasäikeiksi. Hutchinsonin strategia on rakentaa Euler-digrafi, jonka kaaret on merkitty fragmenteilla siten, että jokainen Eulerin polku vastaa RNA-juostetta.
Kombinatoriikka . Yhteenvetona aikaisemmasta genetiikan sovelluksesta RNA:ta voidaan pitää nukleotidinumeroiden merkkijonona. Olkoon tietylle numerosarjalle—,— merkkijonon osamerkkijonojen lukumäärä. Tällöin RNA:han upotettu tieto riippuu vain numeroistaja,,. Merkkijonon rekonstruoimiseksi rakennamme digraafin viereisyysmatriisin avulla , jossa ovat sijastaovat. Sitten kaikki erilaiset Eulerin polut antavat kaikki mahdolliset yhteensopivia merkkijonoja. $f_{i}$ $i$ $f_{ij}$ $ij$ $f_{i}$ $f_{ij}$ ${\näyttötyyli i,j=1,2,\pisteet ,n}$ $f_{ii}=0$ $(f_{ij})$ $f_{ii}=0$ $f_{i}$

Jotkut graafiteoriaalgoritmit

Algoritmit esitetään pakatussa muodossa, ilman yksityiskohtia tietokoneen toteutuksesta. On monia projekteja, joissa ehdotetaan algoritmien muuntamista tietokoneohjelmiksi [154] .

Rekursiivinen graafinen sekvenssi . Rekursiivinen algoritmi, joka määrittää, onko ei-kasvava sekvenssijonkin graafin kärkiasteiden sarja.
Graafin isomorfismin määrittäminen tyhjentävällä numeraatiolla . Kaksi graafia ovat isomorfisia, jos niiden kärkijoukot voidaan järjestää siten, että niiden vierekkäisyysmatriisit ovat identtisiä.
Suora vasemman puun läpikulku (NLR) . Ensin kuljemme vasemman alipuun läpi ja luettelemme kukin kärkipiste vain, kun se ilmestyy ensimmäistä kertaa.
Käänteinen vasemman puun läpikulku (LRN) . Ensin kuljemme vasemman alipuun poikki ja luettelemme kukin huippupiste vain, kun se esiintyy viimeisen kerran.
Keskitetty vasemman puun läpikulku (LNR) . Ensin kuljemme vasemman alipuun läpi, lisäämme luetteloon jokainen kärki, jolla on vasen alipuu, vasta kun se ilmestyy toisen kerran, lisää loput kärjet luetteloon, kun ne ilmestyvät ensimmäistä kertaa.
Hae binäärihakupuusta . Jokaisessa iteraatiossa suljemme pois joko vasemman tai oikean alipuun muusta hausta riippuen siitä, onko kohdeavain suurempi vai pienempi kuin vastaavasti nykyisen solmun avain .
Lisääminen binaarihakupuuhun . Iteratiivisesta näkökulmasta binäärihakua suoritetaan, kunnes se päättyy lopulliseen kärkeen. Uusi avain määrätään sitten uudelle solmulle, josta tulee kyseisen päätesolmun vasen tai oikea alipuu, riippuen uuden avaimen ja loppusolmun avaimen vertailusta.
Huffmanin algoritmi . Etuliitekoodissa, jossa käytetään lyhyempiä koodisanoja useammin esiintyvien merkkien koodaamiseen, viestit vaativat yleensä vähemmän bittejä kuin koodissa, joka ei käytä sitä . Huffman-algoritmi rakentaa juuri tällaisen tehokkaan etuliitekoodin yhdistämälläkaksi alkuperäisen metsän pienipainoista puuta uudeksi puuksi.
Lisätään prioriteettipuuhun . Ensin uusi kärkipiste lisätään ensimmäiseen vapaaseen paikkaan prioriteettipuussa ja sitten sitä siirretään juureen , kunnes sen prioriteetti on pienempi tai yhtä suuri kuin emokärkipisteen prioriteetti .
Poisto prioriteettipuusta. Ensin poistettava kärkipiste korvataan kärjellä, joka on oikealla sijalla prioriteettipuun alemmalla tasolla. Tämä kärki virtaa sitten iteratiivisesti alas vaihtaen paikkoja korkeamman prioriteetin jälkeläisen kanssa, kunnes sen prioriteetti ylittää molempien jälkeläisten prioriteetit.
Prufer-koodaus . Pituus Prufer-sekvenssi muodostetaan tietystä puusta, jonkakärjet on numeroitu, poistamalla kärkipisteitä, kunnes kärkeä ei olejäljellä. $n-2$ $n$ ${\näyttötyyli 1,2,\pisteet ,n}$ $2$
Prufer-dekoodaus . Koodattu puu rekonstruoidaan Prufer - sekvenssistäja puun kärkipisteiden numeroiden luettelosta. ${\displaystyle p_{1},p_{2},\dots ,p_{n-2))$ ${\näyttötyyli 1,2,\pisteet ,n}$
Ylivoimaisen puun rakentaminen . Alkaen graafin tietystä kärjestä, virittävä puu rakennetaan juurettuna tiettyyn kärkeen käyttämällä mitä tahansa menetelmää uusien puun kärkien löytämiseksi vanhojen kärkien viereen.
Kattavan metsän rakentaminen . Aloittaen irrotetun graafin kunkin komponentin tietystä kärjestä, nykyisen komponentin virittävä puu, joka on juurtunut tiettyyn kärkeen, muodostetaan käyttämällä mitä tahansa menetelmää uusien puun kärkien löytämiseksi vanhojen kärkien viereen.
Syvyys ensimmäinen haku (DFS) . Alkaen graafin tietystä kärjestä, rakennetaan hakupuu seuraavasti. Graafista valitaan uusi kärkipiste jo rakennetun puun viimeisimmän löydetyn kärjen viereen. Jos tämä ei ole mahdollista, palataan edelliseen havaittuun huippuun ja yritys toistetaan. Seurauksena on, että haku siirtyy syvemmälle kaavioon (siis nimi "syvyys").
Breadth First Search (BFS) . Alkaen graafin tietystä kärjestä, rakennetaan hakupuu seuraavasti. Haku "haaroittuu" tietystä kärjestä ja kasvattaa puuta valitsemalla vierekkäiset reunat puun kärkipisteillä mahdollisimman lähellä annettua kärkeä. Tämän seurauksena haku liikkuu graafin leveyttä pitkin kerroksina, jotka ovat yhtä kaukana annetusta kärjestä (siis nimi "leveä").
Primin pienin virittävä puu . Etsimme virittävää puuta yhdistetystä painotetusta graafista reunapainojen vähimmäissummalla. Aloitamme mistä tahansa graafin kärjestä ja jokaisessa iteraatiossa rakennamme Prim-puun lisäämällä uuden kärjen, joka on yhdistetty puuhun minimipainoisella reunalla.
Dijkstran lyhin polku . Lyhyimmät polut painotetun graafin tietystä kärjestä kaikkiin muihin pisteisiin etsitään. Aloitamme graafin tietystä pisteestä ja jokaisessa iteraatiossa lisätään käsiteltyihin pisteisiin uusi, joka on yhdistetty reunalla johonkin käsitellyistä kärjestä ja joka on lähinnä annettua kärkeä.
Syvyyshaun käyttäminen .

Etsi siltoja . Tietyssä yhdistetyssä graafissa siltoja etsitään käyttämällä ensimmäistä syvyys -ensimmäistä kulkua, kunnes kaikki syklin reunot tulevat ensimmäiseen palautukseen ja supistumaan yhteen kärkeen.
Topologinen lajittelu . Tietyssä ääriviivattomassa digraafissa kärjet numeroidaan alkaen maksimimäärästä käyttämällä ensimmäistä syvyys-ensimmäistä hakukierrosta ensimmäiseen palautukseen ja numeroimalla polun viimeinen kärki nykyisellä maksimiluvulla, poistaen tämän kärjen myöhemmistä hauista.
Etsi artikulaatiopisteitä . Tietyssä yhdistetyssä graafissa nivelpisteitä etsitään käyttämällä syvyys -ensin hakua , erityistä syvyys-first-hakupuun kärkien numerointia ja näiden lukujen vertailua.
Estä haku . Tietyn yhdistetyn graafin kaikki lohkot etsitään. Aiempaa algoritmia käytetään aliohjelmana.
Tarryn Maze Exit Algorithm . Älä koskaan palaa, jos on vaihtoehto, äläkä ohita toista kertaa samaan suuntaan. Toisin sanoen, kulje aina uusi polku ennen paluuta, mikä tekee tästä algoritmista eräänlaisen syvyyshaun.
Lähin naapuri -algoritmi matkustavan myyjän ongelmassa . Yksinkertaisin TSP- heuristiikka on lähin naapuri. Tämä on ahne algoritmi : valitaan halvin tapa mennä muualle. Toisin sanoen lähimmän naapurin algoritmi on syvyysläpikulku, joka valitsee pienimmän painoiset reunat.
Algoritmi vahvasti toisiinsa liittyvien komponenttien etsimiseen . Algoritmi, joka käyttää syvyyshakua yhdessä kahden pinon kanssa. Strategia molemminpuolisesti saavutettavien pisteiden löytämiseksi on seurata kuinka ei-puun kaaret yhdistävät sen kärjet.

Ahne algoritmi riippumattomuusjärjestelmän enimmäispainon osajoukon ongelman ratkaisemiseksi . Annetaan ei-negatiivinen paino graafin kullekin reunalle ja annetaan graafin riippumattomuusjärjestelmä. Iteroimme graafin kaikki reunat alkaen maksimipainosta ja rakennamme niistä riippumattomuusjärjestelmän osajoukon, jossa on reunojen painojen maksimisumma.
Ahne algoritmi maksimipainon vastaavuusongelman ratkaisemiseen . Edellisen algoritmin erikoistapaus.
Optimaalisesti yhdistetyn graafin rakentaminen kärkeillä. $k$ $n$ Frank Harari kehitti menetelmän -kytketyn Harari-graafin rakentamiseksi pisteisiin , joissa on minimimäärä reunoja . Harari-graafin rakentaminen alkaa -syklisestä graafista, jonka kärjet on numeroitu peräkkäin myötäpäivään kehää pitkin. Rakenne riippuu suhteesta ja jakautuu kolmeen tapaukseen. $k$ ${\displaystyle H_{k,n))$ $n$ $\left\lceil {\frac {kn}{2}}\right\rceil$ $k\geqslant 2$ ${\displaystyle H_{k,n))$ $n$ $0,1,2,\dots ,n-1$ ${\displaystyle H_{k,n))$ $k$ $n$
Eulerin syklin rakentaminen . Yhdistetyssä graafissa, jonka kaikilla pisteillä on parillinen aste, valitsemme minkä tahansa kärjen ja katsomme sitä Eulerin sykliksi. Jokaisessa iteraatiossa lisäämme minkä tahansa uusien reunojen syklin, jolla on yhteinen kärki nykyisen Eulerin syklin kanssa.
(2, n )-de Bruijn-sekvenssin rakentaminen . Muodostetaan (2, n )-de Bruijn-digrafi . Valitsemme tämän digrafin kärjen ja rakennamme digraafin orientoidun Eulerin syklin , alkaen valitusta kärjestä. Valitusta kärjestä lähtien kierretään peräkkäin Eulerin syklin ympäri ja kerätään graafisen kaarien yksibittiset nimikkeet de Bruijn-sekvenssiin.
Postimiehen silmukan rakentaminen . Reunojen jäljitys painotetun yhdistetyn graafin lyhyimpiä polkuja pitkin parittoman asteen kärkien välillä. Jos kahden parittoman asteen kärjen välisen polun kaikki reunat monistetaan, näiden kahden kärjen asteet tulevat parillisiksi ja polun kunkin sisäisen kärjen asteen pariteetti pysyy muuttumattomana.
Vähimmäisvirittävän puun algoritmi ja sen kaksinkertaistaminen matkustavan myyjän ongelmassa . Vähimmäisvirittävän puun löytäminen . Tuplaamme jokainen puun reuna, saamme Euler-graafin . Rakennamme Eulerin syklin . Rakennamme Hamiltonin syklin Eulerin syklistä käyttämällä lyhyitä polkuja, kun Eulerin sykli katkeaa.
Vähimmäisvirittävä puu ja sovitusalgoritmi matkustavan myyjän ongelmassa . Vähimmäisvirittävän puun löytäminen . Rakennamme Euler-graafin lisäämällä reunat joistakin sovituksista virittävän puun kanssa. Rakennamme Eulerin syklin . Rakennamme Hamiltonin syklin Eulerin syklistä käyttämällä lyhyitä polkuja, kun Eulerin sykli katkeaa.
Yksinkertainen testi kaksoisliitetyn graafin tasomaisuudelle . Algoritmi vaatii laskentavaiheita. Ensin piirretään mikä tahansa kaksoisliitetyn graafin sykli. Sitten lisätään jaksoja, kunnes graafi on rakennettu (tasomainen) tai reunojen on leikattava (ei-taso). $O(n^{2})$
Ahne vertex väritys. Sekvenssialgoritmi, joka kulkee nopeasti graafin kärjet tietyssä järjestyksessä ja määrittää kullekin kärjelle ensimmäisen saatavilla olevan värin. Tämä väritys on epätodennäköistä, että se on minimaalinen, ja on epätodennäköistä, että mikään polynomiaikaalgoritmi voi tehdä tämän, koska graafin kromaattisen luvun laskentaongelma on NP-täydellinen .
Ahne vertex väritys korkeimmalla asteella . Jokaisessa vaiheessa valitaan värittämättömien pisteiden joukosta se, jolla on eniten vierekkäisiä erivärisiä pisteitä.
Ahne reunavärjäys . Samanlainen kuin ahne vertex-värjäys.
Maksimaalisen yhteensopivuuden ahne reunavärjäys . Jokaisessa vaiheessa värittämättömien reunojen joukosta etsitään maksimi yhteensopivuus ja sitten kaikki sen reunat maalataan samalla värillä.
Warshallin algoritmi transitiivisen sulkemisen löytämiseksi. Olkoon digraafi annettu. Laskennallisesti tehokas algoritmi rakentaa digrafien sekvenssin siten, että edellinen digrafi on seuraavan digraafin aligraafi ja viimeinen digrafi on alkuperäisen transitiivinen sulkeminen . Seuraava digrafi saadaan edellisestä lisäämällä kaari, jos kaaria ei ole, jos uuden kaaren alkupisteestä loppupisteeseen on polku, jonka pituus on 2.
Kahnin algoritmi topologiselle lajittelulle . Tämä on yksinkertainen algoritmi osittain järjestetyn joukon lineaarisen laajennuksen . Ajatuksena on aina valita minimielementti jokaisessa algoritmin vaiheessa.
Tapahtuman aikaisimman ajan laskeminen. Jokaisessa iteraatiossa suuren kompleksisen projektin painotetussa asyklisessä digrafissa valitaan kärki, joka ei sisällä kaaria, ja sen myöhempien kärkien aikaisimmat aika-arvot päivitetään vastaavasti. Sitten tämä kärki poistetaan digraafista ja seuraava iteraatio alkaa. Algoritmi laskee pisimmät polut alkupisteestä toisiinsa.
Viimeisimmän tapahtuma-ajan laskeminen. Samanlainen kuin aikaisimman tapahtuma-ajan laskenta, mutta suoritetaan sen jälkeen, kun aikaisin tapahtuma-aika on laskettu vastakkaiseen suuntaan projektin päättymisdigraafin yläreunasta, joka alustetaan aikaisimmalla tapahtuma-ajalla.

Jokaisessa iteraatiossa suuren kompleksisen projektin painotetussa asyklisessä digrafissa valitaan kärki, joka ei sisällä kaaria, ja sen myöhempien kärkien aikaisimmat aika-arvot päivitetään vastaavasti. Sitten tämä kärki poistetaan digraafista ja seuraava iteraatio alkaa. Algoritmi laskee pisimmät polut alkupisteestä toisiinsa.

Katso myös

Graafiteorian termien sanasto

Muistiinpanot

↑ Akimov O. E. Diskreetti matematiikka: logiikka, ryhmät, kaaviot, 2003 , s. 238.
↑ 1 2 3 Karpov D.V. Graafiteoria . 2017 tai myöhemmin , s. 2-3.
↑ 1 2 3 Ore O. Kaaviot ja niiden sovellus, 1965 , s. 6.
↑ Wilson R. Johdanto graafiteoriaan, 1977 , s. 5.
↑ 1 2 Bondy JA, Murty USR Graph Theory, 2008 , s. ix.
↑ Basaker R., Saaty T. Finite Graphs and Networks, 1974 , s. 7.
↑ Bondy JA, Murty USR Graph Theory, 2008 , s. vii.
↑ 1 2 Berge K. Graafiteoria ja sen sovellukset, 1962 , s. 5.
↑ Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Graafiteorian luentoja, 1990 , s. 3.
↑ Harari F., Palmer E. Enumeration of Earls, 1977 , s. 255.
↑ Christofdes N. Graafiteoria. Algoritminen lähestymistapa, 1978 , s. 7.
↑ 1 2 3 Harari Frank. Graph Theory, 2003 , s. 13.
↑ 1 2 Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Matematiikan oppikirjan sivujen takana, 1996 , s. 288.
↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertintis, 1736 .
↑ 1 2 3 4 5 Harari Frank. Graph Theory, 2003 , s. 13-17.
↑ 1 2 3 4 5 6 7 8 9 10 Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. yksitoista.
↑ 1 2 M. Camille Jordan. Sur les assemblages de lignes, 1869 .
↑ Romanovsky I.V. Diskreetti analyysi, 2003 , s. 185.
↑ Gross JL, Yellen J. Graafiteorian käsikirja, 2004 , s. 35.
↑ Sylvester JJ Kemia ja algebra, 1878 , s. 284.
↑ 1 2 3 Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
↑ 1 2 Denes Konig. Teoria äärellisistä ja äärettömistä graafista, 1990 , s. kolmekymmentä.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valitut graafiteorian luvut, 2008 , s. 151-152.
↑ 1 2 3 4 Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. 12.
↑ Keisarillisen tiedeakatemian konferenssin kokouspöytäkirjat vuosina 1725-1803. Volume I. 1725-1743, 1897 , s. 220-221.
↑ 1 2 3 Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. viisitoista.
↑ 1 2 Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. 26.
↑ Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. 31-32.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 17.
↑ Harari Frank. Graph Theory, 2003 , s. kahdeksantoista.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. 97-99.
↑ Harari Frank. Graph Theory, 2003 , s. 126.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 127-128.
↑ Hararin elämäkerta , 2005 .
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 5.
↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. xi.
↑ 1 2 Frich R., Peregud E. E., Matsievsky S. V. Valitut graafiteorian luvut, 2008 , s. 145.
↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 .
↑ Denes Konig. Äärillisten ja äärettömien graafien teoria, 1990 .
↑ Wilson R. Johdanto graafiteoriaan, 1977 , s. 6.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 21.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. xi-xii.
↑ Akimov O. E. Diskreetti matematiikka: logiikka, ryhmät, kaaviot, 2003 , s. 236-237.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. xi.
↑ Goodman S., Hidetniemi S. Johdatus algoritmien kehittämiseen ja analysointiin, 1981 , s. 47.
↑ Reinhard Diestel. Graph Theory, 2016 , Notes, s. 33.
↑ Distel R. Graph Theory, 2002 , s. 43.
↑ Kormen T. H. et al. Algoritmit: rakentaminen ja analyysi, 2009 , s. 608.
↑ 1 2 3 4 Ore O. Kaaviot ja niiden sovellus, 1965 , s. 15-19.
↑ Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. 39.
↑ Zykov A. A. Graafiteorian perusteet, 2004 , s. 512-517.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 469.
↑ Berge K. Graafiteoria ja sen sovellukset, 1962 , s. 7.
↑ Reinhard Diestel. Graafiteoria, 2016 , s. yksi.
↑ Distel R. Graph Theory, 2002 , s. viisitoista.
↑ Harari Frank. Graph Theory, 2003 , s. 21-22, 27-28, 31-32.
↑ Reinhard Diestel. Graafiteoria, 2016 , 1.1-1.2, 1.6, 1.10.
↑ Distel R. Graph Theory, 2002 , 1.1-1.2, 1.6, 1.10.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. 2. Nimitys G - englannista. kaavio ja saksa. Kaavio - kaavio, V - englanti. vertex - top, E - englanti. reuna - reuna.
↑ Tutt W. Graph Theory, 1988 , s. 16.
↑ Basaker R., Saaty T. Finite Graphs and Networks, 1974 , s. yksitoista.
↑ 1 2 Frich R., Peregud E. E., Matsievsky S. V. Valitut graafiteorian luvut, 2008 , s. 5. Nimitys K - siitä. komplett - täydellinen.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valitut graafiteorian luvut, 2008 , s. 2. Nimitys deg - englannista. tutkinto - tutkinto.
↑ Harari Frank. Graph Theory, 2003 , s. 23-24.
↑ Reinhard Diestel. Graafiteoria, 2016 , 1.1, 1.10.
↑ Distel R. Graph Theory, 2002 , 1.1, 1.10.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valittuja graafiteorian lukuja, 2008 , s. 2. Nimitys G - englannista. kaavio ja saksa. Kaavio - kaavio, V - englanti. vertex - top, E - englanti. reuna - reuna.
↑ Frich R., Peregud E. E., Matsievsky S. V. Valitut graafiteorian luvut, 2008 , s. 21. Nimitys D - englannista. suora - suora.
↑ Harari Frank. Graph Theory, 2003 , s. 26-27, 83-84.
↑ Reinhard Diestel. Graafiteoria, 2016 , 1.3-1.4, 1.8.
↑ Distel R. Graph Theory, 2002 , 1.3-1.4, 1.8.
↑ Harari Frank. Graph Theory, 2003 , s. 48-51.
↑ Reinhard Diestel. Graafiteoria, 2016 , 1.5.
↑ Distel R. Graph Theory, 2002 , 1.5.
↑ Reinhard Diestel. Graafiteoria, 2016 , Abstrakti.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 2.
↑ Distel R. Graph Theory, 2002 , luku 2.
↑ 1 2 Distel R. Graph Theory, 2002 , luku 3.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 3.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 1.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 4.
↑ Distel R. Graph Theory, 2002 , luku 4.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 5.
↑ Distel R. Graph Theory, 2002 , luku 5.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 6.
↑ Distel R. Graph Theory, 2002 , luku 6.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 7.
↑ Distel R. Graph Theory, 2002 , luku 7.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 8.
↑ Harari Frank. Graph Theory, 2003 , s. 28-30.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 9.
↑ Distel R. Graph Theory, 2002 , luku 9.
↑ Harari Frank. Graph Theory, 2003 , s. 85-88.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 10.
↑ Distel R. Graph Theory, 2002 , luku 10.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 11.
↑ Distel R. Graph Theory, 2002 , luku 11.
↑ Alon N., Spencer J. Probabilistinen menetelmä, 2013 , 1.1. Todennäköisyyspohjainen menetelmä.
↑ Reinhard Diestel. Graafiteoria, 2016 , luku 12.
↑ Distel R. Graph Theory, 2002 , luku 12.
↑ Reinhard Diestel. Graafiteoria, 2016 , 1.9.
↑ Distel R. Graph Theory, 2002 , 1.9.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 197.
↑ Harari Frank. Graph Theory, 2003 , s. 54-56.
↑ Ore O. Grafit ja niiden sovellus, 1965 , s. 9.
↑ Distel R. Graph Theory, 2002 , s. 33-34.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 248-249.
↑ Ore O. Grafit ja niiden sovellus, 1965 , s. 33.
↑ Ore O. Graph Theory, 1980 , s. 53.
↑ 1 2 Yhdellä vedolla , 1940 .
↑ Fleischner G. Euler-kaaviot ja niihin liittyvät ongelmat, 2002 , s. 89-90.
↑ Distel R. Graph Theory, 2002 , s. 139-140.
↑ Harari Frank. Graph Theory, 2003 , s. 17-18.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 371.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , Neliväriongelmaa ei mainita tässä kirjassa.
↑ Ore O. Grafit ja niiden sovellus, 1965 , s. 143-144.
↑ Ore O. Graph Theory, 1980 , s. 9.
↑ Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Matematiikan oppikirjan sivujen takana, 1996 , s. 290-292.
↑ Perelman Ya. I. Live Mathematics, 1967 , s. 24.
↑ Ore O. Graph Theory, 1980 , s. 66.
↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , III. Kapitel. Labyrinttiongelma..
↑ Ore O. Grafit ja niiden sovellus, 1965 , s. 22.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 272.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 22.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 48-50, 176-179.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 64.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 83.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 208.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 209.
↑ 1 2 Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 232.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 295.
↑ Harari Frank. Graph Theory, 2003 , s. yksi.
↑ Gross JL, Yellen J. Graafiteorian käsikirja, 2004 , s. 9.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. yksi.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 22-26.
↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 48-26.
↑ Basaker R., Saaty T. Finite Graphs and Networks, 1974 , osa II. Graafiteorian sovellukset.
↑ Kamenetsky I. S., Marshak B. I., Sher Ya. A. Arkeologisten lähteiden analyysi: Possibilities of a formalized approach, 2013 .
↑ Shalyto A. A. Loogisten ohjaustehtävien algoritmisointi ja ohjelmointi, 1998 .
↑ Nils J. Nilsson. Tekoäly ja uusi synteesi, 1998 .
↑ Melikhov A. N. Suunnatut graafit ja äärelliset automaatit, 1971 .
↑ Lubentsova V. S. Matemaattiset mallit ja menetelmät logistiikassa, 2008 .
↑ Evstigneev V. A. Graafiteorian soveltaminen ohjelmointiin, 1985 .
↑ Paniotto V. I. Ihmissuhteiden rakenne: tutkimusmetodologia ja matemaattiset menetelmät, 1975 .
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriset laitteistomallit ja algoritmit CAD:ssa, 1990 .
↑ Kormen T. H. et al. Algoritmit: rakentaminen ja analyysi, 2009 .
↑ Graafeiden ja verkkojen teoria ATC - prosessien mallintamisessa , 2009 .
↑ Majidov T. I., Baskin I. I., Antipin I. S., Varnek A. A. Johdatus kemoinformatiikkaan, 2013-2016 .
↑ Yablonsky G.S., Bykov V.I., Gorban A.N. Katalyyttisten reaktioiden kineettiset mallit, 1983 .
↑ Topologian ja graafiteorian kemialliset sovellukset , 1987 .
↑ Deza M. M., Sikirich M. D. Kemiallisten graafien geometria: polycycles and bipolycycles, 2013 .
↑ Kemiallinen graafiteoria: johdanto ja perusteet , 1991 .
↑ Fomin G.P. Matemaattiset menetelmät ja mallit kaupallisessa toiminnassa, 2009 .
↑ 1 2 Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 .

Kirjallisuus

Akimov O. E. Diskreetti matematiikka: logiikka, ryhmät, graafit. 2. painos, lisä. M.: Basic Knowledge Laboratory, 2003. 376 s.: ill. ISBN 5-93208-025-6 .
Alon N., Spencer J. Probabilistinen menetelmä / Per. 2. englanti toim. M.: BINOM. Knowledge Laboratory, 2013. 320 s., ill. ISBN 978-5-9963-1316-7 .
Basaker R., Saati T. Äärilliset graafit ja verkot / Per. englanniksi V. N. Burkov, S. E. Lovetsky, V. B. Sokolov. A. I. Teimanin toimituksella. M.: Nauka, 1974. 366 s., ill.
Berge K. Graafisten teoria ja sen sovellukset / Per. ranskasta, kirjoittanut A. A. Zykov. Moskova: Publishing House of Foreign Literature, 1962. 319 s., ill.
Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Matematiikan oppikirjan sivujen takana. M.: Enlightenment, 1996. 320 s., ill. ISBN 5-09-006575-6 .
Goodman S., Hidetniemi S. Johdatus algoritmien kehittämiseen ja analysointiin. M.: Mir, 1981. 366 s., ill.
Deza M. M., Sikirich M. D. Kemiallisten graafien geometria: polycycles and bipolycycles. M.—Izhevsk: Tietojenkäsittelytieteen laitoksen kustantamo, 2013. 384 s., ill. ISBN 978-5-4344-0130-2 .
Distel R. Graafiteoria / Per. englannista. Novosibirsk: Matematiikan instituutin kustantamo, 2002. 225 s., ill. ISBN 5-86134-101-X.
Evstigneev V. A. Graafiteorian soveltaminen ohjelmointiin / Toim. A.P. Ershova. M.: Nauka, 1985. 352 s., ill.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Graafiteorian luentoja / Toim. A.P. Ershova. M.: Nauka, 1990. 383 s., ill. ISBN 5-02-013992-0 .
Zykov A. A. Graafiteorian perusteet. M.: Vuzovskaya kniga, 2004. 662 s.: ill. ISBN 5-9502-0057-8 .
Kamenetsky I. S., Marshak B. I., Sher Ya. A. Arkeologisten lähteiden analyysi: formalisoidun lähestymistavan mahdollisuudet. Ed. 2. M.: IA RAN, 2013. 182 s.: ill. ISBN 978-5-94375-153-0 .
Karpov D. V. Graafiteoria. 2017 tai myöhemmin. 555 s., ill.
Kormen T. Kh., Leyzerson Ch. I., Rivest R. L., Stein K. Algoritmit: rakentaminen ja analyysi. 2. painos : Per. englannista. Moskova: Williams Publishing House, 2009. 1290 s., ill. ISBN 978-5-8459-0857-5 (venäjä). ISBN 0-07-013151-1 (englanniksi).
Christofdes N. Graafiteoria. Algoritminen lähestymistapa. Per. englannista. E. V. Vershkova ja I. V. Konovaltseva. Alla. toim. G. P. Gavrilova. M.: Mir, 1978. 432 s., ill.
Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriset laitteistomallit ja algoritmit CAD:ssa. Moskova: Radio ja viestintä, 1990. 214 s., ill. ISBN 5-256-00748-3 .
Lubentsova V.S. Matemaattiset mallit ja menetelmät logistiikassa / Toim. V.P. Radchenko. Samara: Publishing House of the Samara State Technical University, 2008. 157 s.: ill. ISBN 978-5-7964-1140-7 .
Majidov T. I., Baskin I. I., Antipin I. S., Varnek A. A. Johdatus kemoinformatiikkaan. Osat 1-4. Kazan: Kazan University Press, 2013-2016.
Melikhov A. N. Orientoidut graafit ja äärelliset automaatit. M.: Nauka, 1971. 416 s., ill.
Yhdellä vedolla. Kuvioiden piirtäminen yhdellä jatkuvalla viivalla / Comp. Ja. I. Perelman. L .: Viihdyttävän tieteen talo, 1940. Alkaen 17 kuva.
Ore O. Kaaviot ja niiden käyttö / Per. englannista. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 s.: ill.
Ore O. Graafiteoria. 2. painos stereotypia. / Per. englannista. I. N. Vrublevskaja. Ed. N. N. Vorobieva. M.: Nauka, 1980. 336 s.: ill.
Paniotto VI Ihmissuhteiden rakenne: metodologia ja matemaattiset tutkimusmenetelmät. Kyiv: Naukova Dumka, 1975. 124 s., ill.
Perelman Ya. I. Elävä matematiikka. Matemaattisia tarinoita ja arvoituksia. Ed. 8, tarkistettu. ja ylimääräistä /Toim. ja ylimääräisillä V. G. Boltyansky. M.: Nauka, 1967. 160 s. sairaalta.
Keisarillisen tiedeakatemian konferenssin kokouspöytäkirjat vuosina 1725-1803. Osa I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Pietari: IAN-paino, 1897. 883 s.
Romanovsky IV Diskreetti analyysi. 3. painos, tarkistettu. ja ylimääräistä Pietari: Nevskin murre; BHV-Petersburg, 2003. 320 s.: ill. ISBN 5-7940-0114-3 . ISBN 5-94157-330-8 .
Tutt W. Graafiteoria / Per. englannista. G. P. Gavrilova. M.: Mir, 1988. 424 s., ill. ISBN 5-03-001001-7 .
Graafeiden ja verkkojen teoria ATC-prosessien mallintamisessa : Proc. korvaus / Comp. V. A. Karnaukhov. Uljanovsk: UVAU GA (I), 2009. 63 s.
Wilson R. Johdatus graafiteoriaan / Per. englannista. I. G. Nikitina. Ed. G. P. Gavrilova. M.: Mir, 1977. 207 s.: ill.
Fleishner G. Euler-kaaviot ja niihin liittyvät ongelmat / Per. englannista. V. A. Evstigneeva, A. V. Kostochki ja L. S. Melnikova. Ed. L.S. Melnikova. M.: Mir, 2002. 335 s.: ill. ISBN 5-03-003115-4 (venäjä). ISBN 0-444-88395-9 . [Fleischner H. Eulerian graafit ja niihin liittyvät aiheet. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
Fomin G.P. Matemaattiset menetelmät ja mallit kaupallisessa toiminnassa: oppikirja. 3. painos, tarkistettu. ja ylimääräistä M.: Rahoitus ja tilastot; INFRA-M, 2009. 637 s.: ill. ISBN 978-5-279-03353-9 (Rahoitus ja tilastot). ISBN 978-5-16-003660-1 (INFRA-M).
Frich R., Peregud E. E., Matsievsky S. V. Graafiteorian valikoituja lukuja: Oppikirja / Per. hänen kanssaan. E. E. Pereguda; Paul toim. S. V. Matsievsky. Kaliningrad: Venäjän valtionyliopiston kustantamo. I. Kant, 2008. 204 s.: ill. ISBN 978-5-88874-880-0 .
Harary Frank. Graafiteoria / Per. englannista. V. P. Kozyreva. Ed. G. P. Gavrilova. 2. painos. M.: Pääkirjoitus URSS, 2003. 296 s.: ill. ISBN 5-354-00301-6 .
Harari F., Palmer E. Graafisten luettelo / Per. englannista. G. P. Gavrilova. M.: Mir, 1977. 324 s.: ill.
Topologian ja graafiteorian kemialliset sovellukset / Per. englannista. Ed. R. King. M.: Mir, 1987. 560 s.: ill.
Shalyto A. A. Loogisten ohjausongelmien algoritmisointi ja ohjelmointi. Pietari: SPbGU ITMO, 1998. 56 s., ill.
Yablonsky GS, Bykov VI, Gorban' AN Katalyyttisten reaktioiden kineettiset mallit. Novosibirsk: Nauka, 1983. 253 s.: ill. ISBN 5-354-00301-6 .
Bondy JA, Murty USR Graph Theory. Springer, 2008. 651 s. ISSN 0072-5285. ISBN 978-1-84628-969-9 . e -ISBN 978-1-84628-970-5 . DOI 10.1007/978-1-84628-970-5.
Kemiallinen graafiteoria : johdanto ja perusteet / toimittaneet D. Bonchev ja D. Rouvray. New York: Abacus Press, 1991. ISBN 0-85626-454-7 .
M. Camille Jordan. Sur les assemblages de lignes // J. Reine Angew. Matematiikka. 1869 Voi. 70. S. 185-190.
Reinhard Diestel. graafiteoria. GTM 173, 5. painos 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, osa 173. ISBN 978-3-662-53621-6 .
Leonhardus Eulerus. Solutio problematis ad geometriam situs pertiminentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. S. 128-140.
Gross JL, Yellen J. Graafiteoria ja sen sovellukset. toinen painos. Boca Raton – Lontoo – New York: Chapman & Hall/CRC, 2006.
Gross JL, Yellen J. Graafiteorian käsikirja. CRC Press , 2004. ISBN 978-1-58488-090-5 . s. 35.
Frank Harary . Elämäkerrallinen luonnos ACM SIGACT -verkkosivustolla , 4. tammikuuta 2005.
Denes Konig. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.
Denes Konig. Äärillisten ja äärettömien graafien teoria. Boston: Birkhauser, 1990.
Nils J. Nilsson. Tekoäly ja uusi synteesi. San Francisco, Kalifornia: Morgan Kaufmann Publishes, Inc., 1998. 535 s. ISBN 1-55860-467-7 (kangas). ISBN 1-55860-535-5 (paperi).
JJ Sylvester (7. helmikuuta 1878) "Chemistry and algebra", Nature , 17 :284 . doi : 10.1038/017284a0 .

Linkit

Kirsanov M.N. Kaaviot vaahterassa. Moskova: Fizmatlit , 2007. 168 s. http://vuz.expponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
Sergei Melnikov. Sim ja Krem "elektronimikroskoopin alla" // Tiede ja elämä . - 1996. - Numero. 3 . - S. 144-145 . (Venäjän kieli)Artikkeli käsittelee peliä Gustav Simmonsin keksimässä Sim-kaaviossa.
WikiGrapp - graafiteorian selittävä sanakirja
Algoritmit ja lyhyet kuvaukset C++-ohjelmista
Diskreetti matematiikka, algoritmit, sovelmat, graafin visualisointi
Älykäs kuvaajan visualisointi (automaattinen sijoittaminen tasolle, lyhimmän polun löytäminen, keskustan löytäminen jne.)
Graafiteoriaohjelmisto
Visual Graph : ohjelma, joka tarjoaa käyttäjälle laajan valikoiman työkaluja ja menetelmiä tietojen visualisointiin ja etsimiseen kaavioista

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNF : 119384413 GND : 4113782-6 J9U : 987007538432705171 LCCN : sh85056471 NDL : 00562641 NKC : ph126555

Matematiikan alat

Portaali "Tiede"

Matematiikan perusteet joukko teoria matemaattinen logiikka logiikan algebra

Lukuteoria ( aritmetiikka )

Algebra
Algebra	Yhtälön ratkaisu
Lineaarialgebra	Vektorilaskenta matriiseja Tensorilaskenta Multilineaarinen algebra
Yleisalgebra	Kommutatiivinen algebra Edustusteoria Differentiaalialgebra Homologinen algebra Yleisalgebra Luokkateoria

Analyysi
Klassinen analyysi	Differentiaalilaskenta Integraalilaskenta
Funktion teoria	Harmoninen analyysi Quaternion Analysis Monimutkainen analyysi mittateoria Reaalimuuttujan funktioiden teoria toiminnallinen analyysi Variaatiolaskelma
Differentiaali- ja integraaliyhtälöt	Dynaamiset järjestelmät ja ergodinen teoria Differentiaaliyhtälöt tavallinen osittaisissa johdannaisissa Integraaliyhtälöt
Vektorianalyysi Globaali analyysi Katastrofi teoria Mukautettu analyysi Sujuva äärettömän pieni analyysi

Geometria ja topologia
Geometria	Algebrallinen geometria Analyyttinen geometria Euklidinen geometria Ei-euklidinen geometria Planimetria Stereometria
Topologia	Yleinen topologia Algebrallinen topologia Differentiaaligeometria ja topologia

Diskreetti matematiikka
Kombinatoriikka graafiteoria

Sovellettu matematiikka
Matemaattinen fysiikka Matemaattinen kemia matemaattinen biologia Matemaattiset tilastot Matemaattinen mallinnus Algoritmien teoria Numeeriset menetelmät matemaattinen taloustiede talousmatematiikka Todennäköisyysteoria Toimintatutkimus Peliteoria

Portaali "Matematiikka"
Luokka "Matematiikka"

Algoritmit kaavioissa
Etsi tiivisteitä	Bron-Kerboshin algoritmi Kosarayun algoritmi Malgrange-algoritmi Tarjanin algoritmi Demucronin algoritmi Likimääräinen algoritmi p-mediaanien löytämiseksi Pisimmän polun ongelma Topologinen lajittelu Sarana (graafiteoria) Kargerin algoritmi (minimileikkaus)
Virtauksen maksimointi	Dinitin algoritmi Malhotra-Kumara-Maheshwari-algoritmi Preflow Push Algorithm Ford-Fulkerson-algoritmi Edmonds-Karp-algoritmi liikenneverkko
Vastaava	Kukkapakkausalgoritmi Hopcroft-Karp algoritmi FKT-algoritmi
Viestintäkaaviot	Havel-Hakimi-algoritmi (graafinen sekvenssi) Kuvaajan muokkausetäisyys Isomorfisen osagraafin löytämisen ongelma
muu	Artikulaatiopuun algoritmi (hakee marginalisoinnin) Cuthill-Mackey-algoritmi (nauhan leveyden pienennys) Iteratiivinen pakkaus (idea rekursiosta) Malli: Hakualgoritmit kaavioista

Kaavion hakualgoritmit
Tietämättömät menetelmät	Kaksisuuntainen haku Säteen haku Leksikografinen leveys ensimmäinen haku Leveys ensimmäinen haku Hae kustannuskriteerin mukaan Ensimmäinen syvyyshaku Peruutushaku Hae kiipeämällä huipulle Syvyysrajoitettu haku Syvyys-ensin haku iteratiivisella syventämisellä
Tietoon perustuvat menetelmät	Alfa beta leikkaus Haara- ja sidontamenetelmä Hae ensimmäisen parhaan osuman perusteella A* B* D* Siirtymäkohdan löytäminen IDA* Rekursiivinen haku ensimmäisen parhaan osuman perusteella SMA*
Pikanäppäimet	Aalto-algoritmi Bellman-Ford-algoritmi Dijkstran algoritmi Johnsonin algoritmi Levitin algoritmi Floyd-Warshall-algoritmi Reunahaku
Vähintään ulottuva puu	Boruvkan algoritmi Primin algoritmi Kruskalin algoritmi
muu	British Museum Algorithm Edmondsin algoritmi Puun läpikulku Lähin naapuri -algoritmi matkustavan myyjän ongelmassa