Grafteori

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 18. april 2022; checks kræver 4 redigeringer .

Grafteori er en gren af diskret matematik , der studerer grafer . I den mest generelle forstand er en graf et sæt af punkter ( knudepunkter , knudepunkter), der er forbundet med et sæt linjer (kanter, buer) [1] . Teorien om grafer (det vil sige systemer af linjer, der forbinder givne punkter) er inkluderet i læseplaner for begyndere matematikere, fordi [2] [3] [4] [5] :

ligesom geometri , har synlighed;
ligesom talteori er den let at forklare og har komplekse uløste problemer;
har ikke et besværligt matematisk apparat ("kombinatoriske metoder til at finde den ønskede rækkefølge af objekter adskiller sig væsentligt fra klassiske metoder til at analysere systemers adfærd ved hjælp af ligninger" [6] );
har en udtalt anvendt karakter.

I over hundrede år har udviklingen af grafteori været domineret af firefarveproblemet . Løsningen af dette problem i 1976 viste sig at være et vendepunkt i grafteoriens historie, hvorefter dens udvikling fandt sted som grundlag for moderne anvendt matematik . Grafernes universalitet er uundværlig i design og analyse af kommunikationsnetværk [7] .

Grafteori, som et matematisk værktøj, er anvendelig både til adfærdsvidenskaberne ( informationsteori , kybernetik , spilteori , systemteori , transportnetværk ) og til rent abstrakte discipliner ( mængdelære , matrixteori , gruppeteori , og så videre) [ 8 ] [9] .

På trods af de forskelligartede, komplicerede, obskure og specialiserede termer er mange model- (skematiske, strukturelle) og konfigurationsproblemer omformuleret i grafteoriens sprog, hvilket gør det meget lettere at identificere deres begrebsmæssige vanskeligheder [10] . I forskellige vidensområder kan begrebet "graf" findes under følgende navne:

struktur ( civilingeniør );
netværk ( elektroteknik );
sociogram ( sociologi og økonomi );
molekylær struktur ( kemi );
navigationskort ( kartografi );
distributionsnet ( energi )

og så videre [11] .

Tidlig brug og opdagelser af grafer

Grafteori som en gren af anvendt matematik er blevet "opdaget" flere gange. Nøglen til at forstå grafteori og dens kombinatoriske essens afspejles i James Sylvesters ord : "Theory of offshoots ( engelsk ramification ) er en af teorierne om ren generalisering, hverken størrelsen eller positionen af objektet er afgørende for det. ; den bruger geometriske linjer, men de er ikke mere relevante end de samme linjer i genealogiske tabeller hjælper med at forklare reproduktionslovene .

Første brug af grafdiagrammet i videnskaben

Et diagram over en af varianterne af en graf - et træ - har været brugt i lang tid (selvfølgelig uden at forstå, at dette er en "graf"). Slægtstræet blev brugt til at visualisere familiebånd . Men kun den antikke kommentator til Aristoteles' værker, den fønikiske filosof og matematiker Porphyry , brugte billedet af et træ i videnskaben som en illustration af en dikotomisk opdeling i sit værk "Introduktion" ( græsk Εἰσαγωγή , lat. Isagoge ) til at klassificere filosofisk stofbegreb [ 13] .

Den første brug og "opdagelse" af grafteori

Den schweiziske , preussiske og russiske matematiker Leonhard Euler var i en artikel (på latin , udgivet af St. Petersburg Academy of Sciences ) om løsningen af det berømte Königsberg-broproblem , dateret 1736, den første til at anvende grafteoriens ideer ved at bevise nogle udsagn. Samtidig brugte Euler ikke selve udtrykket "graf" eller nogen termer for grafteori eller billeder af grafer [14] . Leonhard Euler betragtes som grafteoriens (såvel som topologiens ) fader, som opdagede konceptet med en graf [15] , og 1736 betegnes som fødselsåret for grafteorien [16] .

Den anden "opdagelse" af grafer

I 1847 udviklede den tyske fysiker Gustav Kirchhoff faktisk teorien om træer ved at løse et ligningssystem for at finde mængden af strøm i hvert kredsløb i et elektrisk kredsløb . I stedet for et elektrisk kredsløb studerede Kirchhoff faktisk den graf, der svarer til den, og viste, at for at løse et ligningssystem, er det ikke nødvendigt at analysere hver cyklus af grafen, det er nok kun at overveje uafhængige cyklusser defineret af enhver spænding grafens træ [15] .

Et eksempel på et elektrisk kredsløb, dets tilsvarende graf og et spændingstræ
Elektrisk kredsløb 'N
Tæller G svarende til det elektriske kredsløb
Spændende træ T af graf G

Den tredje "opdagelse" af grafer

I 1857 opdagede den engelske matematiker Arthur Cayley , mens han arbejdede med praktiske problemer i organisk kemi , en vigtig klasse af graftræer . Cayley forsøgte at opregne de kemiske isomerer af mættede (mættede) kulbrinter C n H 2n+2 med et fast antal n carbonatomer [ 15] .

De første fire lineære alkaner (mættede kulbrinter)
Metan CH 4
Ethan C2H6 _ _ _
Propan C3H 8 _ _
Butan C 4 H 10

Den fjerde "opdagelse" af grafer

I 1859 kom den irske matematiker Sir William Hamilton med spillet Around the World. Dette spil brugte et dodecahedron , hvor hvert af dets 20 hjørner svarer til en berømt by. Spilleren blev forpligtet til at gå "jorden rundt", det vil sige at gå langs kanterne af dodekaederet på en sådan måde, at han passerede gennem hvert hjørne nøjagtigt én gang [15] .

Hamiltons spil "Around the World"
At krydse hjørnerne af et dodekaeder på et polyeder
Omgå toppunkterne på projektionen af dodekaederet på planet

Den femte "opdagelse" af grafer

I 1869, uafhængigt af Arthur Cayley , udtænkte og udforskede den franske matematiker Camille Jordan (især i avisen "Sur les assemblages de lignes") træer inden for ren matematik. Samtidig brugte Jordan udtrykkene grafteori "vertex" ( fr. sommet ) og "edge" ( fr. arête ), men i stedet for udtrykket "graf" var der "forbindelse af kanter" ( fr. assemblage d 'arêtes ) eller blot "forbindelse" ( fr montering ). Jordan brugte ikke tegninger [17] . Samtidig havde Jordan ikke mistanke om betydningen af hans opdagelse for organisk kemi [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 sembleable system un assemblage d'arêtes , dont x , y , z , u , … sont les sommets.

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

Oprindelsen af ordet "tælle"

Den første optræden af ordet "graf" i betydningen grafteori fandt sted i 1878 i en kort note (på engelsk ) af den engelske matematiker James Sylvester i tidsskriftet Nature og har en grafisk oprindelse som en generalisering af begreberne " Kekule diagram " og "kemikograf" [18] [19] .

Hver invariant og kovariant bliver således udtrykbar ved en graf , der er nøjagtig identisk med et Kekuléan-diagram eller en kemigraf.

— Silvester JJ Kemi og algebra (kursiv som i originalen) [20]

I oversættelse:

Således er hver invariant og kovariant udtrykt ved en graf , nøjagtig identisk med Kekule- diagrammet eller kemografen.

— Sylvester J. J. Chemistry and Algebra, 1878 (udtryk original)

Begyndelsen af den systematiske brug af ordet "graf" og diagrammer af grafer

Vi tegner sædvanligvis prikker, der repræsenterer mennesker, bosættelser, kemiske molekyler osv., og forbinder disse prikker med linjer, der repræsenterer relationer. Det er sociogrammer (i psykologi ), simplices (i topologi ), elektriske kredsløb (i fysik ), organisationsdiagrammer (i økonomi ), kommunikationsnetværk , stamtræer osv. I begyndelsen af det 20. århundrede var den ungarske matematiker Denes König den første til at foreslå at kalde disse skemaer "grafer" og studere deres generelle egenskaber [8] . I 1936 blev verdens første bog om grafteori (på tysk ) af Denes König "The Theory of Finite and Infinite Graphs" udgivet med de fleste af resultaterne over de sidste 200 år, startende fra 1736 - datoen for udgivelsen af den første papir af Leonhard Euler om grafteori med en løsning problemer om Königsberg broer [16] . Især er der i Koenigs bog et generelt afsnit om Koenigsberg-broproblemet og dominoproblemet (konstruktion af en lukket kæde af alle dominobrikker i henhold til spillets regler) [21] [22] .

Grafteoriens historie

Grafteori (med andre ord systemer af linjer, der forbinder givne punkter) er meget begyndervenlig [3] :

har geometrisk klarhed;
har matematisk indhold;
har ikke et besværligt matematisk apparat.

"Ligesom talteori er grafteori begrebsmæssigt simpel, men rejser komplekse uløste problemer. Ligesom geometrien er den visuelt tiltalende. Disse to aspekter, sammen med deres forskellige anvendelser, gør grafteori til et ideelt emne til inklusion i matematikpensum .

Fremkomsten af denne gren af matematikken i det 18. århundrede er forbundet med matematiske gåder. I temmelig lang tid var grafteori "ikke seriøs" og var helt forbundet med spil og underholdning. Denne skæbne for grafteori gentager skæbnen for sandsynlighedsteori , som også først fandt sin anvendelse kun i gambling [3] .

En kort kronologi over begivenheder i udviklingen af grafteori [23]

År	Begivenhed
1735	Eulers præsentation af en artikel om grafteori på St. Petersburg Academy of Sciences
1736	Året betragtes som fødselsåret for grafteori
1741	Udgivelse (dateret 1736) af Eulers artikel om grafteori ved St. Petersburg Academy of Sciences
1852	Francis Guthrie rapporterer firefarveproblemet til Augustus de Morgan
1879	1879 historisk publikation, der forklarer Arthur Cayleys fire-farve problem
1879	Det fejlagtige "bevis" for firefarveproblemet af Alfred Kempe
1890	Percy John Heawood opdagede en fejl i Kempes "bevis", beviste, at teoremet er sandt, hvis "fire" er erstattet af "fem", generaliserede begrebet "landkort" fra et plan til lukkede overflader og formulerede Heawoods formodning
1927	Lev Semyonovich Pontryagin beviste (men publicerede ikke) Pontryagin-Kuratovsky-sætningen
1930	Kazimierz Kuratowski udgav (uafhængigt af Pontryagin) Pontryagin-Kuratovsky-sætningen
1936	Verdens første bog om grafteori af Denes Koenig "The Theory of Finite and Infinite Graphs" er udkommet
1968	En gruppe matematikere fra forskellige lande beviste Heawoods formodning
1976	En gruppe matematikere har udført det første computerbevis for firefarvesætningen
1977	Frank Harari grundlagde tidsskriftet Graph Theory

Positionsgeometri

Grafteoriens (såvel som topologiens ) fader er den schweiziske matematiker og mekaniker Leonhard Euler (1707-1783) [12] , som skrev en artikel med en løsning på Königsberg-broproblemet . Euler skrev [24] :

Ud over den gren af geometrien, der beskæftiger sig med størrelser, og som der altid har været den største opmærksomhed på, er der en anden gren, hidtil næsten ukendt, som Leibniz først nævnte og kalder den positionens geometri [geometria situs]. Denne gren beskæftiger sig kun med bestemmelsen af positionen og dens egenskaber, den inkluderer ikke nogen målinger eller beregninger forbundet med dem ...

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

Ydermere skriver Euler, at det ikke er klart, hvilke problemer og metoder til at løse dem, der vedrører positionsgeometri. Ikke desto mindre anså Euler Königsberg-broerne for netop en sådan opgave, som artiklens titel indikerer. Faktisk skrev Gottfried Leibniz , senest i 1679, i et brev til Christian Huygens [24] :

Jeg er ikke tilfreds med algebra i den forstand, at den ikke tillader, at man opnår hverken de korteste beviser eller de smukkeste konstruktioner af geometri. Derfor, på grund af dette, tror jeg, at vi har brug for en anden måde at analysere, geometrisk eller lineær, som ville arbejde direkte med position på samme måde, som algebra arbejder med kvantitet ...

Leibniz, der introducerede begrebet analyse situs (positionsanalyse), lagde ikke grundlaget for en ny matematisk disciplin, men angav retningen for fremtidig forskning [24] .

Königsberg-broproblemet

Udgivelsen af en artikel af Leonhard Euler "Løsning af et problem relateret til positionens geometri" om løsningen af problemet med Königsberg-broer har følgende historie:

Den 26. august ( 6. september ) 1735 [25] præsenterede Euler en artikel på konferencen for St. Petersburgs Videnskabsakademi [16] ;
i 1736 sendte Euler to breve:

13. marts ( 24 ), 1736 - et brev til Johann Jacob Marinoni , en østrigsk astronom og matematiker, som udelukkende er viet til problemet med Königsberg-broer [26] ;
3. april ( 14 ), 1736 - et brev til Carl Leonard Gottlieb Oehler , en tysk politiker og astronom, i slutningen af hvilket der er en tale om artiklens hovedideer [26] ;

i 1741 i St. Petersborg , endelig blev Eulers artikel publiceret på latin med datoen 1736 [26] :

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

Oversat [27] :

Leonard Euler. Løsning af et problem relateret til positionsgeometri / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, s. 128-140.

Da udgivelsen af Eulers papir er dateret 1736 (og begge bogstaver også), er dette år angivet som fødselsdatoen for grafteorien [16] .

Euler formulerede i sin artikel problemet med syv Königsberg-broer [27] som følger:

I byen Königsberg i Preussen er der en ø, der hedder Kneiphof ; floden der omgiver den er delt i to grene, hvilket kan ses på figuren. Denne flods grene krydses af syv broer a , b , c , d , e , f og g . I forbindelse med disse broer blev der rejst spørgsmålet, om det er muligt at gå over dem på en sådan måde, at man passerer over hver af disse broer, og præcis én gang.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

I slutningen af artiklen skrev Euler konklusionerne ned i et ganske moderne sprog [28] :

20. Følgende regel gør det derfor i alle mulige tilfælde muligt direkte og uden besvær at finde ud af, om det er muligt at gennemføre en tur over alle broerne uden gentagelser:

Hvis der er mere end to områder, hvortil et ulige antal broer fører, kan man med sikkerhed sige, at en sådan gåtur er umulig.

Hvis der dog kun er to områder, hvortil et ulige antal broer fører, så er vandringen mulig, forudsat at den starter i et af disse to områder.

Hvis der endelig ikke er et område, hvortil et ulige antal broer fører, er en gåtur med de nødvendige forhold mulig, og den kan starte i ethvert område.

Derfor kan det stillede problem ved hjælp af denne regel løses fuldstændigt.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

Firefarvesætningen

Firefarvesætningen er det mest berømte udsagn i grafteori (og måske i hele matematikken), som ikke er blevet bevist i lang tid (eller måske aldrig bevist). Dette legendariske problem kan forklares af enhver matematiker til enhver forbipasserende inden for fem minutter, hvorefter begge, der forstår problemet, ikke vil være i stand til at løse det. Følgende citat er fra et nu historisk papir fra 1965 af den amerikanske matematiker Kenneth O. May [29] :

[Det antages, at] ethvert kort på boldens plan eller overflade kun kan farves med fire farver på en sådan måde, at ikke to tilstødende lande har samme farve. Hvert land skal bestå af ét forbundet område , og lande kaldes sammenhængende, hvis de har en fælles grænse i form af en linje (og ikke kun ét fælles punkt). Denne formodning er tæt knyttet til de mest fashionable områder af grafteori, og i den gren af matematik, der kaldes kombinatorisk topologi, fungerede den som en katalysator. I mere end et halvt århundrede har mange matematikere (nogle siger alle) forsøgt at løse dette problem, men har kun været i stand til at bevise formodningen i isolerede tilfælde... Det er enstemmigt indrømmet, at formodningen er sand, men det er usandsynligt at det vil blive bevist i almindelighed. Det ser ud til at være bestemt for et stykke tid at bevare udmærkelsen af at være både det enkleste og mest lokkende uløste problem i matematik.

— Maj KO Oprindelsen af den firfarvede formodning / Isis. 56 (1965). s. 346-348

Firefarvesætningen er relateret til grafteori, da hvert kort genererer en graf som følger:

lande (inklusive den ydre region) er hjørner;
hjørnerne af tilstødende lande er forbundet med en kant.

Denne graf er tegnet på et plan uden krydsende kanter. Firefarvesætningen bevises, hvis det er bevist, at hjørnerne af enhver sådan graf kan farves med fire farver, så tilstødende hjørner har forskellige farver [30] .

Firefarvesætningen har en legendarisk historie, interessant og til tider uforståelig [29] [31] :

der er ubekræftede rapporter om, at August Möbius var klar over dette problem i 1840;
det vides med sikkerhed, at Francis Guthrie , en sydafrikansk matematiker og botaniker, den 23. oktober 1852 informerede den skotske matematiker og logiker August de Morgan om dette problem, hvorefter diskussioner blev holdt i snævre kredse af matematikere og amatører. ;
1879 historisk publikation, der forklarer problemet

Cayley Arthur. Om farvelægning af kort // Proceedings of the Royal Geographical Society. 1879 Bd. 1, nr. 4. S. 259–261

ejet af Arthur Cayley , engelsk matematiker. Nu får problemet mere omtale;

i samme 1879 blev et fejlagtigt "bevis" for problemet offentliggjort

Kempe AB om de fire farvers geografiske problem // American Journal of Mathematics. 1879 Bd. 2, nr. 3. S. 193–200

Engelsk kirkeadvokat og matematiker Alfred Kempe . Dette var ikke kun det første af mange fejlagtige "beviser", men også det mest "korrekte": baseret på ideerne i denne artikel var det muligt først at bevise, at fem farver er nok, og derefter at udføre en komplet computer bevis for firefarvesætningen;

en fejl i Kempes "bevis" efter 11 år i 1890 blev opdaget af den engelske matematiker Percy John Heawood , og i en artikel offentliggjort ved denne lejlighed

Heawood PJ Kortfarvesætninger // Quarterly Journal of Pure and Applied Mathematics. 24 (1890). s. 332-338

beviste også, at teoremet er sandt, hvis "fire" erstattes af "fem", og derudover generaliserede begrebet "landkort" fra et plan til lukkede overflader og formulerede Heawoods formodning ;

i 1968 beviste en gruppe matematikere fra forskellige lande Heawoods formodning;
I 1976 udførte amerikanske matematikere det første computerbevis for firefarvesætningen.

Pontryagin-Kuratovsky-sætningen

Grafteori indeholder topologiske aspekter. Det første resultat i denne retning er Eulers formel i grafteori , som han opnåede i 1736. Følgende resultat i form af Pontryagin-Kuratovsky-sætningen blev opnået kun 191 år senere: i 1927 beviste (men offentliggjorde ikke) den sovjetiske matematiker Lev Semyonovich Pontryagin dette resultat, og i 1930 udgav den polske matematiker Kazimierz Kuratowski det (uafhængigt af Pontryagin). Pontryagin-Kuratovsky-sætningen kaldes også Pontryagin-Kuratovsky-kriteriet [32] :

En plan graf er en graf, der kan tegnes på et plan uden at krydse kanter. En graf, der ikke kan tegnes på denne måde, kaldes ikke-plan . Nedenfor er vist to vigtige ikke-plane grafer, betegnet med og , som ikke kan tegnes i planet uden at krydse kanter. Disse to grafer adskiller sig fra andre ved, at kun de bruges i Pontryagin-Kuratovsky-kriteriet [33] . $K_{5}$ $K_{{3,3}}$

Legendariske ikke-planære grafer
Komplet graf med fem hjørner $K_{5}$
Komplet todelt graf (3, 3) $K_{{3,3}}$

Før fremkomsten af Pontryagin-Kuratovsky-kriteriet var det et meget vanskeligt problem i grafteorien at bevise om grafer er plane eller ikke-plane [33] .

Pontryagin-Kuratovsky teorem. En graf er plan, hvis og kun hvis den ikke på nogen måde indeholder grafer og . $K_{5}$ $K_{{3,3}}$

Til højre er to simple beviser uden ord på, at skelettet af en firedimensionel hyperkube ( tesseract ) som en graf er ikke-plan. Den øverste figur viser, at tesserakten indeholder en komplet graf med fem hjørner , mens den nederste figur viser en komplet todelt graf (3, 3) . $K_{5}$ $K_{{3,3}}$

Store legendariske udgaver

Tidlig grafteori - teorien om grafer før 1936, før udgivelsen af Koenigs bog [24] .

I 1936 blev verdens første bog om grafteori af den ungarske matematiker Denes König , The Theory of Finite and Infinite Graphs, udgivet på tysk:

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

Denne bog bestod af 248 sider (ekskl. forord, indholdsfortegnelse og bibliografi) og de fleste af resultaterne af grafteori i 200 år - fra datoen for udgivelsen af Leonhard Eulers artikel med løsningen af Königsberg-broproblemet [16] .

Moderne grafteori - grafteorier siden 1936, siden udgivelsen af Koenigs bog. Siden udgivelsen af Koenigs bog, men hovedsageligt siden slutningen af Anden Verdenskrig, har grafteori været i hastig udvikling. Denne vækst bestod ikke kun i stigningen i antallet af bøger om grafteori, men også i udviklingen af særlige aspekter af grafteori [16] :

topologisk grafteori ;
algebraisk grafteori ;
algoritmisk grafteori.

En af den moderne grafteoris fædre er Frank Harari , som i 1977 grundlagde tidsskriftet Graph Theory [34] [16] .

Frank Hararis bog Graph Theory er blevet en de facto klassiker [35] [36] .

Reinhard Distels bog "The Theory of Graphs" (modstået 5 udgaver) har ingen konkurrenter i den russisksprogede bibliografi. Denne kanon af et introduktionskursus i grafteori indledte identifikation af visse områder af undersøgelse og forskning [2] [37] .

Beskrivelse af tidlig grafteori

Tidlig grafteori varede præcis 200 år, fra det første papir om grafteori af Leonhard Euler i 1736 til den første bog om grafteori af Denes König i 1936. I forordet til bogen er det skrevet, at præsentationen af grafteori er begrænset til feltet absolutte grafer ( abstrakte grafer i moderne terminologi), og relativ grafteori ( topologisk grafteori i moderne terminologi) og enumerativ grafteori betragtes ikke . . Nedenfor er den fulde titel på Denes Koenigs bog og dens korte indholdsfortegnelse, bestående af kapiteltitler [16] [38] [39] .

Teori om endelige og uendelige grafer. Kombinatorisk topologi af endimensionelle komplekser ( tysk: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe , engelsk: Theory of finite and infinite graphs ).

Kapitel I. Fundamenter ( tysk die Grundlahen , engelske fonde ). Kapitel II. Euler- og Hamilton - vandringer ( tyske Eulersche und Hamiltonsche Linien , engelske Euler-stier og Hamilton-cykler ). Kapitel III. Labyrintproblemet ( tysk das Labyrinthenproblem , engelsk labyrintproblemet ) . Kapitel IV. Acykliske grafer ( tysk kreislose Graphen , engelske acykliske grafer ). Kapitel V. Centres of trees ( tysk Zentren der Bäume , engelsk centers of trees ). Kapitel VI. Særlige metoder til at studere uendelige grafer ( tysk Spezielle Untersuchungen über unendliche Graphen , engelske uendelige grafer ). Kapitel VII. Grundlæggende problemer for rettede grafer ( tysk Basisprobleme für gerichtete Graphen , engelske basisproblemer for rettede grafer ). Kapitel VIII. Nogle anvendelser af rettede grafer ( logik - spilteori - gruppeteori ) _ Kapitel IX. Cykler , stjerner og de tilsvarende lineære former ( tysk Zyklen und Büschel und die entsprechenden linearen Formen , engelske (dirigerede) cyklusser og stjerner og de tilsvarende lineære former ). Kapitel X. Sammensætning af cyklusser og stjerner ( tysk Komposition der Kreis und der Büschel , engelsk sammensætning af cyklusser og stjerner ). Kapitel XI. Faktorisering af regulære finite grafer ( tysk Faktorenzerlegung regulärer endlicher Graphen , engelsk factorization of regular finite graphs ). Kapitel XII. Faktorisering af regulære finite grafer af grad 3 _ Kapitel XIII. Faktorisering af regulære uendelige grafer _ _ Kapitel XIV. Adskille toppunkter og sæt af toppunkter ( tysk trennende Knotenpunkte und Knotenpunktmengen , engelsk adskille toppunkter og sæt toppunkter ).

Repræsentationsproblemer i grafteori

Problemer med terminologi

Den almindeligt nævnte kendsgerning om den brogede og uordnede terminologi og notation i grafteori er til dels en konsekvens af, at specialister fra meget forskellige vidensområder er interesserede i denne videnskab [40] . Derudover er der en vis tilbageslag i selve grafteoriens terminologi , hvilket komplicerer studiet og præsentationen af grafteori en smule. Med særlig omhu er man nødt til at anvende begreber som "rute", "sti" og "kæde", som, hvilket betyder næsten det samme, kan få forskellige specifikke betydninger for forskellige forfattere [36] .

Her er hvad Frank Harari skrev i begyndelsen af sin klassiske bog (genudgivet i 2003) [41] [42] .

De fleste grafteoretikere bruger deres egen terminologi i bøger, artikler og foredrag. Ved konferencer om grafteori mener hver taler, for at undgå misforståelser, det er nødvendigt først og fremmest at bestemme det sprog, han vil bruge. Selv ordet "tælle" er ikke helligt. Nogle forfattere definerer faktisk en "graf" som en graf, mens andre mener begreber som en multigraf, pseudograf, rettet graf eller netværk. Det forekommer os, at ensartethed i grafteoriens terminologi aldrig vil

vil ikke blive opnået, men måske er det nytteløst.

- Harary Frank. Graph Theory, 2003

Den mest radikale opfattelse er fra konstruktiv matematiks synspunkt [43] [44] .

... det forekommer os ikke så vigtigt, hvordan man kalder de punkter, der er forbundet med linjer: "graf", "digraf", "multigraf", "pseudograf". Grafer bygget på grundlag af virkelige strukturer er for forskellige til at blive klassificeret i henhold til de funktioner, som grundlæggerne af denne videnskab talte om. Vi er i tvivl: er det overhovedet nødvendigt at skelne mellem begreber som "kant" - "bue", "kontur" - "cyklus", "sti" - "rute", "center" - "tyngdepunkt" osv. Når alt kommer til alt , på I praksis (og grafer anvendes hovedsageligt), er alle disse rækker af udtryk glemt og erstattet af et hvilket som helst ord: "graf", "kant", "cyklus", "sti", "center". Det er svært for en datalog at forstå, hvorfor en graf med en loop ikke længere er en fuldgyldig graf, men kun en "pseudograf". ... Er en datalog eller enhver anden specialist ikke i stand til selv at bestemme, hvilket ord der skal bruges - "sti" eller "rute" - og gennem hvilke bogstaver det er bedre at udpege sin rute-sti? En graf er et visuelt billede, hvis fortjeneste netop ligger i, at det kræver et minimum af ord og symboler.

— Akimov O. E. Diskret matematik: logik, grupper, grafer, 2003

Programmører bidrager også til udbredelsen af terminologien [45] .

I programmeringsverdenen er der ingen konsensus om, hvilket af de to udtryk "graf" eller "netværk" der er mest almindeligt. Vi har valgt udtrykket "netværk", da det ser ud til at være mere almindeligt i anvendelsesområder.

- Goodman S., Hidetniemi S. Introduktion til udvikling og analyse af algoritmer, 1981

Men i de seneste års udgaver taler vi allerede om "for det meste standard" terminologi [46] [47] .

Den terminologi, der bruges i denne bog, er for det meste standard. Alternativer findes selvfølgelig, og nogle af dem er givet i den første definition af begrebet.

— Diestel R. Graph Theory, 2002. Reinhard Diestel. Grafteori, 2016

For eksempel i det grundlæggende arbejde inden for kybernetik "Algorithms: construction and analysis" anvendes standardterminologi [48] .

Når vi beskriver køretiden for en algoritme på en given graf , definerer vi normalt størrelsen af inputgrafen i form af antallet af dens hjørner og antallet af grafkanter, dvs. vi beskriver størrelsen af inputdataene med to snarere end én parameter. $G=(V,E)$ $|V|$ $|E|$

- Kormen T. H. et al. Algoritmer: konstruktion og analyse, 2009

Problemer med graftegning

Abstrakte grafer kan repræsenteres på et plan på forskellige måder. Spørgsmålet om, hvorvidt disse grafbilleder er isomorfe , det vil sige om disse grafbilleder er isomorfe i forhold til en enkelt abstrakt graf, kan være ikke-trivielt. Nogle gange er dette problem let at løse. For eksempel er de følgende to grafer ikke isomorfe, fordi de har forskelligt antal hjørner [49] .

Nonisomorfe grafer: forskelligt antal hjørner
tre toppe
fire toppe

De næste to grafer er også ikke-isomorfe, fordi de har forskelligt antal kanter [49] .

Nonisomorfe grafer: forskelligt antal kanter
fem ribben
seks ribben

Men for at vise, at de næste to grafer ikke er isomorfe, kræves der et mere subtilt argument. Den første graf har en lukket gennemløb af alle hjørner én gang ( Hamiltonsk cyklus ):

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

mens den anden graf ikke gør det. Det vil sige, at for enhver nummerering af hjørnerne på den anden graf er det umuligt at opnå en Hamilton-cyklus på den, der svarer til Hamilton-cyklussen i den første graf [49] .

Nonisomorfe grafer: forskellige toppunkter
Der er en Hamilton-cyklus
Ingen Hamilton-cyklus

Hvis det ikke umiddelbart er klart, hvordan man beviser, at grafer ikke er isomorfe, så kan spørgsmålet om tilstedeværelsen af isomorfi vise sig at være svært. De følgende to isomorfe grafer er ikke isomorfe ved første øjekast [49] .

Isomorfe grafer tilsyneladende ikke-nisomorfe
Cirkulær graf $C_{7}(1,2)$
Cirkulær graf $C_{7}(1,3)$

Litteraturproblemer

Hvilke kilder er bedre at fokusere på, når grafteori præsenteres? Her er nogle boganmeldelser.

Harary Frank. Graph Theory, 2003.

Frank Hararis bog er blevet en de facto klassiker [35] [36] .

Tredive år er gået siden udgivelsen af monografien "Graph Theory" af F. Harari, men dens attraktive kvaliteter er slet ikke falmet. Foreningen af terminologi, udført af forfatteren og bredt udbredt takket være denne bog, er blevet almindeligt accepteret. Undervisningen i grafteori ved hjælp af F. Hararis bog udføres på mange universiteter i vores land.

- Forord af V.P. Kozyrev (2002) til bogen: Harari Frank. Graph Theory, 2003 Herbert Fleischners Euler-grafer og relaterede emner giver en liste over bøger, der anbefales som en introduktion til grafteori. Det er bøger på engelsk, hvoraf kun den første er oversat til russisk: dette er Frank Hararis bog The Theory of Graphs [50] .

Distel R. Graph Theory, 2002.

... nu er der oversættelser nok til russisk af lærebøger om grafteori, primært Distels vidunderlige bog. Og desværre kun Distels bøger.

...Det var arbejdet med oversættelsen af 5. udgave af Distels bog, der stimulerede fortsættelsen af arbejdet med min bog i 2017 efter en længere pause. Jeg lagde mærke til, hvor stor den " symmetriske forskel " mellem hans bog og min er.

- Karpov D.V. Grafteori. 2017 eller senere

Klassifikation af grafteori

Klassifikationen af grafteori skal indsamles fra forskellige kilder.

Grafteori [16] :

abstrakte grafer ("almindelige" grafer);
topologisk grafteori ;
opregning af grafer ;
algebraisk grafteori ;
algoritmisk grafteori.

Grafteori [51] :

elementær-kombinatorisk grafteori;
logisk grafteori;
algebraisk grafteori ;
matroider ;
tilbagevendende egenskaber af grafer;
tilfældige grafer ;
uendelige grafer.

Analytisk grafteori [52] :

Grundlæggende vilkår for grafteori

Grafteori, som enhver moderne matematisk model , bruger stenografiske symboler, der sparer tænkning og gør den matematiske model fleksibel og effektiv [53] .

Her gives delikat og kortfattet de første led i hoveddelen af grafteorien. De fleste af standardudtrykkene er så beskrivende, at de er nemme at fordøje. Det er nødvendigt at definere en række begreber strengt nok for at kunne bruge dem bredt i fremtiden [41] [54] [55] .

Grafer ( engelske grafer )

En kort, men repræsentativ oversigt over de vigtigste definitioner af grafteori relateret til begrebet en ordentlig graf. Disse begreber introduceres den ene efter den anden ganske systematisk, om end noget kedeligt [56] [57] [58] .

En graf er to endelige disjunkte sæt , og den anden består af 2 - elements undermængder af den første. Notation: [59] , hvorog. $G=(V,E)$ $E\subseteq V\times V$ $V\cap E=\varnothing$

Et grafens toppunkt (knudepunkt, punkt) er et element igrafsættet. Betegnelse:.

V

v\in V(G)

En grafkant (linje, bue) er et element igrafsættet. Betegnelse:.

E

e\in E(G)

En kant kunne i ældre udgaver også kaldes en gren , et led [60] eller en kurve [61] . Typisk er en graf repræsenteret af et diagram , som ofte kaldes en graf. Rækkefølgen af en graf er antallet af hjørner i grafen . Betegnelse :. Antallet af grafkanter er angivet med .

G

|G|

\|G\|

En tom graf er en graf uden hjørner. Betegnelse :.

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

En triviel graf er en graf af orden 0 eller 1.

Eksempler på grafer
Fra venstre mod højre: bestil 1 graf, bestil 2 graf med 1 kant, bestil 4 graf med 4 kanter, bestil 8 graf med 12 kanter

Endespidserne eller enderne af en kant er de to knudepunkter, der definerer en kant. En kant forbinder dens endespidser. En kant og dens endepunkt er indfaldende, eller den ene støder op til den anden . Mængden af alle kanter ved et toppunkt er angivet med . $v\in V(G)$ $E(v)$

Tilstødende eller tilstødende hjørner er to spidser, der falder ind mod den samme kant. Tilstødende kanter er kanter, der har en fælles ende. En komplet graf er en graf, hvis hjørner er parvis stødende op, det vil sige, at to vilkårlige hjørner er forbundet med en kant. Notation for en komplet graf medtoppunkter: [62] (nogle gange). Grafenkaldes en trekant .

n

K_n

K^n

K_{3}

Eksempler på komplette grafer
De første fem komplette grafer

En todelt graf eller bigraf er en graf, der tillader en opdeling af et sæt hjørnepunkter i to delmængder, således at:

enderne af enhver kant tilhører forskellige delmængder af partitionen;
hjørnerne i hver delmængde af partitionen er parvis ikke-tilstødende.

En komplet todelt graf er en todelt graf, hvor hver to hjørner fra forskellige delmængder af partitionen er tilstødende. Notationen for en komplet todelt graf med antallet af toppunkter i delmængder af partitionen og : [62] .

n

m

{\displaystyle K_{n,m))

Forskellige diagrammer af den komplette todelte graf (3, 3)
Kurve $K_{{3,3}}$
Kurve $K_{{3,3}}$
Kurve $K_{{3,3}}$
Kurve $K_{{3,3}}$

Graden eller valensen af et grafvertex er antallet af kanter, der falder ind på toppunktet. Vertex grad notation: [63] . $v$ $\deg v\equiv d(v)$

Et isoleret toppunkt på en graf er et toppunkt med graden nul. Grafens bagerste eller hængende toppunkt er toppunktet med første grad. Den mindste grad af grafens hjørnepunkter er angivet med , den maksimale grad - .

G

\min \deg G\equiv \delta (G)

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

En regulær eller homogen graf er en graf, hvis hjørner alle har samme grad. Med andre ord, for en sådan grafer dens grad.

G

\delta (G)=\Delta (G)

En r-regulær eller r-uniform graf er en graf med . Sådanne grafer kaldes også blot regulære eller homogene . En 3-regulær graf kaldes kubisk .

G

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

Hver kant på grafen falder ind i to hjørner, og hver kant bidrager med to til summen af graderne af grafens hjørner. Vi får den historisk første sætning af grafteori, bevist af Leonhard Euler i en artikel dateret 1736 (det første resultat af grafteori i samme artikel er løsningen af Königsberg-broproblemet). Sætning. Summen af graderne af en grafs hjørner er lig med det dobbelte af antallet af dens kanter. Konsekvens 1. I enhver graf er antallet af hjørner med ulige grader lige. Konsekvens 2. Enhver kubisk graf har et lige antal hjørner.

Eksempel på almindelige grafer
Kubikgraf med 4 hjørner
4-regulær graf med 6 spidser
5-regulær graf med 12 hjørner

Typer af grafer _

Fortsættelse af en kort, men repræsentativ opsummering af de vigtigste grafteoretiske definitioner relateret til begrebet en graf. For fuldstændighedens skyld oplister vi en række varianter af grafer [64] [65] [66] .

En isomorfi af to grafer er en en-til-en-korrespondance mellem sættene af deres hjørner, der bevarer tilstødende. Betegnelse:. $G\simeq H$

Det er klart, at en isomorfi er en ækvivalensrelation på grafer. Normalt skelnes der ikke mellem isomorfe grafer og er skrevet i stedet for , begrebet isomorfisme er meget brugt, når man afbilder grafer.

G=H

G\simeq H

En grafinvariant er et tal, der har samme værdi på isomorfe grafer. Det fulde sæt af invarianter definerer grafen op til isomorfi . For eksempel er antallet af hjørner og antallet af kanter på en graf et komplet sæt invarianter for enhver graf med ikke mere end 3 hjørner.

Et eksempel på isomorfe grafer
Vertex Crossing Chart $K_{4}$
Kort uden at krydse hjørner $K_{4}$

En undergraf af en graf er en graf, hvis spidser og kanter tilhører den originale graf. Den originale graf er overgrafen for dens undergraf. Med andre ord indeholder grafen grafen : . $G$ $G'$ $G\subseteq G'$

En kerneundergraf i en graf er en undergraf, der indeholder alle hjørnerne i dens epigraf. En genereret eller induceret undergraf af en graf er en undergraf, der indeholder alle kanterne af epigrafen for sættet af dens spidser, det vil sige, at to spidser af den genererede undergraf er tilstødende, hvis og kun hvis de støder op i epigrafen.

Eksempel på en graf og undergrafer
Kilde graf
En stilk, men ikke genereret undergraf
Genereret, men ikke en spændende undergraf

En multigraf er et endeligt disjoint sæt og et multisæt , og multisættet består af 2-elements undersæt af mængden. Notation: [67] , hvor ethvert element imultisættetog. $G=(V,E)$ $e\in E$ $e\in V\times V$ $V\cap E=\varnothing$

I en multigraf kan et par hjørner forbindes med mere end én kant. Flere kanter er kanter, der forbinder det samme par hjørner. Med andre ord er en multigraf en graf med flere kanter, og en graf er en multigraf uden flere kanter. En simpel eller almindelig graf er en graf uden flere kanter, hvis en multigraf kaldes en graf. En pseudograf er et endeligt disjoint sæt og et multisæt, og multisættet består af både 1-element og 2-element undersæt af sættet. Notation:, hvor er et multisætog.

G=(V,E)

E\subseteq V\cup (V\ gange V)

V\cap E=\varnothing

I en pseudograf kan en kant forbinde et toppunkt til sig selv. En løkke er en kant, hvis endespidser er de samme. Nogle gange kaldes en pseudograf en multigraf. En hypergraf er et endeligt disjoint sæt og et multisæt, og multisættet består af enhver delmængde af mængden. Notation:, hvor ethvert elementmultisættet hører til den boolske :, og.

G=(V,E)

e\in E

e\in P(V)

V\cap E=\varnothing

Med andre ord, i en hypergraf kan en kant forbinde ikke kun et eller to hjørner, men et vilkårligt antal hjørner. En rettet graf, eller digraph , er en pseudograf, hvis kanter er orienteret , det vil sige, at de har et indledende vertex og et endepunkt . Notation: [68] , hvor multisættetbestår af ordnede par og.

D=(V,E)

E

v,u\in V

V\cap E=\varnothing

En rettet kant, eller bue , er en kant af en digraf.

Eksempler på graftyper
Multigraf af Königsberg-broproblemet
pseudograf
hypergraf , $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}\},$ $\{v_{3},v_{5},v_{6}\},\{v_{4}\}\}$
digraf

Stier forbindelse rediger _

Egenskaben ved en graf, som betragtes som en af de enkleste og samtidig grundlæggende, er forbindelsesegenskaben. Her er den nærmeste kreds af begreber for denne forbindelsesegenskab [69] [70] [71] .

En sti, eller simpel sti, i en graf er en undergraf, som er en sekvens af distinkte knudepunkter, hvor hvert knudepunkt er forbundet til den næste kant. Stinotation ( engelsk sti ):, hvor $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}\))

alle er forskellige.

x_{i}

I teoretisk og praktisk arbejde kan stien kaldes forskelligt, for eksempel en simpel kæde . Endespidserne eller enderne af stien er knudepunkterne og . Hjørner og er forbundet med .

x_{0}

x_k

x_{0}

x_k

P

Stiens indre toppunkter er toppunkterne .

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

Længden af en sti er antallet af kanter i stien. Stilængdenotation :. _

k

P_{k}

En cyklus, eller simpel cyklus, i en graf er en undergraf, som er en lukket sekvens af forskellige hjørner, hvor hvert hjørne er forbundet med den næste kant. Cyklusbetegnelse ( engelsk cyklus ):, hvor

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}\}

alle er forskellige.

x_{i}

Cykluslængden er antallet af kanter i cyklussen. Betegnelse for cykluslængden : .

k

C_{k}

En cyklusakkord er en kant, der ikke hører til en cyklus og forbinder to af dens hjørner. Sætning. Enhver graf med en minimumsgrad af hjørner indeholder en cyklus med mindst længden .

G

\delta (G)\geqslant 2

\delta (G)+1

Eksempel på vej
To stier : gul og blå $P_{4}$
Rød cyklus . Stiplede kanter - cykelakkorder $C_{12}$

En forbundet graf er en graf, hvor to vilkårlige hjørner er forbundet med en sti.

En forbundet komponent eller komponent i en graf er den maksimale forbundne undergraf i en graf. En afbrudt graf består af mindst to forbundne komponenter. Når en komponent er tilsluttet, er den ikke tom; så den tomme graf har ingen komponenter.

Et eksempel på en tilsluttet og afbrudt graf
Forbundet graf på 5 hjørner
Afbrudt graf med 2 komponenter på 5 hjørner

Et adskillende toppunkt, eller artikulationspunkt for en graf, er et toppunkt på en graf, hvor antallet af forbundne komponenter i grafen stiger ved fjernelse. En bro af en graf er en kant af en graf, hvis fjernelse øger antallet af forbundne komponenter i grafen. Broens endespidser er de adskillende spidser. Det er klart, at broer i en graf er dem og kun de kanter, der ikke tilhører nogen cyklus. En uadskillelig graf er en ikke-tom forbundet graf uden adskillende hjørner.

Opdelte hjørner og eksempler på bro
e - bro. Toppunkt a og ender af broen er adskillende hjørner

En rute i en graf er en undergraf, som er en sekvens af hjørner, hvor hvert hjørne er forbundet med den næste kant. Rutebetegnelse: , hvor $(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}\))

En rute kan indeholde sammenfaldende kanter og toppunkter. Det er klart, at hvis alle hjørner i en sti er forskellige, så er dette en sti. Ruten er lukket hvis , ellers er ruten åben .

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

En Euler-cyklus, eller Euler-tur, af en graf er en lukket sti i en graf, der krydser alle grafens kanter nøjagtigt én gang. En Euler-graf er en graf, der har en Euler-cyklus. Det er tydeligt, at Euler-grafen hænger sammen. Sætning (Euler, 1736). En forbundet Euler-graf, hvis og kun hvis alle grafens toppunkter har lige grad. Følge. En forbundet graf med to hjørner af ulige grader har en åben bane, der krydser alle kanter nøjagtigt én gang. Desuden starter denne rute ved et af hjørnerne med en ulige grad og slutter ved et andet.

Euler-grafeksempler
Komplet graf , ingen kantgennemgang mulig én gang $K_{4}$
En ikke-Euler-graf, der har en åben sti, der passerer gennem alle kanter nøjagtigt én gang
Euler graf. Euler-cyklus - krydsende kanter i alfabetisk rækkefølge

Træer ( engelske træer )

Fire familier af grafer er blevet præsenteret ovenfor, disse er komplette, todelte, regulære og Euler-grafer. En anden familie af grafer inden for forskellige videnskabsområder kaldes den samme - træer. Træer finder anvendelse inden for forskellige vidensområder og har en særlig status i selve grafteorien på grund af den ekstreme enkelhed i deres struktur, og når man løser et grafproblem, kan det først studeres på træer [72] [73] [74] .

Skoven er en graf uden cyklusser.

Et træ er en sammenhængende skov. Træbetegnelse ( eng. træ ):.

T

Med andre ord er en skov en graf, hvis komponenter er træer. Et blad er et toppunkt på grad 1 i et træ. Ethvert ikke-trivielt træ har mindst to blade. Når et blad fjernes, forbliver træet igen. Sætning. For en graf er følgende udsagn ækvivalente: (i) grafen er et træ; (ii) hver to hjørner af grafen er forbundet med en unik sti; (iii) grafen er minimalt forbundet , dvs. grafen er forbundet og bliver afbrudt, når en kant fjernes; (iv) grafen er maksimal acyklisk , det vil sige, at grafen ikke har en cyklus, og en cyklus opstår, når to ikke-tilstødende hjørner er forbundet med en kant. Konsekvens 1. Enhver forbundet graf har et spændingstræ. Bevis. Det følger af ækvivalensen af betingelserne (i) og (iii) i sætningen, at enhver minimal spændende subgraf er et træ. Konsekvens 2. En forbundet -vertex- graf er et træ, hvis og kun hvis det har nøjagtig en kant.

n

n-1

Alle træer med 5 toppunkter

Roden af et træ er en fast top af træet. Rodnotation : . _ _ $r$

Et rodfæstet træ er et træ med en rod. Trærækkefølgen er en delrækkefølge på hjørnerne af et træ, bestemt af træet og dets rod: for alle to hjørner og træet , hvis stien med ender og hører til .

x

y

x \leqslant y

x

r

y

I trærækkefølge:

træets rod er det mindste element; $r$
ethvert blad af træet bortset fra roden er det største element;
enderne af enhver kant af et træ er sammenlignelige.

En kæde eller lineært ordnet sæt er et delvist ordnet sæt, hvor ethvert par af elementer er sammenlignelige. Sætning. De spidser af stien på træet med ender og danner en kæde, hvor er enhver fast toppunkt af træet bortset fra roden .

r

y

y

r

Eksempler på kæder på et rodfæstet træ
Træ med rod 3 og maksimale kæder 3-1-2, 3-7-6-5, 3-7-10

Et normalt spændingstræ i en graf er et rodfæstet spændingstræ i en graf, således at alle to tilstødende hjørner af grafen er sammenlignelige.

Et normalt spændingstræ kaldes også et dybde-først søgetræ efter den måde, de bruges i computersøgning. Sætning. Enhver forbundet graf har et normalt spændingstræ, og et hvilket som helst toppunkt på grafen kan være roden af træet. Illustrationen nedenfor viser to mulige spændingstræer for en komplet graf . Spændende træer er repræsenteret af fede kanter. Et venstrespændende træ er normalt, hvis dets rod er vertex A eller D; med rødder B eller C opnås normalitet ikke, da enderne af kanten, for eksempel AD, er uforlignelige. Et retspændende træ kan ikke være normalt for ethvert valg af dets rod; der vil altid være en kant med uforlignelige ender.

K_{4}

To spændende træer af en komplet graf med 4 vertex
Fed kanter er et normalt spændende træ med rod i A eller D
Fed kanter er et spændende træ, der ikke kan være normalt for ethvert valg af rod

Den aktuelle tilstand af grafteori

Den moderne tilstand af grafteori svarer til en standard lærebog, der kombinerer klassikere og aktiv matematik og dækker emnets hovedmateriale. Indholdsfortegnelsen for en sådan bog giver en kort idé om den nuværende tilstand af grafteori, som dette afsnit består af [75] .

Matching, covering and packing ( engelsk matching, covering and packing )

Hvordan finder man det maksimalt mulige antal uafhængige kanter i en graf? Kan alle hjørner af en graf opdeles i par? Svarene begynder med følgende begreber [76] [77] [78] .

Et matchende , eller et uafhængigt sæt kanter i en graf, er et sæt grafkanter, der ikke har fælles hjørner.

Matchninger på grafer (vist med rødt)
Matching af to kanter
Matching af tre kanter

En matchning dækker over et sæt toppunkter i en graf, hvis hver af toppunkterne i sættet er inkluderet i en eller anden kant af matchningen.

Dækning af grafens hjørner ved matchninger (vist med rødt)
Matching dækker 8 grafspidser ud af 9
Matching dækker alle 8 hjørner af grafen

Ægteskabsteorem ( Hall , 1935). En todelt graf indeholder en matchende, der dækker en af delene, hvis og kun hvis et hvilket som helst antal hjørner i denne del er forbundet med mindst lige så mange hjørner i den anden del.

En graf kan opdeles (eller en graf kan pakkes , eller en graf kan dækkes eller dekomponeres) i flere spændende træer eller spændende skove , der ikke har fælles kanter.

Træagtighed er det mindste antal skove, som grafen kan opdeles i. For eksempel har en graf 5 hjørner, så den maksimale størrelse af dens spændingstræ er 4. På den anden side har en graf 10 kanter, så der kræves minimum 3 træer for at dække dem. Derfor er opdelingen af grafen i 3 skove vist nedenfor minimal.

K_{5}

K_{5}

K_{5}

Minimumsspændende skov af en komplet graf med fem hjørner
Komplet graf $K_{5}$
1. Greve Spanning Skov $K_{5}$
2. Greve Spanning Skov $K_{5}$
3. spændingstræ i en graf $K_{5}$

Forbindelse _ _ _

Forbindelsen af en graf udforskes dybere ved at bruge begreberne -forbindelse, blokering og uafhængighed af stier [79] [78] . $k$

$k$ -forbundet graf (vertex - forbundet) $k$ er en forbundet graf, der:

har flere hjørner; $k$
forbliver forbundet efter at have fjernet mindre end nogen toppunkter. $k$

For eksempel er enhver ikke-tom graf 0-forbundet, og enhver forbundet graf med mere end et toppunkt er 1-forbundet. En dobbelt forbundet graf forbliver forbundet, når ethvert toppunkt fjernes. Forbindelse, eller vertex-forbindelse, af en graf

\kappa

er det største heltal , som grafen er forbundet med.

k

k

For eksempel, hvis og kun hvis grafen:

\kappa =0

eller uforbundet;
eller består af et toppunkt.

Forbindelsen af en forbundet graf med et artikulationspunkt er 1. Den komplette graf forbliver forbundet, når et hvilket som helst antal knudepunkter fjernes og har et knudepunkt, efter at et knudepunkt er fjernet , altså for alle .

K_n

n-1

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

n\geqslant 1

En kantforbundet graf

k

og kantforbindelse af en graf

\lambda

er defineret på samme måde . For eksempel, hvis og kun hvis grafen:

\lambda=0

eller uforbundet;
eller består af et toppunkt.

Kantforbindelsen af en forbundet graf med en bro er 1. Forbindelse, kantforbindelse og minimal grad af hjørner er relateret af følgende ulighed.

\lambda

\delta

Sætning (Whitney, 1932). For enhver graf med mere end ét toppunkt

G

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

Et eksempel på en graf med forbindelsesværdier, der ikke er ens med hinanden
Tæl med $\kappa =2,\lambda =3,\delta =4$

En grafblok er en maksimalt forbundet subgraf uden artikulationspunkter.

Blokken har ikke sine egne artikulationspunkter, men den kan godt have artikulationspunkter af den originale graf. En enkelt-blok graf kan simpelthen kaldes en blok . En undergraf er en blok, hvis og kun hvis den:

maksimal dobbeltforbundet subgraf;
bro med dens toppe;
isoleret top.

Forskellige blokke i grafen kan på grund af deres maksimalitet kun skære hinanden ved ét artikulationspunkt. Følgelig:

hver kant af grafen består af en enkelt blok;
selve grafen er en forening af blokke.

I denne forstand er blokke dobbeltforbundne analoger af tilsluttede komponenter. Kun tilsluttede komponenter krydser ikke hinanden, mens blokke kan krydse hinanden. Blokkene definerer sammen med de måder, de krydser hinanden på, grafens grove struktur - grafen over blokke og artikulationspunkter . Grafen over blokke og artikulationspunkter i grafen er en todelt graf med en række hjørner og , konstrueret som følger:

-en

B

toppunkter svarer til alle artikulationspunkter i den originale graf, toppunkter svarer til blokke; $-en$ $B$
En kant forbinder et toppunkt med et toppunkt , hvis artikulationspunktet tilhører en blok . $-en$ $B$ $-en$ $B$

Sætning. Blokgrafen for en forbundet graf er et træ.

Et eksempel på en graf og dens graf over blokke og artikulationspunkter
Kilde graf
Graf over blokke og artikulationspunkter i den originale graf

Flere stier er uafhængige eller usammenhængende , hvis ingen af dem indeholder en indre top af den anden.

Definitionen af -connectivity er relateret til fjernelse af toppunkter. Måske er den følgende definition mere illustrativ: en graf er -forbundet, når to af dens hjørner kan forbindes med uafhængige stier. Disse to definitioner er ækvivalente, de er dobbelte formuleringer af samme egenskab.

k

k

k

k

Den klassiske Menger- sætning er en af grundstenene i grafteorien. Sætning (Menger, 1927). For enhver delmængde af grafens hjørner og det mindste antal knudepunkter, der adskilles fra , er lig med det maksimale antal uafhængige stier fra til .

EN

B

EN

B

EN

B

Global version af Mengers sætning. (i) En graf er -forbundet, hvis og kun hvis der er uafhængige stier mellem to af dens hjørner.

k

k

(ii) En graf er kantforbundet, hvis og kun hvis der er kant-disjunkte baner mellem to af dens toppunkter.

k

k

Den følgende figur viser en graf, hvis to ikke-tilstødende hvide hjørner kan adskilles ved at fjerne mindst to spidser. Det følger af Mengers sætning, at det største antal uafhængige veje mellem disse hjørner er 2.

Graf for at illustrere Mengers sætning
Hvide hjørner er adskilt af mindst to spidser, og hvide spidser kan højst forbindes i to uafhængige baner.

Planar graphs ( engelske planar graphs )

Det er ønskeligt, at grafen tegnet på et ark papir opfattes så let som muligt. En måde at reducere kaoset på mange linjer på er at undgå at krydse dem. Er det muligt at tegne en graf på en sådan måde, at kanterne ikke skærer hinanden, det vil sige kun skærer hinanden ved fælles endespidser [80] [81] [82] ?

En plan graf er en graf tegnet på planet uden kantkrydsninger, dvs. kanter skærer kun hinanden ved fælles endespidser.

Forsiden af en plan graf er et af de åbne områder, der opstår, når grafen fjernes fra planet. Den ydre flade er den eneste ubegrænsede flade af grafen; resten af ansigterne kaldes indre . Sætning. En flad skov har kun ét ansigt - det ydre. Sætning ( Eulers formel , 1736). For enhver forbundet plan graf med spidser, kanter og flader er formlen sand

n

m

l

n-m+l=2

. Følge af Eulers formel. En plan graf med tre eller flere hjørner har højst kanter.

3n-6

Plangraf, Euler-formel og flader
Original plan graf: 4 spidser, 5 kanter og 3 flader, $4-5+3=2$
Tre sider af den originale graf: ydre (rød) og to indre

En plan graf er en graf, der kan tegnes på planet, som om den var plan.

For eksempel er en komplet graf med fire hjørner plan.

K_{4}

Planaritet af en komplet graf med fire spidser
Grafen er tegnet som ikke-plan $K_{4}$
Graf tegnet som flad $K_{4}$

De to legendariske grafer er ikke-plane:

komplet graf med fem hjørner ; $K_{5}$
komplet todelt graf . $K_{3},3$

Lad os bevise, at grafen er ikke-plan. Fra det modsatte. Lad os antage, at det er plant. Derefter har Eulers formel højst kanter. Men den har 10 kanter. Den resulterende modsigelse beviser, at grafen er ikke-plan.

K_{5}

K_{5}

K_{5}

3\cdot 5-6=9

K_{5}

K_{5}

Legendariske ikke-planære grafer
Komplet graf med fem hjørner $K_{5}$
Komplet todelt graf $K_{{3,3}}$

Sammentrækning af en kant af en graf er fjernelse af en kant fra grafen og sammensmeltning af endespidserne af denne kant til et toppunkt sammen med dens kanter.

Rib sammentrækning
Sammentrækning af en kant med endepunkter u og v

Pontryagin-Kuratovsky-sætningen (1927, 1930) eller Kuratovsky-sætningen (1930). En graf er plan, hvis og kun hvis hverken graf eller graf kan opnås fra den ved at slette kanter og hjørner med deres kanter og derefter trække kanterne sammen .

K_{5}

K_{{3,3}}

For eksempel fra en ikke-plan Petersen-graf kan man få på lignende måde:

en graf ved at trække de ydre små kanter sammen rettet mod midten af grafen: 0-5, 1-6, 2-7, 3-8, 4-9; $K_{5}$
graf som vist i følgende animation. $K_{{3,3}}$

Bevis for uplanaritet af Petersen-grafen
Indhentning af en graf fra en Petersen-graf $K_{{3,3}}$

Farvelægning ( engelsk farvelægning )

Hvor mange farver kan bruges til at farve lande på et kort, så tilstødende lande har forskellige farver? Hvor mange dage sidder et parlamentarisk udvalg, hvis hvert udvalg sidder en dag, og nogle medlemmer af parlamentet sidder i mere end et udvalg? Hvad er minimumslængden af en skoleskema, hvis det er kendt, hvor ofte hver lærer underviser i hver klasse [83] [84] ?

En farvning af en graf eller vertexfarvning af en graf er en farvning af en grafs hjørner, således at tilstødende spidser har en anden farve.

Eksempler på graffarvning
Komplet graffarvning $K_{4}$
Komplet graffarvning $K_{6}$
Grev Petersen Malebog

k -farvning af en graf, eller vertex k -farvning af en graf, eller k -farvning , er en vertexfarvning af en graf i k farver.

Forskellig k - farvning af en stjernegraf med 5 hjørner
Stjernegraf med 5 hjørner farvet i 2 farver
Stjernegraf med 5 hjørner farvet i 3 farver
Stjernegraf med 5 hjørner farvet i 4 farver

Det kromatiske tal for en graf, eller det kromatiske toppunkt for en graf, eller k - kromaticitet , er det minimum k , for hvilket grafen har en k -farve. Betegnelse:.

\chi

For eksempel er en graf 1-kromatisk, når den har mindst ét toppunkt og ingen kanter. Den komplette graf er n -kromatisk. En stjernegraf med 5 hjørner er 2-kromatisk. Og alle stjernegrafer er 2-kromatiske. Desuden er en graf todelt , hvis og kun hvis den er 2-kromatisk.

K_n

Sætning. For en graf med m kanter

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

. Bevis. Lad grafen være -farvet. Så for alle to farver er der mindst én kant med ender farvet i disse farver. Derfor er der mindst lige så mange kanter som , det vil sige . Ved at løse uligheden med hensyn til , får vi påstanden om sætningen.

\chi

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

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

\chi

Fire farver sætning. Enhver plan graf er 4-farverbar.

Måske er dette det eneste resultat af grafteori, der hævder at være berømt over hele verden. Det følger heraf, at hvert geografisk kort ikke kan farvelægges med mere end fire farver, således at nabolandene har forskellige farver. På nuværende tidspunkt er beviset for denne sætning af en kompliceret computerkarakter.

Farvelægning af et geografisk kort i 4 farver
Kort over emnerne i Den Russiske Føderation , farvet i fire farver

Det er meget lettere at bevise følgende svækkede påstand. Fem farvesætning. Enhver plan graf er 5-farverbar. Følgende påstand er også almindeligt kendt. Sætning (Gröch, 1959) . Enhver plan graf uden trekanter er 3-farvelig.

Farvelægning af en plan graf uden trekanter i 3 farver
3-farvning af bidiakis-terningen , et eksempel på en plan graf uden trekanter
3-farvning af en plan graf uden trekanter

En kantfarvning af en graf er en farvning af kanterne af en graf, således at tilstødende kanter har forskellige farver.

Eksempler på kantfarvning af grafer
Kantfarvning af en komplet graf $K_{4}$
Kantfarvning af en komplet graf $K_{8}$
Kantfarvning af Petersen-grafen

Kant k -farvning af en graf, eller kant k - farvebarhed , er en kantfarvning af en graf i k farver.

Forskellig kant k -farvning af en komplet graf med 4 hjørner
Den komplette graf er kantfarvet med 3 farver $K_{4}$
Den komplette graf er kantfarvet med 4 farver $K_{4}$
Den komplette graf er kantfarvet med 5 farver $K_{4}$

Det kromatiske indeks for en graf, eller det kromatiske kanttal for en graf, eller kanten k - kromaticitet , er den minimale k , for hvilken grafen har en kant k -farve. Betegnelse:.

\chi '

For det kromatiske tal for en graf er der kun bevist meget grove skøn, mens det for en grafs kromatiske indeks er lig med enten den maksimale grad af grafens hjørner eller .

\chi

\chi '

\Delta

\Delta +1

Det er klart, at for enhver graf .

\chi '\geqslant \Delta

Sætning ( König , 1916). For enhver todelt graf .

\chi '=\Delta

Sætning (Vizing, 1964) . For enhver graf.

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

Vizings sætning opdeler endelige grafer i to klasser: havende og havende .

\chi '=\Delta

\chi '=\Delta +1

Kantfarvning af grafer af forskellige klasser
Den komplette graf har $K_{4}$ $\chi '=\Delta =3$
Den komplette graf har $K_{3}$ $\chi '=\Delta +1=3$

Flows ( engelske flows )

En graf kan opfattes som et netværk, når kanterne bærer en vis strømning, såsom strømmen af vand eller elektricitet eller data og så videre. Hvordan modelleres sådan en situation matematisk [85] [86] ?

En partition af et sæt er et sæt af parvis adskilte delmængder, hvis forening giver hele sættet.

Eksempler på sæt partitioner
Opdeling af et sæt i 6 delmængder
Opdeling af et sæt i 7 delmængder

Et snit i en graf er et sæt af alle kanter af grafen, der skærer en partition af alle hjørnerne af grafen i to sæt - på siderne af partitionen , det vil sige, at endespidserne af hver kant af snittet er på forskellige sider af skillevæggen. Det er klart, at siderne af skillevæggen entydigt bestemmer snittet. En binding eller cocycle er et ikke-tomt snit i en graf, der er minimalt med hensyn til antallet af kanter , det vil sige, når et hvilket som helst antal kanter fjernes fra snittet, ophører snittet med at være ethvert snit. I det følgende eksempel er 5-kantsskæringen ikke et minimumssnit, fordi fjernelse af 3 kanter resulterer i minimumsskæringen vist til højre.

Eksempler på snit i en graf
5-kant skåret i 6-kant graf (ikke binding)
2-kant skåret i samme graf (binding)

Et flow på en graf er et sæt heltaltildelt hvert ordnet partilstødende noder (hjørnepunkter) i et netværk (graf), således at: $f(x,y)$ $(x, y)$

flow er antisymmetrisk ; $f(x,y)=-f(y,x)$
ved de knudepunkter, hvor flowet ikke kommer ind eller ud af netværket, er den første Kirchhoff-regel opfyldt , hvor summeringen udføres over alle, der støder op til . $x$ $\sum f(x,y)=0$ $y$ $x$

Kilden er den node, hvor flowet kommer ind i netværket. Betegnelse :.

s

En sink er en node, hvor en stream forlader netværket. Betegnelse :.

t

Et eksempel på et flow med kilde s og synk t på en graf
Flowgrafen har ikke (Kirchhoff-reglen er ikke opfyldt for hjørnerne u og v)
Flow på grafen

Flowteori:

simulerer reelle strømme;
interagerer med andre grene af grafteori (især med forbindelse og farvelægning).

En kant af en multigraf er ikke entydigt defineret af et par eller .

(x, y)

(y,x)

Den rettede kant af multigrafen er triplen , hvor er kanten af multigrafen, der starter ved toppunktet og slutter ved toppunktet .

(e,x,y)

e

x

y

Kanten c har to retninger og . Løkken har én retning .

e

x\ney

(e,x,y)

(e,y,x)

(e,x,x)

Cirkulationen på en graf er en funktionsådan, at:

f(e,x,y)

(F1) cirkulationen er antisymmetrisk for alle rettede kanter af grafen med ;

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

(e,x,y)

x\ney

(F2) ved alle noder er den første Kirchhoff-regel opfyldt , hvor summeringen udføres over alle ved siden af .

v

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

w

v

Sætning. I cirkulation er det samlede flow gennem enhver sektion nul:

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

, hvor summeringen går over alle kanter af et vilkårligt udsnit af grafen.

(e,v,w)

Et eksempel på cirkulation på en graf (ingen kilder eller dræn)
Cirkulationsgrafen har ikke (for knudepunkter s, t og v er Kirchhoff-reglen ikke opfyldt)
Cirkulation på en graf
I cirkulation er flowet gennem ethvert snit 0

Kapacitetsfunktionen på en graf, eller kapaciteten af kanterne på en graf, er et sæt naturlige tal (med nul), der er tildelt hver rettet kant af en multigraf.

Kapacitetsfunktionen på grafen defineres uafhængigt for begge retninger af kanten.

Eksempel på båndbredde på en graf
Graf med kilde s og synke t. Kapaciteten af rettede kanter er angivet

Netværket er en multigraf med to adskilte noder (vertices)ogen kapacitetsfunktionpå hver rettet kant.

s

t

c(e,x,y)

(e,x,y)

Et netværkssnit er et snit af en netværksmultigraf, således at de valgte noder ligger på forskellige sider af snittet.

s

t

Kapaciteten af et netværksudskæring er summen , hvor summeringen går over alle kanterne af netværksudskæringen.

\sum c(e,v,w)

(e,v,w)

Et flow i et netværk er en funktion med reel værdi i et netværk, således at:

f(e,x,y)

(F1) flowet er antisymmetrisk for alle rettede kanter af netværket (graf) med ;

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

(e,x,y)

x\ney

(F2') ved alle knudepunkter (hjørnepunkter) , bortset fra og , den første Kirchhoff-regel er opfyldt , hvor summeringen udføres over alle ved siden af ;

v

s

t

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

w

v

(F3) for alle rettede kanter af netværket .

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

(e,x,y)

Network cut flow værdien er summen , hvor summeringen går over alle kanterne af netværks cut.

\sum f(e,v,w)

(e,v,w)

Netværkets cut flow værdi er den samme for alle netværk cuts og kaldes netværks flow værdien . Sætning (Ford, Fulkerson, 1956) . I ethvert netværk er det maksimale flow lig med den minimale gennemstrømning af snittene.

Eksempel på maksimalt netværksflow
Netværk med kilde s og synke t. For hver rettet kant angives flow (1. tal) og gennemløb (2. tal). Strømningen gennem enhver sektion er maksimal og lig med 18 - sektionernes minimumsgennemstrømning

Ekstremal grafteori redigér _

Hvilken kanttæthed der er nødvendig for eksistensen af en given subgraf er et typisk ekstremt problem på grafer. Garanterer en tilstrækkelig høj gennemsnitlig grad af hjørner eller et stort kromatisk tal , at den ønskede understruktur helt sikkert vil forekomme i grafen? Hvad er det størst mulige antal kanter, som en -vertex-graf kan have uden at have en anden, mindre, graf som undergraf [87] [88] ? $n$

En ekstremalgraf — for et givet naturligt talog en graf erdette en-vertex-grafmed det maksimalt mulige antal kanter, der ikke indeholder en undergraf:. Dette maksimale antal kanter er angivet med. $n$ $H$ $n$ $G$ $H$ $G\nsupseteq H$ $\operatørnavn {ex} (n,H)$

Den maksimale graf — for et givet naturligt tal og en graf, er en -vertex-graf sådan, at , men med tilføjelse af enhver ny kant .

n

H

n

G

G\nsupseteq H

G\supseteq H

Det er tydeligt, at ekstremalgrafen er maksimal. Men ikke omvendt, som vist i figuren nedenfor.

Et eksempel på en ekstremal graf og en maksimal ikke-ekstrem
Komplet 3. ordens graf $K_{3}$
4. ordens ekstremalgraf for en komplet graf $K_{3}$
Maksimal, men ikke ekstremal orden 4 graf for $K_{3}$

$r$ En -partite graf, eller en multipartite graph , er en graf, hvis sæt af hjørner kan opdeles idelmængder - dele sådan, at: $r$

endespidserne af hver kant ligger i forskellige proportioner;
hjørnerne af den ene del er parvis ikke-tilstødende.

En komplet -partite graf

r

er en-partite graf, hvor hver to hjørner fra forskellige dele støder op til hinanden. Betegnelse:.

r

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

Et eksempel på todelte grafer
Ufuldstændig todelt graf
Komplet todelt graf $K_{{3,3}}$

Et eksempel på 3-delte grafer
Ufuldstændig 3-delt graf
Komplet 3-delt graf $K_{3,2,2}$

Turana-grafen er en-vertex-graf med følgende egenskaber: $n$

dette er en delvis graf med ; $r$ $r\leqslant n$
antallet af hjørner af aktierne afviger ikke fra hinanden med mere end 1.

Notation: Turana-grafen har kanter.

T_{r}(n)

t_{r}(n)

Turan-grafen er tæt (det vil sige tæt på en komplet graf), da den har nære kanter, mere præcist,

T_{r}(n)

n^{2}

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

, og lighed opnås ved opdeling .

r

n

Sætning (Turan, 1941) . Turan-grafener den eneste ekstremalgraf forog, og.

T_{r-1}(n)

n

{\displaystyle K_{r))

\operatørnavn {ex} (n,K_{r})=t_{r-1}(n)

Et eksempel på grafer, der ikke er Turan-grafer
Ufuldstændig todelt graf
En komplet todelt graf , men størrelsen på delene afviger med 2 $K_{5,3}$

Turan graf eksempel
Komplet todelt graf : Turana-graf $K_{{3,3}}$ $T_{2}(6)$
Komplet 4-delt optælling : Turana-antal $K_{4,3,3,3}$ $T_{4}(13)$

Uendelige grafer _ _

Studiet af uendelige grafer er attraktivt, men denne del af grafteorien bliver ofte forsømt. Terminologien falder sammen med terminologien for endelige grafer, bortset fra fundamentalt nye begreber for uendelige grafer. De mest typiske sådanne begreber optræder allerede ved "uendelighedens minimum", når grafen kun har et tælleligt antal hjørner og kun et endeligt antal kanter ved hjørnerne [89] .

En lokalt finit graf er en graf, hvor et begrænset antal kanter konvergerer ved hvert toppunkt.

En stråle er en graf med uendelige sæt af hjørner og kanter, henholdsvis nummereret som følger:

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

En dobbeltstråle er en graf med uendelige sæt af hjørner og kanter, henholdsvis nummereret som følger:

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

Eksempel på dobbeltstråle
En uendelig graf med et tælleligt antal hjørner, 2 kanter konvergerer ved hvert hjørne

Det er klart, at der op til isomorfi kun er én stråle og én dobbeltstråle. En dobbeltstråle med præcis to kanter, der mødes ved alle toppunkter, er en uendelig 2-regulær forbundet graf. En vej er enten en endelig vej, eller en stråle eller en dobbeltstråle. Halen er en understråle af en stråle eller en dobbeltstråle. En stråle har uendeligt mange haler, der kun adskiller sig i det indledende endesegment. En højderyg er foreningen af en stråle med et uendeligt antal ikke-skærende endelige baner, der har det første toppunkt på strålen. Kammens tænder er de sidste hjørner af kammens sidste baner.

kam eksempel
Kam med hvide tænder og bjælke $R$

Königs Lemma på den uendelige vej . Lade:

graf - foreningen af et uendeligt antal ikke-skærende ikke-tomme endelige mængder ; $V_{0},V_{1},V_{2},\dots$
hvert toppunkt fra kl har en nabo fra . $v$ $V_{n}$ $n\geqslant 1$ $f(v)$ $V_{n-1}$

Så indeholder grafen en stråle c for alle .

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

v_{n}\in V_{n}

n

Königs Lemma på den uendelige vej
Illustration til Königs uendelige vejlemma

Bevis. 1. Der er et uendeligt sæt af endelige stier af formen, der ender på . Da det er endeligt, så er der sådan et toppunkt , hvor uendeligt mange sådanne stier ender.

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

V_{0}

V_{0}

v_{0}

V_{0}

2. Uendeligt mange stier, der ender på, har næstsidste toppunkt på . Der er uendeligt mange stier , og selvfølgelig er der et sådant toppunkt i , som hører til et uendeligt sæt af sådanne stier.

v_{0}

V_{1}

V_{1}

v_{1}

V_{1}

3. Uendeligt mange stier, der går igennem , har et toppunkt ved , så der er et toppunkt ved , der hører til et uendeligt sæt af disse stier.

v_{1}

V_{2}

v_{2}

V_{2}

4. Og så videre i det uendelige. Uendelig stråle bygget.

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

Anvendelser af dette uendelige vejlemma er baseret på det faktum, at en tællig graf kan ses som en uendelig sekvens af endelige undergrafer.

Enden af grafen erækvivalensklassenfor grafens stråler. To stråler af en graf er ækvivalente, hvis begge stråler, efter at have fjernet et endeligt sæt hjørner fra grafen, har en hale i den sammetilsluttede komponent.

Lad os definere enderne af stigen , som er uendelig i to retninger. Hver stråle i denne graf indeholder hjørner vilkårligt langt enten til venstre eller højre, men ikke både til venstre og højre. Disse to typer af stråler danner to ækvivalensklasser, så stigen har to ender. I nedenstående figur er disse ender af grafen markeret med prikker.

2-sidet endeløs trappe
2-sidet endeløs trappe, ender markeret med prikker

Enderne af træet er særligt enkle :

to træstråler er ækvivalente, hvis og kun hvis de har en fælles hale;
for hvert fast toppunkt på træet indeholder hver ende præcis én stråle, der starter fra det toppunkt.

Selv et lokalt begrænset træ kan have et kontinuum af ender. For eksempel et binært træ , hvor hjørnerne er angivet med endelige 0-1 sekvenser, med det tomme sæt som roden . Så svarer enderne af et sådant træ til dets stråler, der starter fra roden og følgelig til kontinuummet af uendelige sekvenser 0-1.

\tomt sæt

\tomt sæt

Eksempel på binært træ
Binært træ med et kontinuum af ender, en for hver uendelig sekvens 0-1

Ramsey grafer [ rediger

Indeholder hver tilstrækkelig stor graf enten en komplet graf eller et induceret komplement ? På trods af ligheden med ekstreme problemer med deres søgen efter lokale konsekvenser af globale antagelser, fører det sidste spørgsmål til matematik af en lidt anden art. Faktisk har sætningerne og beviserne for Ramseys teori mere til fælles med lignende resultater fra algebra eller geometri . Sproget i grafer er naturligt i Ramsey-problemer, og materialet viser en række ideer og metoder, der er tilstrækkelige til at formidle charmen ved denne teori som helhed [90] [91] [92] ? ${\displaystyle K_{r))$ ${\displaystyle {\overline {K_{r))))$

Komplementet af en graf er en graf, der har:

sættet af toppunkter falder sammen med sættet af toppunkter i den originale graf;
hjørner er forbundet med en kant, hvis og kun hvis de ikke er forbundet med en kant i den originale graf. Betegnelse for grafen : . $G$ $\overline{G}$

Komplementet af en komplet graf er en fuldstændig afbrudt graf, der kun indeholder toppunkter.

{\displaystyle K_{r))

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

Grafer og deres komplementer
Firkant (venstre) og dens komplement (højre)
Komplet graf $K_{6}$
Tilføjelse ${\displaystyle {\overline {K_{6))))$

En selvkomplementær graf er en graf, der er isomorf i forhold til dens komplement. De mindste ikke-trivielle selvkomplementære grafer indeholder 4 og 5 hjørner.

De mindste ikke-trivielle selvkomplementære grafer
Selvkomplementær graf med 4 hjørner
Selvkomplementær graf med 5 hjørner
Selvkomplementær graf med 5 hjørner

Ramsey-problemet er et velkendt puslespil:

bevise, at der blandt seks personer altid er enten tre parvise bekendte eller tre parvise fremmede.

Formulering af Ramsey-problemet i grafteori:

de seks hjørner af grafen er mennesker, kanterne er bekendte. Bevis, at der enten er tre hjørner, der er parvis forbundet med kanter, eller tre hjørner, der ikke er parvis forbundet.

Præcis formulering ved hjælp af grafens komplement. Sætning. Enhver graf med seks hjørner indeholder enten en trekant, eller dens komplement indeholder en trekant. Bevis. 1. Lad en graf med seks toppunkter være givet. Tag nogen af dens hjørner . Et toppunkt er forbundet med en kant til en af de andre fem toppunkter enten i eller i . Derfor, uden tab af generalitet, antag, at det er forbundet med toppunkter i .

G

v

v

G

\overline{G}

v

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

G

2. Hvis to af hjørnerne er forbundet med en kant, så er c en trekant i . Hvis ikke to af hjørnerne er forbundet med en kant, så danner de en trekant i .

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

v

G

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

\overline{G}

Generalisering af teoremet. Sætning (Ramsey, 1930) . For ethvert naturligt tal eksisterer der et naturligt tal, således at enhver graf med mindstknudepunkter eller dens komplement indeholder.

r

n

n

{\displaystyle K_{r))

Det er praktisk at bruge farve i formuleringen af Ramsey-sætningen:

for enhver komplet graf eksisterer der en komplet graf, således at enhver af dens tofarvede kantfarver indeholder en enfarvet . ${\displaystyle K_{r))$ $K_n$ ${\displaystyle K_{r))$

Ramsey-tallet er det mindstegiveti Ramsey-sætningen. Betegnelse:.

n

r

R(r)

Standardbeviset for Ramsey-sætningen indebærer en øvre grænse for Ramsey-tallet: . Ved hjælp af den probabilistiske metode kan du finde det lavere estimat :.

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

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

For eksempel :

R(3)=6

af løsningen af Ramsey-problemet følger det, at ; $R(3)\leqslant 6$
lad os bevise det . Det er tilstrækkeligt at give et eksempel på en graf med 5 hjørner, der ikke opfylder Ramsey-sætningen for . Denne selvkomplementære femkant vist ovenfor har 5 hjørner og ingen trekanter, og heller ingen trekanter i dens komplement, der matcher den; $R(3)>5$ $K_{3}$
$R(3)\leqslant 6$ og altså . $R(3)>5$ $R(3)=6$

Illustration af formlen R(3) = 6. De røde kanter er grafen, de blå er dens komplement
Graf med 6 hjørner, der er kun røde trekanter
Graf med 6 hjørner, der er kun blå trekanter
Graf med 5 hjørner, ingen røde eller blå trekanter

Ramseys sætning gælder ikke kun for den komplette graf , men også for enhver graf , simpelthen fordi er en undergraf af den komplette graf , hvor er antallet af hjørner . ${\displaystyle K_{r))$ $H$ $H$ $K_{h}$ $h$ $H$

Ramsey-tallet for enhver graf er det mindste naturlige tal , som enhver -vertex-graf eller dens komplement indeholder . Betegnelse :.

H

n

n

H

R(H)

Hvis der er få kanter i en graf, så er det lettere at inkludere i en anden graf, og vi kan forvente , hvor er antallet af hjørner .

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

h

H

Lad os generalisere lidt mere. Ramsey-tallet for et par grafer og er det mindste naturlige tal , således at for enhver toppunktsgraf enten selve grafen eller dens komplement indeholder . Notation: , for komplette grafer .

H_1

H_2

n

n

H_1

H_2

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

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

Det er klart , at .

R(H,H)=R(H)

R(r,r)=R(r)

For de fleste grafer kendes kun meget grove estimater for Ramsey-tal; nøjagtige ikke-trivielle Ramsey-tal kendes kun for meget få grafer. For eksempel , , , .

R(3)=6

R(4)=18

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

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

Illustration af formlen R(3, 4) = 9. De røde kanter er grafen, de blå er dens komplement
Graf med 9 hjørner, nogle røde , ingen blå $K_{3}$ $K_{4}$
Graf med 9 hjørner, ingen røde , kun blå $K_{3}$ $K_{4}$
Graf med 8 hjørner, ingen rød eller blå $K_{3}$ $K_{4}$

Hamilton cykler _ _

Problemet med, om en graf indeholder en lukket bane, der går gennem hver kant nøjagtigt én gang, løses let ved hjælp af Eulers simple sætning (1736). Meget vanskeligere er det samme spørgsmål om toppunkter : hvornår indeholder grafen en lukket bane, der passerer gennem hvert toppunkt nøjagtigt én gang [93] [94] [95] ?

En Hamilton-cyklus er en lukket sti, der passerer gennem hvert hjørne af grafen nøjagtig én gang.

En Hamiltonsk graf er en graf, der har en Hamiltonsk cyklus. Det er klart, at hvert hjørne af en Hamilton-graf indeholder mindst to kanter.

Eksempler på Hamiltonske cyklusser
Hamiltonsk cyklus på et plant dodekaeder
Hamiltonsk cyklus på et volumendodekaeder

Sætning. Enhver Hamiltonsk graf er dobbelt forbundet. Det vil sige, at være to-forbundet er en nødvendig betingelse for at være Hamiltonian. Ikke alle dobbeltforbundne grafer er Hamiltonske.

Eksempler på enkeltforbundne grafer
Tæl "Dart" ikke-hamiltonianere
Tæl "fisk" ikke-hamiltonianere

En theta-graf er en graf, der kun indeholder følgende hjørner:

to hjørner, som omfatter tre kanter;
hjørner, der har to kanter.

Det vil sige, at theta-grafen har to spidser af grad 3 og tre ikke-skærende simple stier, der forbinder disse to spidser, hver med en længde på mindst 2.

Eksempler på tetagraf
Den enkleste tetagraf er en komplet todelt graf $K_{2,3}$
Theta graf med 7 hjørner
Theta graf med 9 hjørner

Thetagraf over ikke-Hamiltonianere. Den enkleste ikke-Hamiltonske dobbeltforbundne graf er en komplet todelt graf .

K_{2,3}

Sætning. Hver ikke-Hamiltonsk dobbeltforbundet graf har en theta-undergraf. Det vil sige, at tilstedeværelsen af en theta-undergraf er en nødvendig betingelse for at være ikke-hamiltonsk. Ikke enhver graf med en theta-undergraf er ikke-hamiltonsk. Den enkleste Hamilton-graf med en theta-undergraf er en komplet todelt graf med en tilføjet kant.

K_{2,3}

De enkleste Hamilton-grafer
Den enkleste Hamilton-graf
Den enkleste Hamilton-graf med en theta-undergraf

Nogle nødvendige betingelser for at være Hamiltonian og ikke-Hamiltonian er blevet givet ovenfor . Hvilke forhold kan være tilstrækkelige for Hamiltonianitet? Kun få forhold på én gang.

Sætning ( Dirac , 1952). En graf med Hamiltonske toppunkter, hvis:

n\geqslant 3

1) minimumsgraden af dens hjørner afhænger af n;

\delta

2) .

\delta \geqslant n/2

Det vil sige en tilstrækkelig betingelse for Hamiltonianitet. Denne betingelse er ikke opfyldt for hver Hamilton-graf. For eksempel, for den enkleste Hamilton-graf med en theta-undergraf, er betingelsen ikke opfyldt.

\delta \geqslant n/2

En kubisk graf er en 3-regulær graf, det vil sige en graf, hvor nøjagtigt 3 kanter konvergerer ved hvert toppunkt. For plane grafer er Hamiltonian relateret til firefarveproblemet . For at bevise firefarvesætningen er det tilstrækkeligt at bevise Tate-formodningen : enhver 3-forbundet plan kubisk graf har en Hamiltonsk cyklus. Hypotesen blev ikke bekræftet. Det første modeksempel blev fundet af Tutt i 1946.

Modeksempel til Tites formodning: Tattas graf
3-forbundet plan kubisk graf uden Hamiltonsk cyklus

Sætning (Tutt, 1956). Enhver 4-forbundet plan Hamilton-graf.

Eksempler på 4-forbundne plane grafer
4-forbundet plan graf: oktaeder
5-forbundet plan graf: icosahedron

Random graphs ( engelske random graphs )

Den probabilistiske metode gør det muligt at bevise eksistensen af et objekt med en given egenskab på følgende måde: 1) et sandsynlighedsrum er defineret på en større klasse af objekter, som er kendt for at være ikke-tom; 2) det vises, at den ønskede egenskab er opfyldt for et tilfældigt udvalgt rumelement med positiv sandsynlighed. Essensen af den probabilistiske metode er ikke-konstruktivt at vise, at en given farve eksisterer eller ej [96] [97] [98] .

Den probabilistiske metode er godt illustreret af følgende eksempel: vi opnår et lavere estimat for Ramsey-tallet . $R(k)$

1. Lad os konstruere et sandsynlighedsrum. Farv tilfældigt hele grafen , det vil sige farve hver kant uafhængigt rød eller blå med lige stor sandsynlighed. Således er sandsynligheden for, at kanten bliver rød , , og blå er også .

K_n

K_n

K_n

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

2^{-1}

2. Vi definerer følgende hændelse på en tilfældigt farvet: en tilfældigt udvalgt komplet undergraf er monokrom, det vil sige enten rød eller blå. Undergrafen har kanter, så sandsynligheden for, at en allerede valgt undergraf er rød er , blå er også , og monokrom er .

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}}

Sandsynligheden for, at en allerede valgt undergraf er monokromatisk, afhænger ikke af . For eksempel er sandsynligheden for at være én farve altid lig med

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}}

, sandsynligheden for at have samme farve er altid

K_{4}

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

. 3. Lad os nu beregne sandsynligheden for, at en tilfældigt valgt undergraf er monokrom. Der er flere måder at vælge en undergraf på i en komplet graf . Da begivenheder viser sig at være monokrom for disse undergrafer kan vise sig at være afhængige af hinanden, så er sandsynligheden for, at en tilfældigt udvalgt undergraf viser sig at være monokrom kun ikke mere end summen af deres sandsynligheder .

K_k

K_k

K_n

{n \vælg k}

K_n

K_k

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

For eksempel sandsynligheden for at være monokrom i højst

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}}

, sandsynligheden for at være monokrom er højst

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

Lad os anslå Ramsey-tallet nedefra. Hvis lille nok til givet , så Ramsey-tallet . $n$ $k$ $R(k)>n$

Lemma. Hvis , så .

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

R(k)>n

Bevis. 1. Lad , det vil sige, at sandsynligheden for, at en tilfældigt udvalgt undergraf er monokrom, er mindre end 1.

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

K_n

K_k

2. Så er sandsynligheden for, at alle undergrafer ikke er monokrome større end nul: .

K_k

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

3. Med andre ord eksisterer der en 2-farvning uden monokromatisk , dvs.

K_n

K_k

R(k)>n

Sætning ( Erdős , 1947). For ethvert naturligt Ramsey-nummer .

k \geqslant 3

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

Denne nedre og øvre grænse er meget tæt.

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

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

Bevis. 1. Når vi har:

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))))

. For alt hvad vi har:

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

. Nu, ved lemmaet , for alle , det vil sige .

R(3)>n

n\leqslant 2^{3/2}

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

2. Lad nu . Vi har:

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}

. For alle beregninger som for :

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

. Nu, ved lemmaet , for alle , det vil sige .

R(k)>n

n\leqslant 2^{k/2}

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

En tilfældig graf er en undergraf af en komplet grafopnået tilfældigt. For eksempel, hvis alle kanterer tilfældigt farvet røde eller blå, så er den tilfældige graf den undergraf, der dannes af alle røde kanter. Det er klart, at tilfældige grafer er uafhængige hændelser. Notation: sandsynligheden for en tilfældig grafer angivet med. $K_n$ $K_n$ $G$ $P(G)$

En tilfældig variabel er et ikke-negativt reelt tal givet på hver tilfældig graf. Det kan for eksempel være antallet af hjørner af en tilfældig graf, forbindelse, kromatisk tal og så videre. Betegnelse:.

G

X(G)

Den matematiske forventning eller middelværdi af en tilfældig variabel er den vægtede sum af sandsynligheden for alle tilfældige grafer:

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

. Den matematiske forventning er lineær , dvs. ligheder

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

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

udføres for to tilfældige variable og ethvert reelt tal .

x

Y

\lambda

Hvis den matematiske forventning, det vil sige middelværdien af den stokastiske variabel, er lille, så skal den stokastiske variabel være lille for mange tilfældige grafer. Så er det naturligt at antage, at der blandt sidstnævnte findes en graf med den nødvendige egenskab. Denne idé ligger til grund for ikke-konstruktive eksistensbeviser. Det kvantitative udtryk for denne idé er som følger. Markovs ulighed . For enhver tilfældig variabelog ethvert reelt tal, uligheden

X\geqslant 0

a>0

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

. Bevis. Det er indlysende, at (summen udføres over alle tilfældige grafer )

G

E(X)=\sum \limits _{G}P(G)X(G)\geqslant \sum \limits _{G \top 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)

Mindreårige, træer og brønd- -orden rediger

En af de mest dybtgående matematiske sætninger, der overskygger enhver anden sætning i grafteorien, er graph minor- sætningen : ethvert uendeligt sæt af grafer indeholder to grafer, således at den ene er en mindre af den anden. Nogle grundlæggende begreber forklares nedenfor om tilgangene til denne sætning, hvis bevis tager 500 sider [99] [100] .

En forudbestilling , eller en kvasiorden , er en refleksiv og transitiv relation på et sæt. Betegnelse:. $\leqslant$

En komplet forudbestilling , eller en egentlig kvasi, er en forudbestilling, hvor enhveruendeligrække af sætelementer indeholder to forudbestilte elementer, hvor det større element følger efter det mindste i sekvensen. Med andre ord indeholder enhver sekvensisættet,.

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

x

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

i<j

Velforudbestilte elementer er elementer i et velforudbestilt sæt. Sætning. En forudbestilling på et sæt er fuldført, hvis og kun hvis sættet ikke indeholder følgende uendelige sekvenser af elementer:

med parvis uforlignelige elementer;
strengt faldende, det vil sige rækkefølgen , hvor betyder og . $x_{0}>x_{1}>x_{2}>\dots$ ${\displaystyle x_{i}>x_{j))$ ${\displaystyle x_{i}\geqslant x_{j))$ ${\displaystyle x_{i}\neq x_{j))$

Eksempler. 1. Delbarhedsrelationen på mængden af naturlige tal er forudbestilt og endda delvist ordnet , men ikke fuldstændig forudbestilt, da en uendelig række af primtal ikke indeholder et forudbestilt par.

\,\vdots\,

2. Delbarhedsrelationen på mængden af heltal er forudbestilt og ikke delvist ordnet (fordi f.eks. og , men ) og heller ikke fuldstændig forudbestilt.

2\,\vdots-2

-2\,\vdots \,2

2\neq -2

Delelighedsforhold
Hasse diagram over forholdet mellem delelighed af naturlige tal

En underinddeling eller forlængelse af en graf, eller en underinddelingsgraf , er en graf, der er opnået fra originalen ved at dividere kanter med hjørner.

En topologisk minor af en graf er en graf, hvis underinddeling er en undergraf af den originale graf. Den topologiske mol bevarer den topologiske form af en undergraf af den originale graf.

Topologisk mindre eksempel
Kilde graf $G$
Underinddeling - underafsnit $H$ $G$
Topologisk graf minor $H$ $G$

En mindre graf er en graf, der er opnået fra den originale graf ved at fjerne hjørner og fjerne og trække kanter sammen. Relationsbetegnelse- mindre:

x

Y

X\preccurlyeq Y

Enhver undergraf i en graf er dens underordnede. Hver graf er sin egen minor.

Mindre eksempel
Bilaget opnås ved at fjerne ef og kontrahere bc

Sætning. (i) Enhver topologisk mol af en graf er også dens (almindelige) mol. Det modsatte er ikke sandt generelt. (ii) For en graf med højst 3 kanter ved hvert toppunkt er enhver mol en topologisk mol. Sætning. På sættet af alle endelige grafer er relationerne, der er en mindre og en topologisk mindre, partielle ordrer .

\precurlyeq

Hasse-diagram over forholdet er en (topologisk) minor
Relationen til at være den (topologiske) mol af en firkant. Alle mindreårige er subgrafer, undtagen trekanten. En trekant fås fra en firkant ved at trække toppunktet sammen

En forbudt eller udelukket minor for en given egenskab af grafer er en graf, hvis tilstedeværelse som en minor i en graf indikerer fraværet af denne egenskab i sidstnævnte.

Ifølge den forrige sætning er sættet af forbudte mindreårige lukket for at tage mindreårige: hvis en graf er en forbudt mindreårig og , så er grafen også en forbudt mindre.

G

H\preccurlyeq G

H

Sætning. En egenskab ved grafer kan defineres af forbudte mindreårige, hvis og kun hvis den er lukket for at tage mindreårige. Grafegenskaber, der er lukket for mindreårige, forekommer ofte i grafteori. Det mest berømte eksempel er givet af Pontryagin-Kuratovsky-sætningen : planhed er givet ved forbud mod mindreårige og .

K_{5}

K_{{3,3}}

Karakterisering ved forbudte grafer er en god karakterisering . En god karakterisering er en karakterisering af en egenskab ved grafer, der gør det lettere at bevise, at egenskaben ikke eksisterer. Bare for at sikre, at grafen har en eller anden egenskab, er det nok at afbilde grafen på en bestemt måde. Der opstår vanskeligheder ved at bevise fraværet af en ejendom. Men for eksempel i nærværelse af forbudte mindreårige for en ejendom, kan dens fravær let bevises ved at præsentere en forbudt mindreårig. Sætning. I nærværelse af forbudte mindreårige eksisterer der altid et unikt mindste sæt af dem, hvis elementer er de mindreårige af alle forbudte mindreårige. Det er klart, at de forbudte mindreårige fra det mindste sæt er uforlignelige med hensyn til at være mindreårige. Følgende teorem siger, at ethvert sæt af uforlignelige grafer er endeligt.

\precurlyeq

\precurlyeq

Robertson-Seymour-sætningen (1986-2004). Finite grafer er godt forudbestilt med hensyn til atvære mindre.

\precurlyeq

Følge. Enhver egenskab ved grafer, der er lukket i at tage mindreårige, kan defineres af et begrænset sæt af forbudte mindreårige. En stærk version af dette teorem for træer er som følger. Sætning (Kruskal, 1960) . Finite træer er godt forudbestilt med hensyn til at være en topologisk minor.

Et eksempel på sættet af forbudte mindreårige
Petersen-familien , forbudte mindreårige for en ulinket grafindlejring

Noget algebra redigér _

Simple cyklusser og kantklip af grafer er baseret på en algebraisk struktur, hvis opnåelse af forståelse gør det muligt at anvende kraftfulde og smukke metoder til lineær algebra, som igen fører til en dybere forståelse af grafteori og tilsvarende algoritmer på grafer [101] [102] [ 103] [104] .

En grafs toppunktsrum er mængden af alle delmængder af sættet af alle grafens toppunkter, transformeret til et vektorrum over et 2-elementfelt Notation af en grafs toppunktsrum $\{0,1\}.$ $G:{\mathcal {V}}(G).$

Vektoren af dette rum er en delmængde af grafens hjørner:

summen af to vektorer er defineret som summen af modulo 2 eller den symmetriske forskel eller ringsum af delmængderne;
vektoren er modsat sig selv;
null vektor er et tomt sæt af hjørner;
grundlaget for vektorrummet er opbygget af alle et-elements delmængder - grafens hjørner. Derfor er dimensionen af et vektorrum lig med antallet af grafens toppunkter.

Additionstabel modulo 2 vektorer af rum 4 hjørner

$\plus$

Grafkantrummet er sættet af alle undersæt af grafkantsættet konverteret til et vektorrum over et felt med 2 elementer . Notation af grafkantmellemrum

\{0,1\}.

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

Fuldstændig analog med hjørnernes rum. Strukturen af en graf er bestemt af dens kanter, så vi beskæftiger os normalt med kanternes rum. Nedenfor er en tabel med modulo 2-addition af kantrumsvektorerne i en cyklisk graf . Elementerne i det udskårne underrum er inde i de blå rammer, tre elementer i en af baserne i dette underrum er fremhævet med blåt. Underrummet af cyklusser i dette tilfælde er et underrum af underrummet af snit og består af to elementer: det tomme sæt og grafen ; dens elementer er fremhævet med blåt.

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

C_{4}

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

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

C_{4}

Spændende træ, seks bindinger og grafcyklus

C_{4}


blåt spændingstræ _	Seks bindinger (minimumssnit). Tre elementer i en af baserne er fremhævet med blåt						Cyklus

Additionstabel modulo 2 vektorer af rum 4 grafkanter

C_{4}

$\plus$

Rummet af cyklusser af en graf er et underrum af rummet af kanter af en graf, som genereres af alle simple cyklusser af grafen. Cycle space notation af en graf $G:{\mathcal {C}}(G).$

Med andre ord er rummet af cyklusser spændt over af simple cyklusser, det vil sige, det består af:

tomt sæt;
alle simple cyklusser af grafen;
af alle summer modulo 2 af grafens simple cyklusser.

Sætning. Cyklusrummet genereres også af cyklusser uden akkorder. Det cyklomatiske tal, eller cykliske rangorden, af en graf er dimensionen af grafens cyklusrum. Sætning. Det cyklomatiske tal for en forbundet graf er lig med antallet af akkorder i et spændingstræ i grafen, det vil sige, det er lig med , hvor er antallet af grafkanter og er antallet af hjørner.

m-n+1

m

n

Nedenfor er en tabel over modulo 2-addition af cyklusrumsvektorerne i den givne graf , vist nedenfor sammen med spændingstræet. Tre elementer i en af baserne i dette rum er fremhævet med blåt.

{\mathcal {C}}(G)

G

Omspændende træ og seks simple cyklusser af en given graf


Strækkende træ af en graf $G$	Seks simple cyklusser af den givne graf. Tre elementer i en af baserne er fremhævet med blåt

Modulo 2 additionstabel over cyklusrumsvektorer

$\plus$

Rummet af snit, eller bindinger, af en graf er et underrum af rummet af kanter af en graf, som genereres af det tomme sæt og alle minimale snit i grafen. Grafbinding mellemrumsnotation $G:{\mathcal {B}}(G).$

Med andre ord er rummet af snit spændt over af minimale snit, det vil sige, det består af:

tomt sæt;
alle minimale udskæringer af grafen;
af alle summer modulo 2 af grafens minimumssnit.

Sætning. Skæringsrummet genereres også af snit, hvoraf det ene af de to sæt skillevægge er et isoleret toppunkt. En grafs skæringsrang er dimensionen af grafens skæreplads. Sætning. Skæringsrækken for en forbundet graf er lig med antallet af kanter af ethvert spændingstræ i grafen, dvs. hvor er antallet af grafens toppunkter.

n-1

n

Nedenfor er en tabel over modulo 2-addition af de afskårne rumvektorer i den givne graf , vist nedenfor sammen med spændingstræet. Fire elementer i en af baserne i dette rum er fremhævet med blåt.

{\mathcal {B}}(G)

G

Omspændende træ og ti bindinger af en given graf

G


Strækkende træ af en graf $G$	Ti bindinger (minimumssnit) af den givne graf. Fire elementer i en af baserne er fremhævet med blåt

Tilføjelsestabel modulo 2 af cut space vektorer

$\plus$

Anvendelser af grafteori

Allerede i 1800-tallet brugte man grafer i design af elektriske kredsløb og molekylære kredsløb; matematik sjov og puslespil er også en del af grafteorien [105] .

Nogle problemer i grafteori

Problemet med Königsberg-broer . Kør gennem alle broerne i centrum af det gamle Königsberg én gang. Løst af Leonhard Euler i en publikation dateret 1736 , dette er det første resultat af grafteori (den første sætning i samme publikation er, at summen af graderne af hjørnerne af en graf er lig med det dobbelte af antallet af dens kanter) [ 16] [106] [12] [107] [21] [108] [109] [13] [110] .

Nogle gange overføres denne opgave til brosystemet i andre byer. For eksempel blev der offentliggjort et problem om 17 broer ved mundingen af Neva i byen Leningrad i 1940 [110] .

Firefarveproblemet - er det muligt at farvelægge ethvert kort med fire farver, så tilstødende lande har forskellige farver? Formuleret i 1852, i 1977 udgivet (annonceret i 1976) det første generelt accepterede positive bevis ved hjælp af en computer [111] [112] [113] [114] [115] [116] [117] [118] .
Domino problem. Alle 28 dominobrikker skal forbindes i en sammenhængende (simpel) kæde, så de tilstødende halvdele af to sten har samme nummer. Da tilstedeværelsen af doubler ikke komplicerer problemet, er dominoproblemet også stillet for 21 terninger (uden doubler) uden tab af generalitet [21] [22] [119] .
Labyrintens opgave. Gå ind i en vilkårlig labyrint og gå gennem alle dens korridorer [120] [121] .
Problemet med tre huse og tre brønde . Læg ikke-krydsende stier fra hvert af de tre huse til hver af de tre brønde. Dette problem, ligesom Königsberg-broproblemet, har ingen løsning [122] .
Problemet med ridderens træk . Gå ridderen rundt om skakbrættet , besøg hver celle præcis én gang, og vend tilbage til den oprindelige celle [123] .
Opgave problem . Lad virksomheden kræve flere forskellige typer arbejde, og hver medarbejder er kun egnet til nogle af dem og kan ikke udføre mere end ét job ad gangen. Hvordan skal opgaver fordeles for at køre det maksimale antal opgaver på samme tid? En todelt graf hjælper med at løse problemet, hvor hjørnerne af den ene del er ansatte, den anden er job, og hver kant er en passende jobopgave [124] .
Kombinatorisk optimering [125] .

Problemet med den korteste vej . Givet en ( rettet ) graf og hver vægt af dens kant (bue) repræsenterer den tid, det tager at krydse den. Find den korteste vej (i tid) mellem de givne hjørner.
Minimum spaning tree problem . Antag, at flere computere skal forbindes på faste steder for at danne et computernetværk , og omkostningerne ved at skabe en direkte forbindelse mellem et hvilket som helst par af computere er kendt. Hvilke direkte forbindelser skal bygges for at minimere omkostningerne ved netværket?
Steiners minimale træproblem . Lad der være en vilkårlig delmængde af hjørner af en forbundet vægtet graf . Find et undergraftræ med minimumsummen af kantvægte , der indeholder alle hjørner af en given delmængde.
Problemet med den rejsende sælger (TSP) . Lad sælgeren nødt til at besøge flere byer i løbet af den næste måned. Vægtene repræsenterer rejseomkostningerne mellem hvert par af byer. Hvordan arrangerer man besøg på en sådan måde, at de samlede omkostninger ved rejsen minimeres? Du skal med andre ord finde en Hamilton-cyklus, hvis samlede kantvægt er minimal.
Problemet med maksimalt flow . Lad vand pumpes gennem et netværk af rørledninger fra en kilde til et afløb. Grafmodellen er et netværk, hvor hver buevægt er den øvre grænse for flowet gennem den tilsvarende rørledning. Find det maksimale flow fra kilde til synke.
Problemet med det kinesiske postbud . Find minimumsvægtcyklussen over alle kanter i en given vægtet graf, hvor vægten af kanterne afhænger af anvendelsen (f.eks. afstand, tid, omkostninger osv.).
Kinesisk postmandsproblem (digraf). Når det udføres, bevæger strømmen af et computerprogram sig mellem forskellige tilstande, og overgange fra en tilstand til en anden afhænger af inputdataene. Ved test af software vil vi gerne generere inputdata, så alle mulige overgange testes.

Programudførelsesflowet er modelleret af en digraf, hvor hjørnerne er programtilstande, buerne er overgange, og hver af buerne er tildelt en kaldelabel for den tilsvarende overgang. Så er problemet med at finde en sekvens af inputdata, der forårsager alle overgange og minimerer deres samlede antal, det svarer til at finde en rettet vej for det kinesiske postbud af minimum længde.

Opgaven med RNA- rekonstruktion . Baseret på uordnede fragmenter af det samme RNA, rekonstruer denne RNA-kæde eller et komplet sæt egnede RNA-kæder.
Problemet med at rekonstruere en række af cifre. Lad for en given streng af cifre — antallet af cifre i strengen, — antallet af understrenge i strengen. Hvor mange forskellige strenge er der svarende til de givne og , , ? $f_{i}$ $jeg$ $f_{ij}$ $ij$ $f_{i}$ $f_{ij}$ $i,j=1,2,\dots ,n$ $f_{ii}=0$

Graf isomorfi problem . Udvikl en generel algoritme til at bestemme grafisomorfi eller bevis, alternativt, at en sådan algoritme ikke eksisterer [126] .
Grafrekonstruktionsproblem . Kan to ikke-isomorfe simple grafer med tre eller flere toppunkter og ingen etiketter på toppunkterne have den samme liste over undergrafer, hver opnået ved at slette et toppunkt [127] ?
Problemet med en undergruppe af uafhængighedssystemet med maksimal vægt. Lad en ikke-negativ vægt gives for hver kant af grafen. Find delmængden af uafhængighedssystemet med den maksimale sum af vægtene af dets kanter [128] .
Problemet med at matche med maksimal vægt. Et særligt tilfælde af det tidligere problem [129] .
Maksimeringsproblem. Bestem i grafen det maksimale antal toppunkt- uafhængige stier, der forbinder ethvert par af toppunkter [130] .
Minimeringsproblemet. Bestem i grafen det mindste antal hjørner, der deler ethvert par aborrer [130] .
Subgraf -homeomorfismeproblemet . Bestem, om den første graf indeholder en subgraf, der er homøomorf til den anden graf [131] .
Klikeproblemet er et andet NP-komplet problem.
Planaritet af en graf - er det muligt at afbilde en graf på et plan uden krydsende kanter (eller med et minimum antal lag, som bruges ved sporing af sammenkoblingerne af printplader eller mikrokredsløb).

Grafteori omfatter også en række matematiske problemer, der ikke er løst til dato .

Klassifikationer af anvendelser af grafteori

Klassificering af anvendelser af grafteori i henhold til graden af relation til matematik [132] :

matematiske felter: gruppeteori , matrixteori , numerisk analyse , sandsynlighedsteori , topologi , kombinatorisk analyse og en matematisk model for binære relationer ;
ikke-matematiske områder: fysik , kemi , kommunikationsteori , computerdesign , elektroteknik , maskinteknik , arkitektur , operationsforskning , genetik , psykologi , sociologi , økonomi , antropologi og lingvistik .

Klassificering af anvendelser af grafteori i henhold til graden af væsentlighed af interaktion [133] [134] :

flere materielle interaktioner er især fysiske netværk (f.eks. elektriske kredsløb ), veje , organiske molekyler ;
mindre materielle interaktioner er især økosystemer , sociologiske relationer , databaser , kontrolflow i et computerprogram .

Klassificering af anvendelser af grafteori i henhold til de anvendte typer grafer [135] :

simple grafer, det vil sige ikke multigrafer, digrafer eller pseudografer;
multigrafer og pseudografier, men ikke digrafer;
simple digrafier;
(pseudo)digrafier.

Klassificering af anvendelser af grafteori i henhold til typerne af attributter for de anvendte grafer [136] :

kanterne og spidserne af den anvendte graf har ingen attributter;
kanterne på den anvendte graf har attributter, hjørnerne ikke;
hjørnerne af den anvendte graf har attributter, kanterne ikke;
både kanter og hjørner af den anvendte graf har attributter.

Klassificering af anvendelser af grafteori efter anvendelsesområder.

Klassificeringen udføres i henhold til indholdsfortegnelsen i bogens anden del [137] .

Ansøgninger til økonomi og driftsforskning.
kombinatoriske opgaver.
Gåder til spil.
Matchende.
Tekniske applikationer.
Naturvidenskab.
Opgaverne med at studere mennesket og samfundet.
Yderligere applikationer.
strømme i netværk.

Klassificering af anvendelser af grafteori efter anvendelsesområder.

Klassificeringen udføres i henhold til tilgængelig videnskabelig litteratur . Liste over nogle anvendelsesområder for grafteori med referencer til litteraturen:

arkæologi [138] ;
blokdiagrammer [139] ;
kunstig intelligens [140] ;
endelige automater [141] ;
logistik [142] ;
programmering [143] ;
sociologi [144] ;
kredsløb [145] ;
teori om algoritmer [146] ;
flyvekontrol [147] ;
kemoinformatik [148] ;
kemisk kinetik (for eksempel fasereglen ) [149] ;
kemi ( computerkemi ) [150] [151] [152] ;
økonomi [153] .

Nogle anvendelser af grafteori

Før man anvender matematisk kraft på problemer i den virkelige verden, er det nødvendigt at bygge en matematisk model af problemet. Grafer er et utroligt alsidigt matematisk modelleringsværktøj. Nedenfor er flere andre anvendelser af grafteori end problemer i grafteori [154] .

Kombinatorisk optimering . Kantvægt er en af de mest brugte grafattributter, især ved kombinatorisk optimering. For eksempel kan vægten af en kant repræsentere:

billetpris;
rejsetid;
rumlig afstand;
strømtab;
øvre flowgrænser ;
ind- og udgange til overgange i en endelig automat .

Der er problemer løst ved at indstille vertex-attributter i en grafmodel. For eksempel kan vægten af et toppunkt repræsentere:

produktionsomkostninger ; _
tidsinterval i skemalægningsteori ;
tilstanden af Markov-processen ;
tilstanden af en node i et forbindelsesnetværk.

Modeller på simple grafer.

Arkæologi . Lad en samling af artefakter findes på stedet for en by, der eksisterede fra 1000 f.Kr. til 1000 e.Kr. Derefter kan du bygge en graf med toppunkter - artefakter, og toppunkterne er tilstødende, når de tilsvarende artefakter er fra samme grav. Lad os antage, at de artefakter, der findes i den samme grav, har overlappende brugsperioder. Hvis vi bygger en intervalgraf , så er der en fordeling af delintervaller af det indledende interval (-1000, 1000) ( skalering er mulig ), i overensstemmelse med det arkæologiske fund.
Sociologi . I et socialt datingnetværk er hjørnerne mennesker, og kanterne indikerer, at de tilsvarende par mennesker kender hinanden. Inddragelsen af begrebet selverkendelse kræver cyklusser af selverkendelse i modellen, som svarer til sløjfer i grafen.
Geografi . I en geografisk model kan grafens hjørner repræsentere lande (regioner, stater), og kanter kan repræsentere en fælles grænse.
Geometri . Konfigurationen af hjørner og kanter af ethvert polyeder i tredimensionelt rum danner en simpel graf, som kaldes dens 1-skelet . 1-skeletterne af de platoniske faste stoffer er regulære grafer .
Computer Design . Et antal processorer er forbundet sammen på en enkelt chip til en multiprocessor -computer, der kan udføre parallelle algoritmer . I grafmodellen for et sådant netværk af sammenkoblinger er et vertex en enkelt processor, en kant er en direkte forbindelse mellem to processorer. Specifikationen for parallelle arkitekturer illustrerer nogle af samspillet mellem grafteori og abstrakt algebra .
Byggeri . En todimensionel ramme af stålbjælker forbundet med hængsler, der tillader hver bjælke at rotere i et plan, er stiv, hvis ingen af dens bjælker kan rotere . Problemet med at afgøre, om en ramme er stiv, kan reduceres til forbindelse i en todelt graf.
Fysisk kemi . Kulbrinte eret kemisk molekyle sammensat af brint og kulstofatomer . Det er mættet , hvis det indeholder det maksimale antal brintatomer for dets kulstofatomer. Mætning opstår, når kun simple bindinger er til stede , det vil sige, når kulbrintestrukturmodellen er en simpel graf. Brintatomet har én elektron og er altid 1 -valent i molekylet. Kulstofatomet er 4-valent og har fire elektroner i sin ydre skal . De mættede kulbrinter butan og isobutan har samme kemiske formel , men deres grafer er ikke isomorfe , så de er isomerer . ${\ce {C4H10}}$
Datalogi . For et netværk af computere er dermulige par af computere, der kan forbindes direkte. Hvis alle par er forbundet, så ercomputerne forbundet, men mange af forbindelserne er ikke nødvendige. Hvis computere er forbundet med et minimum antal kanter, danner disse kanter et træ , og antallet af kanter i træet er én mindre end antallet af hjørner. $n$ ${n\choose 2}={\frac {n^{2}-n}{2))$ $n$
Retsvidenskab . Lad ABC Corporation udvikle og markedsføre en computerchip , og snart vil DEF Corporation lancere en chip med slående operationel lighed med markedet. Hvis ABC beviser, at DEF-skemaet er en omarrangering af ABC-skemaet, dvs. at skemaerne er isomorfe , vil der være grundlag for en patentkrænkelsessag . Hvis ABC kontrollerer for strukturvedholdenhed for hver knude på DEF-chippen, kan opgaven tage for lang tid. At kende organiseringen af mikrokredsløb kan spare tid.
Teori om algoritmer . Lad en distribueret algoritme arbejde i et sammenkoblingsnetværk med en array-arkitektur. Og lad det tilgængelige netværk af forbindelser være en 13-dimensionel hyperkubegraf . Hvis en 13-dimensionel hyperkubegraf indeholder en undergraf , et gitter af størrelse, så kan algoritmen overføres direkte til denne hyperkube. $8\ gange 8\ gange 32$ $Q_{13}$ $8\ gange 8\ gange 32$
Datalogi . Værdierne k for vertex k - connectivity og edge k - connectivity bruges i en kvantitativ model for netværksoverlevelse , som er netværkets evne til at opretholde forbindelser mellem dets noder efter fjernelse af nogle kanter eller noder.
Datalogi . I et kommunikationsnetværk er en fejl ødelæggelsen (fjernelsen) af et toppunkt eller en kant fra modelleringsgrafen. Jo højere tilslutningsmuligheder af hjørner og kanter er, jo mere pålideligt er netværket. Jo færre forbindelser, der bruges til at oprette forbindelse, jo billigere er netværket. Vi får følgende optimeringsproblem: for k mindre end n , find en k - forbundet n -vertex-graf med det mindste antal kanter.
Kodningsteori . Rumfartøjet transmitterer nogle talkodede billeder, hvor tallene er mørkeværdierne for billedpunkterne. Fordelen ved Gray -kodning af et billedeer, at hvis en fejl på grund af "kosmisk støj" resulterer i en fejllæsning af et binært ciffer i et tal, så vil fortolkningen af dette tal afvige lidt fra den sande værdi af mørket. Rækkefølgen Gray-kodensvarer til en Hamiltonsk cyklus i en hyperkubegraf . $n$ $Q_{n}$
Computer Design . En metode til at miniaturisere et ikke-plant elektronisk netværk er at påføre isolering mellem flade lag af bare ledere, der forbinder knudepunkterne. Spånstørrelse og -omkostninger reduceres , samtidig med at antallet af lag minimeres. En simpel tilgang til at designe flerlagskredsløb er at bruge "fælles linjetegninger" af spændende undergrafer, der inducerer kantopdeling. Det betyder, at noderne i hvert lag er i samme position på planet, og hvert lag er tegnet som linjestykker.
Kommunikationsteori . Det mindste antal radarstationer, der kræves for at overvåge flere strategiske objekter, er dominanstallet for den tilsvarende graf.
Transport . Lad en naturkatastrofe ramme en region bestående af små landsbyer. Punkterne på grafen er landsbyerne i regionen. Ribben indikerer, at en ambulancestation, der er oprettet i en af landsbyerne, også kan betjene en anden. Derefter beskriver det mindste dominerende sæt af grafen en måde at betjene regionen med et minimum antal førstehjælpsstationer.
Datalogi . Overvej problemet med at placere damer på et skakbræt : hvert felt på brættet er enten besat af en dronning eller nået af en dronning i ét træk. At bestemme minimumsantallet af dronninger svarer til at finde dominanstallet for en graf med 64 hjørner, hvor kanterne svarer til dronningernes træk.

Modeller på rodfæstede træer .

Databaser . Mange informationsstrukturer inden for datalogi er baseret på træer . De mapper og undermapper (eller mapper og undermapper), der indeholder computerbrugerens filer , er normalt repræsenteret af operativsystemet som noder i et rodfæstet træ .
Databaser . Binære søgetræer gemmer specialordnede data til effektive søgninger . Især hvisnoderne i det binære søgetræ bruges korrekt til at gemmeelementnøgler , kan søgningen fuldføres i runtime . $n$ $n$ $O(\log(n))$
Teori om algoritmer . Designet af store computerprogrammer, der implementerer komplekse beslutningsstrategier, er ofte baseret på rodfæstede træer .
Databaser . Rodede træer bruges til at gemme information organiseret i kategorier og underkategorier. Dewey Decimal Classification for Libraries er et sådant eksempel.
Sprogvidenskab . Et rodfæstet træ kan bruges til at analysere en naturlig sprogsætning .
Teori om algoritmer . For en forbundet graf med et valgt toppunkt er træet med den korteste vej som et rodfæstet træ en kompakt måde at kortlægge den korteste vej fra et valgt toppunkt til ethvert andet. Bredth first-søgning opretter et træ for den korteste vej for en uvægtet graf , og Dijkstras algoritme opretter et sådant træ til en vægtet graf .
Datalogi . Når du krydser udtrykstræet , vil det resulterende udtryk blive vist i præfiks , postfix eller infix-notation , afhængigt af hvilken traversal der bruges. Infix-udtrykket kræver parenteser , som kan inkluderes i den rekursive traversering i rækkefølge ved at oprette en venstre parentes i starten af hver undertrægennemgang og en højre parentes i slutningen af hver undertrægennemgang.
Kodningsteori . Et binært træ kan bruges til at konstruere en præfikskode for et givet tegnsæt. For at gøre dette er de sidste hjørner af det binære træ markeret med disse symboler, kanter - 0 og 1 fra venstre mod højre, så vil kodeordet være sammensat af kantetiketter på stien fra roden til symbolet.

Modeller på farvede grafer .

Kommunikationsteori . Når man tildeler en udsendelsesfrekvens til radiosendere i samme region, kræver nogle senderpar forskellige frekvenser for at undgå interferens. Grafmodellen bruges til at løse problemet med at minimere antallet af tildelte forskellige frekvenser. Antag, at hvis to sendere er mindre end 100 km fra hinanden, skal de sende på forskellige frekvenser. Derefter bygges en graf, hvis toppunkter er sendere, og kanterne peger på par i en afstand på mindre end 100 km fra hinanden. Problemet med at tildele radiofrekvenser for at undgå interferens svarer til problemet med at farve toppunkterne på en graf, således at tilstødende hjørner har forskellige farver. Det mindste antal frekvenser vil være lig med det mindste antal farver.
Kemi . Lad spidserne af grafen repræsentere de forskellige kemikalier, der bruges i produktionsprocessen, og kanterne repræsentere et par kemikalier, der kan eksplodere, når de blandes. Så er det kromatiske tal på grafen det mindste antal lagerrum, der kræves for at opbevare separat par eksplosive stoffer.
Operationsforskning . Lad toppunkterne på grafen være kurser på et universitet, en kant forbinder to kurser, hvis og kun hvis mindst én studerende er tilmeldt begge kurser. Disse kurser kan ikke tages samtidigt. Så er det kromatiske tal på grafen det mindste antal akademiske timer adskilt i tid i klasseskemaet , hvor eleverne ikke vil have en konflikt mellem kurser .
Teori om algoritmer . Lad grafens hjørnepunkter være variable i et computerprogram , en kant forbinder to variable, der kan være aktive på samme tid. Så er det kromatiske antal af grafen det mindste antal registre , der kræves for at undgå mulig glidning - en tilstand af konstant ombytning .
Operationsforskning . Lad toppunkterne på grafen være studiekurser på et universitet, og en kant forbinder to kurser, hvis og kun hvis mindst tre studerende er tilmeldt begge kurser. Disse kurser kan ikke tages samtidigt. Men antallet af tidsfordelte akademiske timer i klasseskemaet er mindre end det kromatiske tal på grafen, hvor eleverne ikke har en konflikt mellem studieforløb . Så skal man planlægge på en sådan måde, at antallet af konflikter minimeres. Hvis grafens kanter vægtes afhængigt af konfliktens uønskede grad, f.eks. forbinder kanten den samme lærers uddannelsesforløb, så skal vi finde en farvelægning med den mindste fælles vægt af kanter med ensfarvet slutter.
Computer Design . Flere elektroniske enheder er på et printkort . Forbindelsesledningerne, der kommer ud af enhederne, skal have forskellig farve, så de kan skelnes. Det mindste antal påkrævede farver er det kantkromatiske tal på modelleringsnetværket.

Modeller på multigrafer og pseudografer.

Geografi . I en geografisk model kan hjørnerne af en multigraf repræsentere lande (regioner, stater), og kanterne kan repræsentere veje, der krydser en fælles grænse.
Kemi . For eksempel harbenzenmolekylet dobbeltbindinger for nogle par af dets atomer , så det er modelleret af en multigraf. Kulstofatomet harvalens 4 og er modelleret af et toppunkt på multigrafen af grad 4, hydrogenatomet har valens 1 og er modelleret af et toppunkt på grad 1
Transport . En speciel trolley, udstyret med en sensor, kører gennem dele af jernbanenettet for at søge efter defekter. Er det muligt at planlægge bevægelsen af vognen, så den diagnosticerer hver sektion af sporene nøjagtigt én gang, og derefter vender tilbage til udgangspunktet? Problemet svarer til at bestemme, om en multigraf er Euler .
Computer Design . Tilfældige udvekslingsgrafer tjener som modeller for parallelle arkitekturer, der er egnede til at udføre forskellige distribuerede algoritmer , herunder kortblanding og hurtig Fourier-transformation . Hjørnerne på den tilfældige udvekslingspseudograf er bitstrenge af længde . ${\displaystyle SE_{n))$ $n$
Computer Design . Computeren består af flere moduler og deres kontakter . Modulernes fysiske position bestemmes, og kontakterne skal tilsluttes . Kontakterne er små i størrelse, og der kan ikke sættes mere end to ledninger på en skive. For at minimere støj og forenkle ledningsføring bør den samlede ledningslængde holdes på et minimum. Den nødvendige konstruktion er givet af en Hamiltonsk sti med minimal vægt.
Transport . Hver weekend transporterer en privatskole n børn til m busstoppesteder. Forældre møder deres børn ved busstoppesteder. Skolen ejer k busser med forskellig kapacitet. Hvordan bygger man busruter med minimale samlede omkostninger? Hjørnerne på grafen er skolen og stopper, vægten af kanterne er afstanden mellem dem. Hver bus kan rumme flere grupper af børn, der stiger af ved forskellige stoppesteder, for ikke at overskride bussens kapacitet. Omkostningerne ved busruten er lig med prisen for Hamiltonian-cyklussen med minimumvægt. Opgaven er således at opdele m busstoppesteder i k delmængder, således at summen af ruteomkostningerne for alle busser er minimal.
Operationsforskning . Universitetet har flere undervisere til undervisning i flere kurser . Det er påkrævet at beregne det mindste antal akademiske timer i klasseskemaet, der kræves for at planlægge alle kurser, således at der ikke undervises i to afsnit af samme kursus på samme tid. Vi bygger en todelt graf over andelen af lærere og kurser, kanter forbinder lærere med deres kurser (en lærer kan undervise i forskellige kurser, og forskellige lærere kan undervise i det samme kursus). Udvælgelsen af undervisere til kurser kan udføres i en vis periode. Hvis kantfarven er en akademisk time i et dagligt skema, så er farven på kanterne af en todelt graf et muligt skema for kursusafsnit. Minimal kantfarvning bruger færrest akademiske timer.

Modeller på simple digrafer.

Kartografi . Bygadekortet kan repræsenteres som en blandet graf som følger. Punkterne på denne graf er byens objekter, og de orienterede og enkle kanter er gaderne med henholdsvis ensrettet og tovejstrafik.
Sociologi . Et hierarki kan repræsenteres som et rettet træ . For eksempel hierarkiet af beslutningstagning i en virksomhed. Grafer og digrafer bruges til at modellere sociale relationer , ikke kun fysiske netværk.
Økologi . Ernæringsforholdet mellem plante- og dyrearter i et økosystem kaldes et fødenet og er modelleret af en simpel digraf. Hver art i systemet er repræsenteret af et toppunkt, og buerne er rettet fra den art, der lever til den art, som den første art lever af.
Økonomi . I store projekter involverer planlægning ofte opgaver, der ikke kan begynde, før andre er afsluttet. Toppunkterne i digrafmodellen er opgaver, en bue fra et toppunkt til et andet betyder, at den anden opgave ikke kan starte før afslutningen af den første opgave. For at forenkle diagrammet tegnes der ikke buer som følge af transitivitet.
Programmering . Et computerprogram er et sæt programmeringsblokke med tilhørende kontrolflow . En digraf er en naturlig model for denne dekomponering: et toppunkt er en programmeringsblok forbundet, og hvis styring ved den sidste instruktion af en blok overføres til den første instruktion af en anden blok, så trækkes en bue fra den første blok til den anden blok . Flowdiagrammer har normalt ikke flere buer.
Elektroteknik . Bestem den elektriske strøm i hver gren af et elektrisk kredsløb ved hjælp af Ohms lov , Kirchhoffs første regel og Kirchhoffs anden regel . En effektiv løsningsstrategi er at bruge et spændingstræ til at finde det mindste sæt konturer af digrafen , hvis tilsvarende ligninger er tilstrækkelige til at løse problemet. Det grundlæggende grundlag for cyklusser er grundlaget for cyklusrummet , så dets tilsvarende ligninger vil udgøre et komplet sæt lineære algebraiske ligninger, og problemet vil blive løst.
Programmering . Lad n jobbehandles på én maskine . Den tid, det tager at behandle ethvert job efter et andet, er kendt. Hvordan organiserer man opgaver for at minimere den samlede tid? Vi tegner en digraf med n toppunkter - opgaver og med de tilsvarende vægte af buerne. Så er den nødvendige rækkefølge af opgaver givet af en Hamilton-sti med minimal vægt.
Økonomi . Givet prisen på en ny bil og stigningen i prisen hvert år forudsiges de årlige driftsomkostninger og gensalgsværdi. Hvordan minimerer du nettoomkostningerne ved at eje og drive en bil, når du starter med en ny bil? Vi bygger en digraf med antallet af knudepunkter 1 mere end antallet af driftsår, hvis buer går fra mindre til større år og har en vægt svarende til omkostningerne ved at købe en ny bil i året for begyndelsen af buen og dens vedligeholdelse indtil begyndelsen af året for buens afslutning. Problemet bunder i at finde den korteste vej fra det første toppunkt til det sidste.
Radio . Søgenetværket er modelleret af en digraf : toppen af digrafen er en person, buen er en envejs direkte forbindelse fra person til person. For at sende en notifikation fra person til person er det ikke nødvendigt at have en direkte forbindelse, der skal kun være en dirigeret sti. Den transitive lukning af en digraf definerer alle par af toppunkter, for hvilke der er en vej fra et toppunkt til et andet.
Programmering . Lad en procedure med flere operationer udføres på én maskine, og der er en naturlig delrækkefølge af operationer. Lineær udvidelse af dette sæt operationer ville løse problemet med lineær rækkefølge af operationer på maskinen.
Økonomi . Digrafmodellen bruges til at planlægge store komplekse projekter for at nå to mål: at planlægge aktiviteter, så tiden til at gennemføre projektet er minimal; identificere aktiviteter, hvis forsinkelse vil forsinke projektet. Hvis varigheden af hver hændelse er kendt, bruges den kritiske sti-metode (CPM)til at løse disse problemer

Modeller på (pseudo)digrafer.

Markov kæde . I en Markov-proces afhænger sandsynligheden for en overgang fra en tilstand til en anden kun af den aktuelle tilstand. I en grafmodel af en Markov-kæde er hver bue mærket med en overgangssandsynlighed fra tilstanden ved starttoppunktet til tilstanden ved endetoppunktet, og summen af sandsynligheden for de udgående buer fra hvert toppunkt er 1. En Markov diagram er et eksempel på en vægtet graf .
Leksikalsk analyse . Kildekoden til et computerprogram kan opfattes som en streng af tegn. Den leksikalske scanner skal scanne disse tegn et ad gangen og genkende, hvilke tegn "kombinerer" for at danne et syntaktisk token eller leksem . En sådan scanner kan modelleres med en mærket digraf . Det første toppunkt er starttilstanden før scanning af tegn. Det andet toppunkt er accepttilstanden, hvor en understreng af de scannede tegn er en gyldig identifikator. Det tredje toppunkt er den afviste tilstand - understrengen blev kasseret som en ugyldig identifikator. Buemærkerne angiver, hvilke symboler der forårsager overgangen fra starttilstand til sluttilstand.
Spilteori . Lad spilleren, begyndende med $3, spille det næste spil. Der kastes to mønter. Hvis to hoveder kommer op, vil spilleren vinde $3, ellers vil de tabe $1. Spilleren spiller, indtil de enten mister alle deres penge eller har mindst $5. Grafmodellen er en Markov- kædegraf .

Anvendelse af Euler-cyklussen og det kinesiske postbudsproblem.

Kodningsteori . Lad den roterende tromle have 16 forskellige sektorer. Tildel 0 eller 1 til hver sektor ved at placere ledende materiale i nogle sektorer og ikke-ledende i andre. Derefter "læser" vi med faste sensorer en 4-bit streng svarende til de fire sektorer, der faldt på sensorerne. Hvis 16-bit strengen af trommesektorer er en (2, 4) de Bruijn-sekvens , så kan tromlens position bestemmes ud fra den 4-bit understreng, som sensorerne fanger. Dette er mere økonomisk end en 4-bit kode pr. sektor. (2, 4)-de Bruijn-sekvensen er konstrueret under anvendelse af (2, 4)-de Bruijn-digrafen .
Byens økonomi . Digrafen er et netværk af ensrettede gader, de tykke buer er de gader, der skal fejes, kantens vægt er den tid, det tager at passere gaden uden at feje, og den tid, det tager at feje gaden, er det dobbelte. Hvilken rute minimerer den samlede tid til at feje alle påkrævede gader, der starter og slutter ved et givet toppunkt?
Datalogi . Plotter flere tusinde kopier af netværket, hvis det tager dobbelt så lang tid at bygge en vandret kant end en lodret. Opgaven med at dirigere plotteren, så den samlede tid holdes på et minimum, er modelleret som et kinesisk postbuds opgave.
Sociologi . Lad nogle par i en afdeling på seks mødes privat i samme mødelokale. Er det muligt at organisere to-personers konferencer, så en af deltagerne i hver konference (undtagen den sidste) også deltager i den næste, men ingen deltager i tre på hinanden følgende konferencer?
Genetik . I en RNA-kæde (ribonukleinsyre) repræsenterer hvert led et af de fire mulige nukleotider . Når man forsøger at identificere en RNA-streng i en ukendt prøve, tillader den nuværende teknologi ikke direkte identifikation af lange strenge. Der er en metode til fragmentering og subfragmentering af en lang RNA-kæde til identificerbare understrenge. Hutchinsons strategi er at konstruere en Euler-digraf, hvis buer er mærket med fragmenter, så hver Euler-sti svarer til en RNA-streng.
Kombinatorik . Sammenfattende den tidligere anvendelse i genetik kan RNA opfattes som en række af nukleotidnumre. Lad for en given streng af cifre— antallet af cifrei strengen,— antallet af understrengei strengen. Så afhænger informationen indlejret i RNA kun af talleneog,,. For at rekonstruere en streng bygger vi en digraf af tilstødende matrix , hvor i stedeter. Så vil alle forskellige Euler-stier give alle mulige matchende strenge. $f_{i}$ $jeg$ $f_{ij}$ $ij$ $f_{i}$ $f_{ij}$ $i,j=1,2,\dots ,n$ $f_{ii}=0$ $(f_{ij})$ $f_{ii}=0$ $f_{i}$

Nogle grafteoretiske algoritmer

Algoritmerne præsenteres i et komprimeret format uden detaljer om computerimplementering. Der er mange projekter, der foreslår at konvertere algoritmer til computerprogrammer [154] .

Rekursiv grafisk sekvens . En rekursiv algoritme, der bestemmer, om en ikke-tiltagende sekvens er en sekvens af toppunkter i en graf.
Bestemmelse af grafisomorfi ved udtømmende opregning . To grafer er isomorfe, hvis deres sæt af hjørner kan ordnes, så deres nabomatricer er identiske.
Direkte venstre trægennemgang (NLR) . Først krydser vi det venstre undertræ og viser kun hvert toppunkt, når det vises for første gang.
Omvendt venstre trægennemgang (LRN) . Først krydser vi det venstre undertræ og viser kun hvert toppunkt, når det vises for sidste gang.
Centreret venstre trægennemgang (LNR) . Først krydser vi det venstre undertræ, føj til listen hvert knudepunkt, der har et venstre undertræ, først når det vises for anden gang, føj de resterende spidser til listen, når de vises for første gang.
Søg i et binært søgetræ . Ved hver iteration udelukker vi enten venstre eller højre undertræ fra resten af søgningen, afhængigt af om målnøglen er henholdsvis større eller mindre end nøglen i den aktuelle node.
Tilføjelse til det binære søgetræ . Fra et iterativt synspunkt udføres den binære søgning, indtil den ender ved det endelige toppunkt. Den nye nøgle tildeles derefter til den nye knude, som bliver venstre eller højre undertræ af den endeknude, afhængigt af sammenligningen af den nye nøgle med endeknudepunktets nøgle.
Huffman algoritme . I en præfikskode , som bruger kortere kodeord til at kode hyppigere tegn, kræver meddelelser generelt færre bits end i kode, der ikke gør det. Huffman-algoritmen bygger netop sådan en effektiv præfikskode ved at forbindeto træer med mindst vægt i den oprindelige skov til et nyt træ.
Tilføjelse til prioritetstræet . Først tilføjes et nyt vertex til det første ledige sted i prioritetstræet, og derefter flyttes det op til roden , indtil dets prioritet er mindre end eller lig med prioriteten af det overordnede vertex .
Fjernelse fra prioritetstræet. Først erstattes det toppunkt, der skal fjernes, af det toppunkt, der indtager den længst højre plads i det nederste niveau af prioritetstræet. Dette toppunkt flyder derefter iterativt ned og bytter plads med den efterkommer med højere prioritet, indtil dens prioritet overstiger prioriteterne for begge efterkommere.
Prufer kodning . En Prufer sekvens af længdeer konstrueret ud fra et givet træ medhjørner nummereretmed , ved at slette knudepunkter, indtil der ikke er nogetknudepunkt tilbage. $n-2$ $n$ $1,2,\dots ,n$ $2$
Prufer afkodning . Det kodede træ er rekonstrueret ud fra Prufer-sekvensenog listen over træets. ${\displaystyle p_{1},p_{2},\dots ,p_{n-2))$ $1,2,\dots ,n$
At bygge et spændingstræ . Med udgangspunkt i et givet toppunkt på grafen konstrueres et spændingstræ med rod i et givet toppunkt ved at bruge et hvilket som helst skema til at finde nye træspidser ved siden af gamle toppunkter.
Bygge en spændende skov . Startende fra et givet toppunkt for hver komponent i en frakoblet graf, konstrueres et spændingstræ af den aktuelle komponent med rod i et givet toppunkt ved at bruge et hvilket som helst skema til at finde nye træspidser ved siden af gamle toppunkter.
Depth First Search (DFS) . Med udgangspunkt i et givet toppunkt på grafen bygges et søgetræ som følger. Et nyt toppunkt vælges på grafen, ved siden af det senest opdagede toppunkt på det allerede konstruerede træ. Hvis dette ikke er muligt, sker en tilbagevenden til det tidligere detekterede toppunkt, og forsøget gentages. Som et resultat bevæger søgningen sig dybere ind i grafen (deraf navnet "i dybden").
Breadth First Search (BFS) . Med udgangspunkt i et givet toppunkt på grafen bygges et søgetræ som følger. Søgningen "gafler" fra et givet toppunkt og vokser træet ved at vælge tilstødende kanter med træspidser så tæt som muligt på det givne toppunkt. Som et resultat bevæger søgningen sig langs grafens bredde i lag, der er lige langt fra det givne toppunkt (deraf navnet "bred").
Prims minimumspændende træ . Vi leder efter et spændingstræ af en forbundet vægtet graf med minimumsummen af kantvægte . Vi starter fra et hvilket som helst toppunkt på grafen, og ved hver iteration bygger vi et Prim-træ ved at tilføje et nyt toppunkt forbundet til træet med en kant med minimumsvægt.
Dijkstras korteste vej . De korteste veje fra et givet toppunkt i en vægtet graf til alle andre toppunkter søges. Vi tager udgangspunkt i et givet toppunkt på grafen og tilføjer ved hver iteration et nyt til de behandlede toppunkter, forbundet med en kant til et af de behandlede toppunkter og nærmest det givne toppunkt.
Anvendelse af dybde-først-søgning .

Søg efter broer . På en given sammenhængende graf søges broer ved hjælp af den første dybde -første passage indtil den første tilbagevenden og sammentrækning af alle cykluskanter til et toppunkt.
Topologisk slags . På en given konturløs digraf nummereres toppunkterne, startende fra det maksimale antal, ved at bruge den første dybde-første søgepas til den første retur og nummerering af stiens sidste toppunkt med det aktuelle maksimale antal, hvilket fjerner dette toppunkt fra efterfølgende søgninger.
Søg efter artikulationspunkter . På en given sammenhængende graf søges artikulationspunkter ved hjælp af dybde -først søgning , en speciel nummerering af hjørnerne i dybde-første søgetræet og sammenligning af disse tal.
Bloker søgning . For en given forbundet graf søges alle dens blokke. Den tidligere algoritme bruges som en underrutine.
Tarry 's Maze Exit Algorithm . Vend aldrig tilbage, hvis der er et alternativ, og passer aldrig en anden gang i samme retning. Med andre ord skal du altid krydse en ny vej, før du vender tilbage, hvilket gør denne algoritme til en slags dybde-først-søgning.
Nærmeste nabo-algoritme i problemet med rejsende sælger . Den enkleste TSP- heuristik er nærmeste nabo. Dette er en grådig algoritme : den billigste måde at gå et andet sted er valgt. Med andre ord er den nærmeste naboalgoritme en dybdegennemgang, der vælger kanterne på den mindste vægt.
Algoritme til søgning efter stærkt forbundne komponenter . En algoritme, der bruger dybde-først-søgning i kombination med to stakke. Strategien for at finde gensidigt tilgængelige hjørner er at holde styr på, hvordan ikke-træbuer forbinder dens hjørner.

Grådig algoritme til at løse problemet med en delmængde af uafhængighedssystemet med maksimal vægt. Lad en ikke-negativ vægt gives for hver kant af grafen, og der gives et system med grafuafhængighed. Vi itererer over alle grafens kanter, startende med den maksimale vægt, og bygger ud fra dem en delmængde af uafhængighedssystemet med den maksimale sum af vægtene af kanterne.
En grådig algoritme til at løse problemet med maksimal vægtmatchning. Et særligt tilfælde af den tidligere algoritme.
Konstruktion af en optimalt forbundet graf med toppunkter. $k$ $n$ Frank Harari udviklede en procedure til at konstruere en -forbundet Harari-graf på hjørner, der har det mindste antal kanter for . Konstruktionen af Harari-grafen begynder med en -cyklisk graf, hvis toppunkter er sekventielt nummereret med uret langs omkredsen. Konstruktionen afhænger af relationen og falder i tre tilfælde. $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$
Konstruktion af Euler-cyklussen . I en forbundet graf, hvor alle toppunkter har en lige grad, vælger vi et hvilket som helst toppunkt og betragter det som en Euler-cyklus. Ved hver iteration tilføjer vi enhver cyklus af nye kanter, der har et fælles toppunkt med den aktuelle Euler-cyklus.
Konstruktion af (2, n )-de Bruijn-sekvensen . Vi konstruerer (2, n )-de Bruijn-digrafen . Vi vælger et toppunkt i denne digraf og bygger en orienteret Euler-cyklus af digrafen, startende fra det valgte toppunkt. Sekventielt, startende fra det valgte toppunkt, går vi rundt i Euler-cyklussen og samler en-bit-etiketter af grafbuerne i de Bruijn-sekvensen.
Opbygning af en postmandsløkke . Sporing af kanter langs de korteste veje af en vægtet forbundet graf mellem hjørner af ulige grader. Hvis alle kanterne på en sti mellem to hjørner af ulige grad duplikeres, bliver graderne af disse to hjørner lige, og pariteten af graden af hvert indre hjørne af stien forbliver uændret.
Algoritme for minimumspændingstræet og dets fordobling i problemet med rejsende sælger . Find det mindste spændingstræ . Vi fordobler hver kant af træet, vi får Euler-grafen . Vi bygger en Euler-cyklus . Vi bygger en Hamilton-cyklus fra Euler-cyklussen, og bruger korte stier, når Euler-cyklen går i stykker.
Minimum spændingstræ og matchende algoritme i problemet med den rejsende sælger . Find det mindste spændingstræ . Vi bygger en Euler-graf ved at tilføje kanter fra nogle matchende til spændingstræet. Vi bygger en Euler-cyklus . Vi bygger en Hamilton-cyklus fra Euler-cyklussen, og bruger korte stier, når Euler-cyklen går i stykker.
En simpel test for planheden af en dobbeltforbundet graf . Algoritmen kræver beregningstrin. Først tegner vi en hvilken som helst cyklus af en dobbeltforbundet graf. Derefter tilføjer vi cyklusser, indtil grafen er bygget (plan) eller kanterne skal skære hinanden (ikke-plane). $O(n^{2})$
Grådig vertexfarvning. En sekventiel algoritme, der hurtigt krydser hjørnerne af en graf i en given rækkefølge og tildeler hvert hjørne den første tilgængelige farve. Denne farvning er usandsynligt minimal, og det er usandsynligt, at nogen polynomiel- tidsalgoritme kan gøre dette, da problemet med at beregne det kromatiske tal for en graf er NP-komplet .
Grådig vertexfarvning med højeste grad . På hvert trin, blandt de ufarvede hjørner med den maksimale grad, vælges den, der har det største antal tilstødende hjørner i forskellige farver.
Grådig kantfarvning . Svarer til grådig vertexfarvning.
Grådig kantfarvning af en maksimal matchning. Ved hvert trin, blandt de ufarvede kanter , søges den maksimale match , og derefter males alle dens kanter med samme farve.
Warshalls algoritme til at finde en transitiv lukning. Lad en digraf gives. En beregningseffektiv algoritme konstruerer en sekvens af digrafer, således at den foregående digraf er en undergraf af den næste digraf, og den sidste digraf er en transitiv lukning af den originale. Den næste digraf fås fra den forrige ved at tilføje en bue, hvis der ikke er nogen bue, hvis der er en bane af længde 2 fra startpunktet på den nye bue til slutpunktet.
Kahns algoritme til topologisk sortering . Dette er en simpel algoritme til at konstruere en lineær udvidelse et delvist ordnet sæt . Ideen er altid at vælge minimumselementet ved hvert trin i algoritmen.
Beregning af det tidligste tidspunkt for en begivenhed. Ved hver iteration i den vægtede acykliske digraf af et stort komplekst projekt vælges et toppunkt, der ikke inkluderer nogen bue, og de tidligste tidsværdier for dets efterfølgende hjørner opdateres i overensstemmelse hermed. Derefter fjernes dette toppunkt fra digrafen, og den næste iteration begynder. Algoritmen beregner de længste veje fra det oprindelige toppunkt til hinanden.
Beregning af seneste begivenhedstidspunkt. Svarer til beregningen af det tidligste hændelsestidspunkt, men udføres efter beregningen af det tidligste hændelsestidspunkt i modsat retning fra toppen af projektslutdigrafen, som initialiseres med det tidligste hændelsestidspunkt.

Ved hver iteration i den vægtede acykliske digraf af et stort komplekst projekt vælges et toppunkt, der ikke inkluderer nogen bue, og de tidligste tidsværdier for dets efterfølgende hjørner opdateres i overensstemmelse hermed. Derefter fjernes dette toppunkt fra digrafen, og den næste iteration begynder. Algoritmen beregner de længste veje fra det oprindelige toppunkt til hinanden.

Se også

Ordliste over grafteoretiske termer

Noter

↑ Akimov O. E. Diskret matematik: logik, grupper, grafer, 2003 , s. 238.
↑ 1 2 3 Karpov D.V. Graph Theory. 2017 eller senere , s. 2-3.
↑ 1 2 3 Ore O. Grafer og deres anvendelse, 1965 , s. 6.
↑ Wilson R. Introduction to Graph Theory, 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. Graph Theory and Its Applications, 1962 , s. 5.
↑ Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Forelæsninger om grafteori, 1990 , s. 3.
↑ Harari F., Palmer E. Enumeration of Earls, 1977 , s. 255.
↑ Christofdes N. Grafteori. Algoritmisk tilgang, 1978 , s. 7.
↑ 1 2 3 Harari Frank. Graph Theory, 2003 , s. 13.
↑ 1 2 Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Behind the pages of a Mathematics Textbook, 1996 , s. 288.
↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 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-grafer og relaterede emner, 2002 , s. elleve.
↑ 1 2 M. Camille Jordan. Sur les assemblages de lignes, 1869 .
↑ Romanovsky I.V. Diskret analyse, 2003 , s. 185.
↑ Gross JL, Yellen J. Handbook of graph theory, 2004 , s. 35.
↑ Sylvester JJ Chemistry and algebra, 1878 , s. 284.
↑ 1 2 3 Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
↑ 1 2 Denes Konig. Theory of finite and infinite graphs, 1990 , s. tredive.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 151-152.
↑ 1 2 3 4 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 12.
↑ Referater fra møderne i konferencen for det kejserlige videnskabsakademi fra 1725 til 1803. Bind I. 1725-1743, 1897 , s. 220-221.
↑ 1 2 3 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. femten.
↑ 1 2 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 26.
↑ Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 31-32.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 17.
↑ Harari Frank. Graph Theory, 2003 , s. atten.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 97-99.
↑ Harari Frank. Graph Theory, 2003 , s. 126.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 127-128.
↑ Biografisk skitse af Harari , 2005 .
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 5.
↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. xi.
↑ 1 2 Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 145.
↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 .
↑ Denes Konig. Teori om endelige og uendelige grafer, 1990 .
↑ Wilson R. Introduction to Graph Theory, 1977 , s. 6.
↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 21.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. xi-xii.
↑ Akimov O. E. Diskret matematik: logik, grupper, grafer, 2003 , s. 236-237.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. xi.
↑ Goodman S., Hidetniemi S. Introduktion til udvikling og analyse af algoritmer, 1981 , s. 47.
↑ Reinhard Diestel. Graph Theory, 2016 , Noter, s. 33.
↑ Distel R. Graph Theory, 2002 , s. 43.
↑ Kormen T. H. et al. Algoritmer: konstruktion og analyse, 2009 , s. 608.
↑ 1 2 3 4 Ore O. Grafer og deres anvendelse, 1965 , s. 15-19.
↑ Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 39.
↑ Zykov A. A. Fundamentals of graph theory, 2004 , s. 512-517.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 469.
↑ Berge K. Graph Theory and Its Applications, 1962 , s. 7.
↑ Reinhard Diestel. Graph Theory, 2016 , s. en.
↑ Distel R. Graph Theory, 2002 , s. femten.
↑ Harari Frank. Graph Theory, 2003 , s. 21-22, 27-28, 31-32.
↑ Reinhard Diestel. Graph Theory, 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. Udvalgte kapitler af grafteori, 2008 , s. 2. Betegnelse G - fra engelsk. graf og tysk. Graf - graf, V - engelsk. vertex - top, E - engelsk. kant - kant.
↑ Tutt W. Graph Theory, 1988 , s. 16.
↑ Basaker R., Saaty T. Finite Graphs and Networks, 1974 , s. elleve.
↑ 1 2 Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 5. Betegnelse K - fra det. komplet - komplet.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 2. Betegnelse deg - fra engelsk. grad - grad.
↑ Harari Frank. Graph Theory, 2003 , s. 23-24.
↑ Reinhard Diestel. Graph Theory, 2016 , 1.1, 1.10.
↑ Distel R. Graph Theory, 2002 , 1.1, 1.10.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 2. Betegnelse G - fra engelsk. graf og tysk. Graf - graf, V - engelsk. vertex - top, E - engelsk. kant - kant.
↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 21. Betegnelse D - fra engelsk. direkte - direkte.
↑ Harari Frank. Graph Theory, 2003 , s. 26-27, 83-84.
↑ Reinhard Diestel. Graph Theory, 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. Graph Theory, 2016 , 1.5.
↑ Distel R. Graph Theory, 2002 , 1.5.
↑ Reinhard Diestel. Graph Theory, 2016 , Abstrakt.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 2.
↑ Distel R. Graph Theory, 2002 , kapitel 2.
↑ 1 2 Distel R. Graph Theory, 2002 , kapitel 3.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 3.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 1.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 4.
↑ Distel R. Graph Theory, 2002 , kapitel 4.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 5.
↑ Distel R. Graph Theory, 2002 , kapitel 5.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 6.
↑ Distel R. Graph Theory, 2002 , kapitel 6.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 7.
↑ Distel R. Graph Theory, 2002 , kapitel 7.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 8.
↑ Harari Frank. Graph Theory, 2003 , s. 28-30.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 9.
↑ Distel R. Graph Theory, 2002 , kapitel 9.
↑ Harari Frank. Graph Theory, 2003 , s. 85-88.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 10.
↑ Distel R. Graph Theory, 2002 , kapitel 10.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 11.
↑ Distel R. Graph Theory, 2002 , kapitel 11.
↑ Alon N., Spencer J. Probabilistic method, 2013 , 1.1. Probabilistisk metode.
↑ Reinhard Diestel. Graph Theory, 2016 , kapitel 12.
↑ Distel R. Graph Theory, 2002 , kapitel 12.
↑ Reinhard Diestel. Graph Theory, 2016 , 1.9.
↑ Distel R. Graph Theory, 2002 , 1.9.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 197.
↑ Harari Frank. Graph Theory, 2003 , s. 54-56.
↑ Ore O. Graphs and their application, 1965 , s. 9.
↑ Distel R. Graph Theory, 2002 , s. 33-34.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 248-249.
↑ Ore O. Graphs and their application, 1965 , s. 33.
↑ Ore O. Graph Theory, 1980 , s. 53.
↑ 1 2 I ét slag , 1940 .
↑ Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 89-90.
↑ Distel R. Graph Theory, 2002 , s. 139-140.
↑ Harari Frank. Graph Theory, 2003 , s. 17-18.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 371.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , Fire-farveproblemet er ikke nævnt i denne bog.
↑ Ore O. Graphs and their application, 1965 , s. 143-144.
↑ Ore O. Graph Theory, 1980 , s. 9.
↑ Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Behind the pages of a Mathematics Textbook, 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. Det labyrintproblem..
↑ Ore O. Graphs and their application, 1965 , s. 22.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 272.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 22.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 48-50, 176-179.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 64.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 83.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 208.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 209.
↑ 1 2 Gross JL, Yellen J. Grafteori og dens anvendelser, 2006 , s. 232.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 295.
↑ Harari Frank. Graph Theory, 2003 , s. en.
↑ Gross JL, Yellen J. Handbook of graph theory, 2004 , s. 9.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. en.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 22-26.
↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 48-26.
↑ Basaker R., Saaty T. Finite Graphs and Networks, 1974 , del II. Grafteoretiske applikationer.
↑ Kamenetsky I. S., Marshak B. I., Sher Ya. A. Analyse af arkæologiske kilder: Possibilities of a formalized approach, 2013 .
↑ Shalyto A. A. Algoritmisering og programmering af logiske kontrolopgaver, 1998 .
↑ Nils J. Nilsson. Kunstig intelligens og en ny syntese, 1998 .
↑ Melikhov A. N. Oriented graphs and finite automata, 1971 .
↑ Lubentsova V. S. Matematiske modeller og metoder i logistik, 2008 .
↑ Evstigneev V. A. Anvendelse af grafteori i programmering, 1985 .
↑ Paniotto V. I. Struktur af interpersonelle relationer: metodologi og matematiske metoder til forskning, 1975 .
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriske hardwaremodeller og algoritmer i CAD, 1990 .
↑ Kormen T. H. et al. Algoritmer: konstruktion og analyse, 2009 .
↑ Teori om grafer og netværk i modellering af ATC-processer , 2009 .
↑ Majidov T. I., Baskin I. I., Antipin I. S., Varnek A. A. Introduction to chemoinformatics, 2013-2016 .
↑ Yablonsky G.S., Bykov V.I., Gorban A.N. Kinetiske modeller for katalytiske reaktioner, 1983 .
↑ Kemiske anvendelser af topologi og grafteori , 1987 .
↑ Deza M. M., Sikirich M. D. Geometry of chemical graphs: polycycles and bipolycycles, 2013 .
↑ Kemisk grafteori: introduktion og grundlæggende , 1991 .
↑ Fomin G.P. Matematiske metoder og modeller i kommerciel aktivitet, 2009 .
↑ 1 2 Gross JL, Yellen J. Grafteori og dens anvendelser, 2006 .

Litteratur

Akimov O. E. Diskret matematik: logik, grupper, grafer. 2. udg., tilf. M.: Grundlæggende videnslaboratorium, 2003. 376 s.: ill. ISBN 5-93208-025-6 .
Alon N., Spencer J. Probabilistisk metode / Pr. 2. engelsk udg. M.: BINOM. Videnlaboratoriet, 2013. 320 s., ill. ISBN 978-5-9963-1316-7 .
Basaker R., Saati T. Finite grafer og netværk / Per. fra engelsk af V. N. Burkov, S. E. Lovetsky, V. B. Sokolov. Under redaktion af A. I. Teiman. M.: Nauka, 1974. 366 s., ill.
Berge K. Teori om grafer og dens anvendelser / Pr. fra fransk af A. A. Zykov. Moscow: Publishing House of Foreign Literature, 1962. 319 s., ill.
Vilenkin N. Ya., Shibasov L. P., Shibasova Z. F. Bag siderne i en lærebog i matematik. M.: Oplysning, 1996. 320 s., ill. ISBN 5-09-006575-6 .
Goodman S., Hidetniemi S. Introduktion til udvikling og analyse af algoritmer. M.: Mir, 1981. 366 s., ill.
Deza M. M., Sikirich M. D. Geometri af kemiske grafer: polycykler og bipolycykler. M.—Izhevsk: Publishing House of Institute of Computer Research, 2013. 384 s., ill. ISBN 978-5-4344-0130-2 .
Distel R. Grafteori / Pr. fra engelsk. Novosibirsk: Matematisk Instituts Publishing House, 2002. 225 s., ill. ISBN 5-86134-101-X.
Evstigneev V. A. Anvendelse af grafteori i programmering / Ed. A. P. Ershova. M.: Nauka, 1985. 352 s., ill.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Forelæsninger om grafteori / Ed. A. P. Ershova. M.: Nauka, 1990. 383 s., ill. ISBN 5-02-013992-0 .
Zykov A. A. Grundlæggende om grafteori. M.: Vuzovskaya kniga, 2004. 662 s.: ill. ISBN 5-9502-0057-8 .
Kamenetsky I. S., Marshak B. I., Sher Ya. A. Analyse af arkæologiske kilder: Muligheder for en formaliseret tilgang. Ed. 2. M.: IA RAN, 2013. 182 s.: ill. ISBN 978-5-94375-153-0 .
Karpov D. V. Grafteori. 2017 eller senere. 555 s., ill.
Kormen T. Kh., Leyzerson Ch. I., Rivest R. L., Stein K. Algoritmer: konstruktion og analyse. 2. udg. : Per. fra engelsk. Moskva: Williams Publishing House, 2009. 1290 s., ill. ISBN 978-5-8459-0857-5 (russisk). ISBN 0-07-013151-1 (engelsk).
Christofdes N. Grafteori. Algoritmisk tilgang. Om. fra engelsk. E. V. Vershkova og I. V. Konovaltseva. Under. udg. G. P. Gavrilova. M.: Mir, 1978. 432 s., ill.
Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriske hardwaremodeller og algoritmer i CAD. Moskva: Radio og kommunikation, 1990. 214 s., ill. ISBN 5-256-00748-3 .
Lubentsova V.S. Matematiske modeller og metoder i logistik / Ed. 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. Introduktion til kemoinformatik. Del 1-4. Kazan: Kazan University Press, 2013-2016.
Melikhov A. N. Orienterede grafer og endelige automater. M.: Nauka, 1971. 416 s., ill.
Med et slag. Tegning af figurer med én sammenhængende linje / Comp. Ja. I. Perelman. L .: Underholdende videnskabs hus, 1940. Fra 17 fig.
Ore O. Grafer og deres anvendelse / Pr. fra engelsk. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 s.: ill.
Ore O. Grafteori. 2. udg. stereotype. / Per. fra engelsk. I. N. Vrublevskaya. Ed. N. N. Vorobieva. M.: Nauka, 1980. 336 s.: ill.
Paniotto VI Struktur af interpersonelle relationer: metodologi og matematiske forskningsmetoder. Kiev: Naukova Dumka, 1975. 124 s., ill.
Perelman Ya. I. Levende matematik. Matematiske historier og gåder. Ed. 8, revideret. og yderligere / Ed. og med yderligere V. G. Boltyansky. M.: Nauka, 1967. 160 s. fra syg.
Referater fra møderne i konferencen for det kejserlige videnskabsakademi fra 1725 til 1803. Bind I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Petersborg: IAN trykkeri, 1897. 883 s.
Romanovsky IV Diskret analyse. 3. udg., revideret. og yderligere St. Petersborg: Nevskij-dialekt; BHV-Petersburg, 2003. 320 s.: ill. ISBN 5-7940-0114-3 . ISBN 5-94157-330-8 .
Tutt W. Grafteori / Pr. fra engelsk. G. P. Gavrilova. M.: Mir, 1988. 424 s., ill. ISBN 5-03-001001-7 .
Teorien om grafer og netværk i modellering af ATC-processer : Proc. godtgørelse / Komp. V. A. Karnaukhov. Ulyanovsk: UVAU GA (I), 2009. 63 s.
Wilson R. Introduktion til grafteori / Pr. fra engelsk. I. G. Nikitina. Ed. G. P. Gavrilova. M.: Mir, 1977. 207 s.: ill.
Fleishner G. Euler grafer og relaterede spørgsmål / Pr. fra engelsk. V. A. Evstigneeva, A. V. Kostochki og L. S. Melnikova. Ed. L. S. Melnikova. M.: Mir, 2002. 335 s.: ill. ISBN 5-03-003115-4 (russisk). ISBN 0-444-88395-9 . [Fleischner H. Eulerske grafer og beslægtede emner. S. 1, V. 1. Amsterdam: North-Holland, 1990.]
Fomin G.P. Matematiske metoder og modeller i kommerciel aktivitet: lærebog. 3. udg., revideret. og yderligere M.: Finans og statistik; INFRA-M, 2009. 637 s.: ill. ISBN 978-5-279-03353-9 (Finans og statistik). ISBN 978-5-16-003660-1 (INFRA-M).
Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler i grafteori: Lærebog / Per. med ham. E. E. Pereguda; Paul udg. S. V. Matsievsky. Kaliningrad: Forlaget for det russiske statsuniversitet. I. Kant, 2008. 204 s.: ill. ISBN 978-5-88874-880-0 .
Harary Frank. Grafteori / Pr. fra engelsk. V. P. Kozyreva. Ed. G. P. Gavrilova. 2. udgave. M.: Redaktionel URSS, 2003. 296 s.: ill. ISBN 5-354-00301-6 .
Harari F., Palmer E. Optælling af grafer / Pr. fra engelsk. G. P. Gavrilova. M.: Mir, 1977. 324 s.: ill.
Kemiske anvendelser af topologi og grafteori / Pr. fra engelsk. Ed. R. Konge. M.: Mir, 1987. 560 s.: ill.
Shalyto A. A. Algoritmisering og programmering af logiske kontrolproblemer. Sankt Petersborg: SPbGU ITMO, 1998. 56 s., ill.
Yablonsky GS, Bykov VI, Gorban' AN Kinetiske modeller af katalytiske reaktioner. Novosibirsk: Nauka, 1983. 253 s.: ill. ISBN 5-354-00301-6 .
Bondy JA, Murty USR Grafteori. 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.
Kemisk grafteori: introduktion og grundlæggende / redigeret af D. Bonchev og D. Rouvray. New York: Abacus Press, 1991. ISBN 0-85626-454-7 .
M. Camille Jordan. Sur les assemblages de lignes // J. Reine Angew. Matematik. 1869 Bd. 70. S. 185-190.
Reinhard Diestel. grafteori. GTM 173, 5. udgave 2016/17. Springer-Verlag, Heidelberg. Kandidattekster i matematik, bind 173. ISBN 978-3-662-53621-6 .
Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. S. 128-140.
Gross JL, Yellen J. Grafteori og dens anvendelser. anden version. Boca Raton–London–New York: Chapman & Hall/CRC, 2006.
Gross JL, Yellen J. Håndbog i grafteori. CRC Press , 2004. ISBN 978-1-58488-090-5 . S. 35.
Frank Harary . Biografisk skitse på ACM SIGACTs hjemmeside , 4. januar 2005.
Denes Konig. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.
Denes Konig. Teori om endelige og uendelige grafer. Boston: Birkhauser, 1990.
Nils J. Nilsson. Kunstig intelligens og en ny syntese. San Francisco, Californien: Morgan Kaufmann Publishes, Inc., 1998. 535 s. ISBN 1-55860-467-7 (klud). ISBN 1-55860-535-5 (papir).
JJ Sylvester (7. februar 1878) "Chemistry and algebra," Nature , 17 :284 . doi : 10.1038/017284a0 .

Links

Kirsanov M.N. Grafer i ahorn. Moskva: Fizmatlit , 2007. 168 s. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
Sergei Melnikov. Sim og Krem under "elektronmikroskopet" // Videnskab og liv . - 1996. - Udgave. 3 . - S. 144-145 . (Russisk)Artiklen omhandler spillet på Sim-grafen, opfundet af Gustav Simmons.
WikiGrapp - forklarende ordbog over grafteori
Algoritmer og korte beskrivelser af C++-programmer
Diskret matematik, algoritmer, applets, grafvisualisering
Intelligent Graph Visualizer (automatisk placering på flyet, finde den korteste vej, finde centrum osv.)
Software til grafteori
Visual Graph : et program, der giver brugeren en bred vifte af værktøjer og metoder til at visualisere og søge efter information i grafer

Ordbøger og encyklopædier

I bibliografiske kataloger
BNF : 119384413 GND : 4113782-6 J9U : 987007538432705171 LCCN : sh85056471 NDL : 00562641 NKC : ph126555

Grene af matematik

Portal "Science"

Grundlaget for matematik mængdeteori matematisk logik logikkens algebra

Talteori ( aritmetik )

Algebra
Elementær algebra	Ligningsløsning
Lineær algebra	Vektorregning matricer Tensorregning Multilineær algebra
Generel algebra	Kommutativ algebra Repræsentationsteori Differentiel algebra Homologisk algebra Universal Algebra Kategori teori

Analyse
Klassisk analyse	Differentialregning Integralregning
Funktionsteori	Harmonisk analyse Kvaternion Analyse Kompleks analyse måle teori Teori om funktioner af en reel variabel funktionel analyse Variationsberegning
Differential- og integralligninger	Dynamiske systemer og ergodisk teori Differentialligninger almindelig i partielle derivater Integralligninger
Vektoranalyse Global Analyse Katastrofe teori Tilpasset analyse Glat infinitesimal analyse

Geometri og topologi
Geometri	Algebraisk geometri Analytisk geometri Euklidisk geometri Ikke-euklidisk geometri Planimetri Stereometri
Topologi	Generel topologi Algebraisk topologi Differentialgeometri og topologi

Diskret matematik
Kombinatorik grafteori

Anvendt matematik
Matematisk fysik Matematisk kemi matematisk biologi Matematik statistik Matematisk modellering Teori om algoritmer Numeriske metoder matematisk økonomi finansiel matematik Sandsynlighedsteori Operationsforskning Spilteori

Portal "Matematik"
Kategori "Matematik"

Algoritmer på grafer
Søg efter sæler	Bron-Kerbosh algoritme Kosarayu's algoritme Malgrange algoritme Tarjans algoritme Demucrons algoritme Tilnærmet algoritme til at finde p-medianer Problemet med den længste vej Topologisk slags Hængsel (grafteori) Kargers algoritme (minimumssnit)
Flowmaksimering	Dinits algoritme Malhotra-Kumara-Maheshwari-algoritme Preflow Push Algoritme Ford-Fulkerson algoritme Edmonds-Karp algoritme transportnetværk
Matchende	Blomsterkomprimeringsalgoritme Hopcroft-Karp algoritme FKT algoritme
Kommunikationsgrafer	Havel-Hakimi algoritme (grafisk sekvens) Grafredigeringsafstand Problemet med at finde en isomorf subgraf
Andet	Algoritme for artikulationstræ (henter marginalisering) Cuthill-Mackey-algoritme (reduktion af båndbredde) Iterativ komprimering (ideen om rekursion) Skabelon:Søgealgoritmer på grafer

Algoritmer til grafsøgning
Uoplyste metoder	Tovejssøgning Strålesøgning Leksikografisk bredde første søgning Bredde først søgning Søg efter omkostningskriterium Dybde første søgning Backtracking søgning Søg ved at klatre til toppen Dybdebegrænset søgning Dybde-første søgning med iterativ uddybning
Informerede metoder	Alfa beta klipning Gren og bundet metode Søg efter første bedste match EN* B* D* At finde et overgangspunkt IDA* Rekursiv søgning på det første bedste match SMA*
Genveje	Bølgealgoritme Bellman-Ford algoritme Dijkstras algoritme Johnsons algoritme Levits algoritme Floyd-Warshall algoritme Kantsøgning
Minimumspændende træ	Boruvkas algoritme Prims algoritme Kruskals algoritme
Andet	British Museum Algoritme Edmonds algoritme Trækøring Nærmeste nabo-algoritme i problemet med rejsende sælger

Grafteori

Tidlig brug og opdagelser af grafer

Første brug af grafdiagrammet i videnskaben

Den første brug og "opdagelse" af grafteori

Den anden "opdagelse" af grafer

Den tredje "opdagelse" af grafer

Den fjerde "opdagelse" af grafer

Den femte "opdagelse" af grafer

Oprindelsen af ​​ordet "tælle"

Begyndelsen af ​​den systematiske brug af ordet "graf" og diagrammer af grafer

Grafteoriens historie

Positionsgeometri

Königsberg-broproblemet

Firefarvesætningen

Pontryagin-Kuratovsky-sætningen

Store legendariske udgaver

Beskrivelse af tidlig grafteori

Repræsentationsproblemer i grafteori

Problemer med terminologi

Problemer med graftegning

Litteraturproblemer

Klassifikation af grafteori

Grundlæggende vilkår for grafteori

Grafer ( engelske grafer )

Typer af grafer _

Stier forbindelse rediger _

Træer ( engelske træer )

Den aktuelle tilstand af grafteori

Matching, covering and packing ( engelsk matching, covering and packing )

Forbindelse _ _ _

Planar graphs ( engelske planar graphs )

Farvelægning ( engelsk farvelægning )

Flows ( engelske flows )

Ekstremal grafteori redigér _

Uendelige grafer _ _

Ramsey grafer [ rediger

Hamilton cykler _ _

Random graphs ( engelske random graphs )

Mindreårige, træer og brønd- -orden rediger

Noget algebra redigér _

Anvendelser af grafteori

Nogle problemer i grafteori

Klassifikationer af anvendelser af grafteori

Nogle anvendelser af grafteori

Nogle grafteoretiske algoritmer

Se også

Noter

Litteratur

Links

Oprindelsen af ordet "tælle"

Begyndelsen af den systematiske brug af ordet "graf" og diagrammer af grafer