2012-07-26 kl 10:21
 |
Alekseev V.V., Gavrilov G.P., Sapozhenko A.A. (red.) Graph Theory. Täckningar, läggning, turneringar. Samling översättningar - M.: Mir, 1974.- 224 sid. |
Innehåll
Förord
Lista över symboler
KAPITEL 1. Metoder för att representera grafer
1.1. Allmän representation av godtyckliga grafer
1.2. Definiera grafer med matriser
1.3. Binär representation av grafer
1.4. Binära relationer för grafer
1.5. Ange en graf som en formell kvadratisk form
1.6. Analytisk representation av grafer
KAPITEL 2. Problem med optimal grafrepresentation
2.1. Representera grafer med hjälp av datastrukturer
2.2. Träd representation
2.3. Uppskattning av antalet operationer av algoritmer
2.4. Om den optimala kodningen av aritmetiska grafer
KAPITEL 3. Element i teorin om komplexitet hos algoritmer för problem på grafer
3.1. Grundläggande koncept
3.2. Klasserna P och NP
3.3. Polynom reducerbarhet och JVP-kompletta problem
3.4. Bevis på resultat på .VP-fullständighet
3.5. Tillämpning av WP-fullständighetsteori för problemanalys
KAPITEL 4. Funktion på vanliga grafer
4.1. Operationer på hörn till kanter
KAPITEL 5. Grafåterställning
5.1. Isomorfi
5.2, Invarianter
5.3. Problem med isomorfism
5.4. Återhämtningsproblem. Existens och unikhet
5.5. Ulam gissning
5.6. Algoritm för att återställa grafer från en genomförbar uppsättning
5.7. Existens och unikhet teorem
5.8. Minimala uppsättningar av subgrafer
Slutsats
Bibliografi
2012-07-26 kl 10:35
 |
Donets G.A., Shor N.3. Algebraisk syn på problemet med färgläggning av plana grafer - K.: Naukova Dumka, 1982. - 144 sid. |
Innehåll
De viktigaste stadierna för att bevisa den fyrfärgade gissningen.
Historisk referens.
Bevis från Tait, Kempe och Heawood.
Reducerbarhet av grafer och konfigurationer.
Fyra typer av konfigurationsreducerbarhet.
Neutraliseringsmetoden och dess utveckling.
Heawoods ekvationer.
Fyrfärgsproblemet och en grupp ersättningar.
På ekvationssystem modulo.
Algebraiska ojämlikheter relaterade till färgning av triangulära grafer med tre färger.
Om algoritmer för färgläggning av plana grafer med fyra färger.
Kombinatorik av matchningar och färgning av grafer.
Pfaffiska och perfekta grafmatchningar.
Vid räkning av antalet matchningar av en graf dubbel till en maximal plan graf.
Beräkning av koefficienter för vissa polynom modulo 2 och modulo 3 med hjälp av formler relaterade till att räkna antalet matchningar.
Analys av ett ekvationssystem modulo.
Urvalsproblem och graffärgning.
På en algoritm för färgläggning av plana grafer.
Härledning av ekvationssystemet. Ett speciellt fall.
Några villkor för lösbarheten av ett kanoniskt system.
Allmänt villkor för systemets lösbarhet.
Studie av ett ekvationssystem för det allmänna fallet.
Förutsättningar för att lösa det allmänna kanoniska systemet och frågor om att konstruera en färgalgoritm.
2012-07-26 kl 10:44
Innehåll
Från författaren 4
Inledning 5
KAPITEL 1. IDENTIFIERING 12
§1.1. Vanliga räkningar 12
§ 1.2. Isomorfism 15
§ 1.3. Invarianter 21
§ 1.4. Beräkning av invarianter 31
§ 1.5. Isomorfism problem 41
§ 1.6. Vissa tillämpningar av densitet och löshet 47
§ 1.7. Algoritmer för densitet, löshet och isomorfism 56
§ 1.8. Uppskattningar av densitet och löshet. Greve av Turan 65
§ 1.9. Optimala och kritiska grafer 73
§ 1.10. Återställningsproblem 80
KAPITEL 2. ANSLUTNING 96
§ 2.1. Rutter 96
§2.2. Block 108
§2.3. Träd 118
§ 2.4. Matchningar och tvådelade grafer 125
§ 2.5.1 sammankopplade grafer 137
§ 2.6. Viktade grafer och mått 149
§ 2.7. Multigrafer 162
§ 2.8. Euler-kedjor och cyklar 171
§ 2.9. Ribb målarbok 176
KAPITEL 3. CYKLOMATIK 188
§ 3.1. Ramar och sektioner 188
§ 3.2. Utrymme av sugrafer 197
§ 3.3. Matriser över incidenter, nedskärningar och cykler 202
§ 3.4. Grafer med givna snitt och cykler 211
§ 3.5. Topologiska grafer 225
§ 3.6. Planaritet 234
§ 3.7. Stridskorsningar 252
§ 3.8. Hadwigers gissning 262
§ 3.9. Platt triangulering målarbok 275
§ 3.10. Perfekta grafer 291
KAPITEL 4. ORIENTERING 305
§ 4.1. Finita grafer av allmän form 305
§ 4.2. Tillgänglighet 314
§4.3. Kärnor 332
§ 4.4. Orienterbarhet 342
§ 4.5. Transitabilitet 350
Tillägg. Booleska metoder i grafteori 363
Slutsats 379
2012-07-26 kl 10:55
 |
Kalmykov G.I. Trädklassificering av märkta grafer. - M.: FIZMATLIT, 2003. - 192 sid. - ISBN 5-9221-0333-4. |
Innehåll
Förord för teoretiska fysiker
Förord av författaren
Kapitel I Klassificering av märkta grafer
§1. Halvordning av rotade märkta träd. Pseudo-skelett och trådram av en ansluten märkt graf
§ 2. Maximal epigrafi av ett träd. Trädklassificering av anslutna märkta grafer
§ 3. Trädklassificering av märkta träd och andra klassificeringar av märkta träd
§ 4. Maximal isomorfism av rotade märkta träd
§ 5. Klasser av maximalt isomorfa rotade märkta träd
§ 6. Klassificering av alla (n+1)-vertexmärkta grafer
§ 7. Räkning av antalet anslutna märkta grafer med jämna och udda antal kanter
Kapitel II Representation i trädform av koefficienter för effektexpansion av termodynamiska storheter
§ 1. Trädrepresentation av Ursellfunktionen
§ 2. Trädsummor för expansionskoefficienter för tryck och täthet i aktivitetsgrader
§ 3. Representation i trädform av expansionskoefficienter i aktivitetsgrader för trunkerade fördelningsfunktioner
Kapitel III Några problem med övergången till den termodynamiska gränsen
Kapitel IV Expansioner till aktivitetsgrader i den termodynamiska gränsen
§ 1. Expansion av tryck och densitet
§ 2. Utbyggnader av distributionsfunktioner
§ 3. Uppskattning av konvergensradien för expansioner av tryck och täthet i aktivitetsgrader vid en icke-negativ potential
Kapitel V Analytiska fortsättningar av virial expansion och expansioner av aktivitetsgrader
Kapitel VI Om expansioner av densitet och specifik volym efter aktivitetsgrader
Kapitel VII Representation av virialkoefficienter i form av polynom i trädsummor
§ 1. Fallet med trädsummor som representerar koefficienterna `b_n(beta)`
§ 2. Fallet med trädsummor som representerar koefficienterna `a_n(beta)`
Kapitel VIII Problemet med asymptotisk katastrof och dess lösning med trädsummemetoden
§ 1. Verksamhetsutbyggnader
§ 2. Viriella koefficienter
Ansökan. Beräkning av integraler från exempel IV.2
Bibliografi
Beteckningar
Sakregister
2012-07-26 kl 11:48
 |
Cameron P., van Lint J. Grafteori, kodningsteori och blockdiagram - M.: Nauka, 1980, 140 pp. |
Innehåll
Översättarens förord 4
Inledning 5
1. Kort introduktion till kretsteori 6
2. Starkt regelbundna grafer 17
3. Kvasi-symmetriska kretsar 24
4. Starkt regelbundna grafer utan trianglar 29
5. Kretspolariteter 37
6. Grafexpansion 41
7. Koder 47
8. Cykliska sneakers 54
9. Tröskelavkodning 59
10. Reed-Muller koder 62
11. Självortogonala koder och scheman 67
12. Kvadratiska restkoder 73
13. Symmetriska koder över GFC) 83
14. Nästan perfekta binära koder och enhetligt packade koder 88
15. Associativa system 97
Litteratur 109
Tillägg från andra upplagan 114
Mer läsning 134
Ämnesregister 137
2012-07-26 kl 11:59
 |
Christofides N. Grafteori. Algoritmiskt tillvägagångssätt. Per. från engelska - M.:Mir, 1978, 432 sid. |
Innehåll
Förord
Kapitel 1 Inledning
1. Grafer. Definition
2. Stigar och rutter
3. Slingor, orienterade slingor och slingor
4. Vertex grader
5. Subgrafer
6. Typer av grafer
7. Starkt sammankopplade grafer och grafkomponenter
8. Matrisrepresentationer
9. Uppgifter
10. Referenser
Kapitel 2: Nåbarhet och anslutning
1. Introduktion
2. Matris av uppnådda och motprestationer
3. Hitta starka komponenter
4. Baser
5. Problem i samband med begränsad tillgänglighet
6. Mål
7. Referenser
Kapitel 3. Oberoende och dominerande uppsättningar.
Täckningsset problem
1. Introduktion
2. Oberoende uppsättningar
3. Dominanta set
4. Minsta täckningsproblem
5. Tillämpningar av täckningsproblemet
6. Mål
7. Referenser
Kapitel 4. Målarbok
1. Introduktion
2. Några satser och uppskattningar relaterade till kromatiska tal
3. Noggranna färgalgoritmer
4. Ungefärliga färgalgoritmer
5. Generaliseringar och tillämpningar
6. Mål
7. Referenser
Kapitel 5. Placering av centra
1. Introduktion
2. Divisioner
3. Centrum och radie
4. Absolut centrum
5. Algoritmer för att hitta absoluta centra
6. Flera centra (p-center)
7. Absoluta p-centra
8. Algoritm för att hitta absoluta p-centra
9. Uppgifter
10. Referenser
Kapitel 6. Placera medianer i en graf
1. Introduktion
2. Median för grafen
3. Multipel median (p-medianer) av grafen
4. Generaliserad p-median för en graf
5. Metoder för att lösa p-medianproblemet
6. Mål
7. Referenser
Kapitel 7. Träd
1. Introduktion
2. Konstruktion av alla spännande träd i grafen
3. Kortaste spännträdet (SST) i en graf
4. Steinerproblem
5. Mål
6. Referenser
Kapitel 8. Kortaste vägarna
1. Introduktion
2. Den kortaste vägen mellan två givna hörn s och t
3. Kortaste vägarna mellan alla par av hörn
4. Upptäcka negativa viktcykler
5. Hitta K kortaste vägarna mellan två givna hörn
6. Kortaste vägen mellan två givna hörn i en riktad acyklisk graf
7. Problem nära problemet med kortaste vägen
8. Uppgifter
9. Referenser
Kapitel 9. Cykler, nedskärningar och Euler-problemet
1. Introduktion
2. Cyklomatiskt tal och fundamentala cykler
3.. Nedskärningar
4. Matriser av cykler och nedskärningar
5. Euler-cykler och det kinesiska brevbärarproblemet
6. Mål
7. Referenser
Kapitel 10. Hamiltonska cyklar, kedjor och problemet med resande säljare
1. Introduktion
DEL I
2. Hamiltonian cykler i en graf
3. Jämförelse av metoder för att söka efter Hamiltonska cykler
4. Enkelt schemaläggningsproblem
DEL II
5. Resande säljare problem
6. Problem med resande säljare och problem med kortaste spann
7. Resande säljarproblem och uppdragsproblem
8. Uppgifter
9. Referenser
10. Ansökan
Kapitel 11. Strömmar i nätverk
1. Introduktion
2. Grundläggande problem med maximalt flöde (från s till t)
3. Enkla versioner av problemet med maximalt flöde (från s till t)
4. Maximalt flöde mellan varje par av hörn
5. Minsta kostnadsflöde från s till t
6. Flödar i grafer med vinster
7. Mål
8. Referenser
Kapitel 12. Matchnings-, transportproblem och uppdragsproblem
1. Introduktion
2. Största matchningar
3. Maximala matchningar
4. Tilldelningsproblem
5. Allmänt problem med att konstruera en spännande subgraf med föreskrivna grader
6. Täckningsproblem
7. Mål
8. Referenser
Bilaga 1. Sökmetoder med hjälp av beslutsträd
1. Sökprincip med hjälp av ett beslutsträd
2. Några exempel på förgrening
3. Typer av sökning med hjälp av beslutsträd
4. Tillämpa gränser
5. Förgreningsfunktioner
Sakregister
2012-07-26 kl 12:25
 |
Mainika E. Optimeringsalgoritmer på nätverk och grafer. Per. från engelska - M.:Mir, 1981, 328 sid. |
Innehåll
Översättningsredaktörens förord
Förord
Glana 1. Introduktion till graf- och nätverksteori
1.1. Inledande anmärkningar
1.2. Några begrepp och definitioner
1.3. Linjär programmering
Övningar
Litteratur
Kapitel 2. Algoritmer för att konstruera träd
2.1. Algoritmer för att konstruera spännande träd
2.2. Algoritm för att bygga en maximalt riktad skog
Övningar
Litteratur
Kapitel 3. Pathfinding Algoritmer
3.1. Algoritm för att hitta den kortaste vägen
3.2. Algoritmer för att hitta alla kortaste vägar
3.3. Algoritm för att söka efter kortaste vägarna
3.4. Att hitta andra optimala vägar
Övningar
Litteratur
Kapitel 4. Strömmande algoritmer
4.1. Introduktion
4.2. Algoritm för att hitta det maximala flödet
4.3. Algoritm för att hitta det lägsta kostnadsflödet
4.4. Defekt algoritm
4.5. Dynamisk flödessökningsalgoritm
4.6. Strömmar med booster
Övningar
Litteratur
Kapitel 5. Algoritmer för sökning av ånga och beläggning
5.1. Introduktion
5.2. Algoritm för att lösa problemet med ånggenerator med maximal effekt
5.3 Algoritm för att välja en match med maximal vikt
5.4. Algoritm för att konstruera täckning med minimal vikt
Övningar
Litteratur
Kapitel 6. Brevbärarens problem
6.1. Introduktion
6.2. Postman problem för en oriktad graf
0,3. Postman problem för riktad graf
6.4. Postman problem för blandad graf
Övningar
Litteratur
Kapitel 7. Problem med resande säljare
7.1. Formulering och några egenskaper hos lösningen på resandeförsäljarproblemet
7.2. Förutsättningar för existensen av en Hamiltonsk kontur
7.3. Nedre gränser
7.4. Metoder för att lösa det resande säljarproblemet
Övningar
Litteratur
Kapitel 8. Placeringsproblem
8.1. Introduktion
8.2. Centrera sökuppgifter
8.3. Mediansökproblem
8.4. Generaliseringar
Övningar
Litteratur
Kapitel 9. Nätverk
9.1. Kritisk sökvägsmetod (CPM)
9.2- Fastställande av varaktigheten för "operationer" utifrån villkoret att säkerställa lägsta kostnad
9.3. Generaliserade nätverksgrafer
Övningar
Litteratur
Sakregister
2012-07-26 kl 12:49
 |
Melikhov A.N., Bershtein L.S., Kureichik V.M. Tillämpning av grafer för design av diskreta enheter - M.: Nauka, 1974, 304 sid. |
Innehåll
Förord
Introduktion
Kapitel I. Grundläggande definitioner och begrepp inom grafteori
§ 1. Metoder för att specificera, huvudtyper och delar av grafer
§ 2. Anslutning av grafer
§ 3. Grundtal av grafer
§ 4. Metrik för grafer
§ 5. Plana grafer
§ 6. Isomorfism och isomorf inbäddning av grafer
§ 7. Övergång från modulära scheman till grafer
§ 8. Gren och bunden metod
Kapitel II. Layout av diskreta enhetskretselement
§ 1. Täcker funktionsscheman med ett modulkopplingsschema
§ 2. Redogörelse för problemet med att skära en kretsgraf
§ 3. Sekventiella skäralgoritmer
§ 4. Iterativa skäralgoritmer
§ 5. Klippning av kretsdiagrammet i ett godtyckligt antal delar
Kapitel III. Placera kretsdiagrammet på planet
§ 1. Redogörelse för modulplaceringsproblemet
§ 2. Sekventiella placeringsalgoritmer
§ 3. Iterativa placeringsalgoritmer
§ 4. Algoritm för att placera element med hjälp av förgrenings- och bindningsmetoden
Kapitel IV. Minimera in-Circuit-korsningar av diskreta enheter
§ 1. Om antalet skärningspunkter av kanter av kompletta och kubiska grafer
§ 2. Räkning av skärningspunkterna mellan kanter av godtyckliga grafer för en fast placering av hörn på planet
§ 3. Räkning av skärningspunkterna för kanter på godtyckliga grafer när de mappas till ett rektangulärt gitter
§ 4. Minimera antalet skärningar av kretsdiagramkanter
Kapitel V. Några frågor om planaritet hos kretsdiagram
§ 1. Metoder för att bestämma en grafs planaritet
§ 2. På planaritetstalet för en graf
§ 3. Algoritm för att bestämma planariteten för en graf med en Hamiltonsk cykel
§ 4. Dela upp en graf i plana subgrafer
§ 5. Dela upp en graf i plana sugrafer med internt stabila uppsättningar
Kapitel VI. Spårning av diskret enhetskretsanslutningar
§ 1. Redogörelse för spårningsproblemet
§ 2. Strålspårningsalgoritmer
§ 3. Spårningsalgoritmer med konstruktion av en skog av spännande träd
§ 4. Spåra förbindelser i flera lager
Bibliografi
Namnindex
Sakregister
2012-07-26 kl 12:53
 |
Melnikov O.I. Grafteori i underhållande problem. Utg. 3, rev. och ytterligare 2009. 232 sid. |
Innehåll
Inledning 5
Villkorlig fördelning av uppgifter efter grader av komplexitet 7
Uppgifter. Problemlösningar 8
Begagnad litteratur 226
Bilaga 227
2012-07-26 kl 12:57
 |
Ore O. Grafer och deras tillämpning: Transl. från engelska 1965. 176 sid. |
Innehåll
Från redaktören
Introduktion
KAPITEL I. Vad är en graf?
1. Sport
2. Nullgraf och komplett graf
3. Isomorfa grafer
4. Plana grafer
5. Ett problem om plana grafer
6. Antal kanter på grafen
KAPITEL II. Anslutna grafer
1. Komponenter
2. Problem kring Königsbergsbroarna
3. Euler-grafer
4. Att hitta rätt väg
5. Hamiltonska linjer
6. Pussel och grafer
KAPITEL III. Träd
1. Träd och skogar
2. Cyklar och träd
3. Problemet med att koppla samman städer
4. Gator och torg
KAPITEL IV. Motsvarande
1. Problem med tillsättning till befattningar
2. Annan formulering
3. Cirkulär korrespondenser
KAPITEL V. Riktade grafer
1. Sport igen
2. Enkelriktad trafik
3. Grader av hörn
4. Genealogiska grafer
KAPITEL VI. Spel och pussel
1. Pussel och riktade grafer
2. Spelteori
3. Sportskrivarparadoxen
KAPITEL VII. Relation
1. Relationer och grafer
2. Särskilda villkor
3. Ekvivalensrelationer
4. Delbeställning
KAPITEL VIII. Plana grafer
1. Villkor för plana grafer
2. Eulers formel
3. Några relationer för grafer. Dubbla grafer
4. Vanliga polyedrar
5. Mosaiker
KAPITEL IX, Målarkartor
1. Fyrfärgsproblemet
2. Femfärgssats
Träningslösningar
Litteratur
Ordlista över grundläggande termer som används i boken
2012-07-26 kl 12:58
 |
Ore O. Graph theory - 2:a uppl. - M.: Nauka, Huvudredaktionen för fysisk och matematisk litteratur, 1980, 336 sid. |
Innehåll
Från redaktören för den ryska översättningen 8
Förord 9
Kapitel 1. GRUNDBEgrepp 11
1.1. Definitioner 11
1.2. Lokala grader 16
1.3. Delar och understycken 22
1.4. Binära relationer 25
1.5. Adjacency- och incidensmatriser 30
Kapitel 2. ANSLUTNING 34
2.1. Rutter, kretsar och enkla kretsar 34
2.2. Anslutna komponenter 36
2.3. En-till-en-mappningar 39
2.4. Avstånd 41
2.5. Längd 45
2.6. Matriser och kretsar. Produkt av grafer 43
2.7. Pussel 51
Kapitel 3. KEDJEPROBLEM 53
3.1. Eulerkedjor 53
3.2. Eulerkedjor i oändliga grafer 58
3.3. Om labyrinter 64
3.4. Hamiltonian cyklar 70
Kapitel 4. TRÄD 77
4.1. Trädens egenskaper 77
4.2. Centrum i träd 82
4.3. Cyklisk rang (diplomatiskt nummer) 87
4.4. Unika mappningar 88
4.5. Fritt ritade grafer 96
Kapitel 5. ARK OCH BLOCK 101
5.1. Förbindande kanter och hörn 101
5.2. Blad 105
5.3. Homomorfa bilder av graf 107
5.4. Block 109
5.5. Maximala enkla cykler 114
Kapitel 6. VALAXIOM 117
6.1. Slutför beställning 117
6.2. Maximala principer 120
6.3. Kedjesummerbara egenskaper 123
6.4. Maximal uteslutning räknas till 126
6.5. Max antal träd 128
6.6. Samband mellan maximala grafer 130
Kapitel 7. MATCHNINGSSATSER 134
7.1. Tvådelade grafer 134
7.2. Brister 138
7.3. Matchande satser 141
7.4. Inbördes matchningar 145
7.5. Matchningar i privata grafer 150
7.6. Tvådelade grafer med positiva 155
7.7. Applikationer till matriser 160
7.8. Alternerande kedjor och max 167
7.9. Separera set 176
7.10. Ledmatchningar 178
Kapitel 8. orienterade grafer 184
8.1. Inklusionsrelation och nåbar 184
8.2. Homomorfism sats 189
8.3. Transitiva grafer och fördjupningar i ordningsrelationer 191
8.4. Grundläggande grafer 194
8.5. Alternerande kedjor 198
8.6. Sugrafer av första graden i kolumn 202
Kapitel 9. ACYKLISKA GRAFIKER 206
9.1. Grundläggande grafer 206
9.2. Kedjedeformationer 208
9.3. Uppspelningsdiagram 211
Kapitel 10. DELORDNING 216
10.1. Grafer över delbeställningar 216
10.2. Representationer i form av summor av beställda set 217
10.3. Strukturer och strukturell verksamhet. Avslutande relationer 223
10.4. Mått i delbeställning 227
Kapitel 11. BINÄRA RELATIONER OCH GALOAS KORRESPONDENS 232
11.1. Galois-korrespondenser 232
11.2. Galois-anslutningar för binära relationer 237
11.3. Alternerande produktrelationer 242
11.4. Ferrers relationer 245
Kapitel 12. LÄNKANDE KEDJOR 248
12.1. Sats om sekantkedjor 248
12.2. Vertex split 252
12.3. Revbensseparering 254
12.4. Underskott 256
Kapitel 13. DOMINANTA SET TÄCKAR 260
UPPSÄTTNINGAR OCH OBEROENDE UPPSÄTTNINGAR
13.1. Dominant set 260
13.2. Täckningsset och överdrag 262
13.3. Oberoende set 266
13.4. Turans sats 270
13.5. Ramseys sats 273
13.6. Ett problem från informationsteorin
Kapitel 14. KROMATISKA GRAFIKER
14.1. Kromatiskt nummer
14.2. Summor av kromatiska grafer
14.3. Kritiska grafer
14.4. Färga polynom
Kapitel 15. GRUPPER OCH GRAFIKER
15.1. Automorfism grupper
15.2. Färgade Cayley-grafer för grupper
15.3. Grafer med givna grupper
15.4. Kantkartläggningar
Litteratur
Namnindex
Sakregister
2012-07-26 kl 12:58
Innehåll
Översättningsredaktörens förord
Förord
Del I. Grafteori
1. Grundläggande begrepp
1.1. Grundläggande definitioner
1.2. Subgrafer och komplement
1.3. Rutter, kedjor, stigar och slingor
1.4. Anslutningsmöjligheter och grafkomponenter
1.5. Operationer på grafer
1.6. Speciella grafer.
1.7. Artikulationspunkter och separerbara grafer
1.8. Isomorfism och 2-isomorfism
1.9 Anteckningar angående litteratur
Övningar
2. Trädkapning set och cykler
2.1. Träd, skelett och kodträd
2.2. k-träd, spännande k-träd, skogar
2.3. Rang och cyklomatiskt nummer
2.4. Grundläggande cykler
2.5. Klippset
2.6. Snitt
2.7. Grundläggande skärset
2.8. Skelett, cyklar och skärset
2.9. Anteckningar angående litteraturen
Övningar
3. Euler och Hamiltonska grafer
3.1. Euler-grafer
3.2. Hamiltonska grafer
3.3. Anteckningar angående litteraturen
Övningar
4. Grafer och vektorrum
4.1. Grupper och fält
4.2. Vektor utrymmen
4.3. Vektor utrymme graf
4.4. Dimension av delrum av cykler och skärningar
4.5. Förhållandet mellan delrum av cykler och nedskärningar
4.6. Ortogonalitet av delrum av cykler och snitt
4.7. Anteckningar angående litteraturen
Övningar
5. Riktade grafer
5.1. Grundläggande definitioner och begrepp
5.2. Grafer och relationer
5.3. Riktade och rotade träd
5.4. Riktade Euleriska grafer
5.5. Orienterade skelett och orienterade Euleriska kedjor
5.6. Riktade Hamiltonska grafer
5.7. Acykliska riktade grafer
5.8. Turneringar
5.9. Anteckningar angående litteraturen
Övningar
6. Grafmatriser
6.1. Incidentmatris
6.2. Klipp Matrix
6.3. Cyklomatisk matris
6.4. Ortogonalitetsrelation
6.5. Submatriser av snitt, incidenter och cykler matriser
6.6. Unimodulära matriser
6.7. Antal skelett
6.8. Antal spännande 2-träd
6.9. Antal riktade spännande träd i en riktad graf
6.10 Adjacency-matris
6.11. Earls Coates och Mason
6.12. Anteckningar angående litteraturen
Övningar
7. Planaritet och dualitet
7.1. Plenardiagram
7.2. Eulers formel
7.3. Kuratowskis teorem och andra karakteriseringar av planaritet
7.4. Dubbla grafer
7.5. Planaritet och dualitet
7.6. Anteckningar angående litteraturen
Övningar
8. Anknytning och matchningar
8.1. Connectivity eller vertex connectivity
8.2. Edge-anslutning
8.3. Grafer med givna grader
8.4. Mengers teorem
8.5. Motsvarande
8.6. Matchning i tvådelade grafer
8.7. Allmän grafmatchning
8.8. Anteckningar angående litteraturen
Övningar
9. Beläggningar och färger
9.1. Oberoende set och vertexbeläggningar
9.2. Ribböverdrag
9.3. Kantfärgning och kromatiskt index
9.4. Vertexfärgning och kromatiskt nummer
9.5. Kromatiska polynom
9.6. Fyrfärgsproblem
9.7. Anteckningar angående litteraturen
Övningar
10. Matroider
10.1. Grundläggande definitioner
10.2. Grundläggande egenskaper
10.3. Ekvivalenta system av axiom
10.4. Matroid dualitet och grafoider
10.5. Begränsning, förträngning och matroid minderåriga
10.6. Representabilitet av matroider
10.7. Binära matroider
10.8. Orienterbara matroider
10.9. Matroider och den "giriga" algoritmen
10.10. Anteckningar angående litteraturen
Övningar
Del II. Elektriska krets teori
11. Grafer och elektriska kretsar
11.1. Konvertering av konturer och sektioner
11.2. System av konturekvationer och sektionsekvationer
11.3. Metod med blandade variabler
11.4. Huvudpartition av grafen
11.5. Tillståndsekvationer
11.6. Icke-förstärkningsegenskap i resistiva kretsar
11.7. Anteckningar angående litteraturen
Övningar
12. Resistiva n-poliga kretsar
12.1. Introduktion
12.2. Y-matriser för en resistiv n-polskrets av rang n
12.3. Implementering av (n+1)-nodresistiva n-poliga kretsar (Söderbaum-metoden)
12.4. Implementering av en cyklomatisk matris och en tvärsnittsmatris
12.5. Implementering av (n+1)-nodresistiva n-poliga kretsar (Guillemins tillvägagångssätt)
12.6. Anteckningar angående litteraturen
Övningar
13. Kretsfunktion och kretskänslighet
13.1. Topologiska formler för RLC-kretsar utan inbördes induktans
13.2. Topologiska formler för allmänna linjära kretsar
13.3. Beräkning av kopplad krets och kretskänslighet
13.4. Anteckningar angående litteraturen
Övningar
Del III. Elektriska kretsteori
14. Grafanalysalgoritmer
14.1. Transitiv stängning
14.2. Transitiv orientering
14.3. Djup första sökning
14.4. Dubbelkopplad och starkt sammankopplad
14.5. Reducerbarhet för programgrafer
14.6. Dominatorer i programdiagrammet
14.7. Anteckningar angående litteraturen
Övningar
15. Optimeringsalgoritmer
15.1. Kortaste vägarna
15.2. Träd med minsta längd av viktade stigar
15.3. Optimala binära sökträd
15.4. Maximalt antal matchningar i en graf
15.5. Maximalt antal matchningar i en tvådelad graf
15.6. Perfekt matchning, optimalt uppdrag och schemaläggning
15.7. Flöden i transportnätet
15.8. Optimal förgrening
15.9. Anteckningar angående litteraturen
Övningar
Litteratur
Sakregister
2012-07-26 kl 12:59
 |
Tutt W. Grafteori. Per. från engelska - M.:Mir, 1988, 424 sid. |
2012-07-26 kl 12:59
Innehåll
Översättningsredaktörens förord
Förord
1. Introduktion
§ 1. Vad är en graf?
2. Definitioner och exempel
§ 2. Definitioner
§ 3. Exempel på grafer
§ 4. Grafförpackningar
3. Kretsar och cykler
§ 5. Nya definitioner
§ 6. Euler-grafer
§ 7. Hamiltonska grafer
§ 8. Oändliga grafer
4. Träd
§ 9. Trädens elementära egenskaper
§ 10. Uppräkning av träd
§ 11. Vissa tillämpningar av grafteori
5. Planaritet och dualitet
§ 12. Plenardiagram
§ 13. Eulers sats om plana grafer
§ 14. Grafer på andra ytor
§ 15. Dubbla grafer
§ 16. Whitney-dualitet
6. Färgläggande grafer
§ 17. Kromatiskt tal
§ 18. Två bevis
§ 19. Målarkort
§ 20. Kantfärgning
§ 21. Kromatiska polynom
7. Digrafer
§ 22. Definitioner
§ 23. Euler-digrafer och turneringar
§ 24. Markov-kedjor
8. Matchningar, bröllop och Mengers teorem
§ 25. Halls sats om bröllop
26 § Teori om transversaler
§ 27. Tillämpningar av Halls sats
§ 28. Mengers sats
§ 29. Flöden i nätverk
9. Matroid teori
§ 30. Introduktion till teorin om matroider
§ 31. Exempel på matroider
§ 32. Matroider och grafteori
§ 33. Matroider och teorin om transversaler
Efterord
Ansökan
Bibliografi
Sakregister
Ladda ner (djvu, 4 MB) libgen.info
Innehåll
Från översättningsredaktören 5
Förord 8
Kapitel I. Inledning 11
Kapitel II. Tre pelare i Eulerian grafteori 15
Lösa ett problem relaterat till positionsgeometri 16
Om möjligheten att kringgå ett linjärt komplex utan upprepningar och avbrott 33
Från "Analysis situs" av O. Veblen 38
Kapitel III. Grundläggande begrepp och preliminära resultat 39
111.1. Blandade grafer och deras huvuddelar 40
111,2. Vissa samband mellan grafer och (blandade) (di)grafer.
Subgrafer 45
111,3. Grafer som härrör från en given graf 50
111,4. Rutter, kedjor, stigar, cyklar, träd; anslutning 53
111,5. Kompatibilitet, cyklisk ordning av uppsättningen Ku och motsvarande
Eulerkedjor 72
111,6. Matchningar, 1-faktorer, 2-faktorer, 1-faktoreringar, 2-faktoreringar
tioner, tvådelade grafer 75
111,7. Inbäddning av grafer i ytor; isomorfismer 81
111,8. Färgning av plangrafer 89
111,9. Hamiltonian cyklar 92
III. 10. Incidens- och närliggande matriser, flöden och spänningar 97
III. 11. Algoritmer och deras komplexitet 100
III. 12. Avslutande kommentarer 102
Kapitel IV. Karakteriseringssatser och deras konsekvenser 104
IV.1. Räknar 104
IV.2. Digrafer 110
IV.3. Blandade grafer 113
IV.4. Övningar 119
Kapitel V. Några möjliga generaliseringar 121
V.I. Kedjeutbyggnader, ban-/cykelutbyggnader 121
V.2. Resultat om paritet 122
V.3. Dubbla passager 124
V.4. Gränsövergång: Grafdelningar 124
V.5. Övningar 126
Kapitel VI. Olika typer av Euler-kretsar 127
VI. 1. Euler-kedjor som undviker vissa övergångar 127
VI.2. Parvis kompatibla Euler-kedjor 155
VI.3. L-kedjor i plana grafer 183
VI.4. Övningar 266
Kapitel VII. Transformationer av Euler-kedjor 270
VII. 1. Transformation av godtyckliga Euler-kedjor i diagram 271
VII.2. Transformation av Euleriska kedjor av en speciell typ 276 Under senare år har ämnena för grafteorin blivit betydligt mer mångsidiga; antalet publikationer ökade kraftigt.
Den här boken skrevs av en av de framstående specialisterna inom diskret matematik. Trots den lilla volymen och sammanfattningen av presentationen täcker boken ganska fullt ut det aktuella läget för grafteorin. Det kommer säkerligen att vara användbart för studenter vid universitet och tekniska högskolor och kommer utan tvekan att vara av intresse för en bred krets av vetenskapsmän som är involverade i tillämpningar av diskret matematik.
Ladda ner (djvu, 6 MB) libgen.info
Innehåll
Förord
Introduktion
Kapitel 1. Upptäckt!
Problemet med Königsbergsbroarna
Elektriska kretsar
Kemiska isomerer
"Runt världen"
Fyrfärgshypotes
Grafteori på 1900-talet
Kapitel 2. Grafer
Typer av grafer
Rutter och anslutningar
Grader
Ramsey problem
Extrema grafer
Skärningsgrafer
Operationer på grafer
Övningar
Kapitel 3. Block
Ledpunkter, broar och block
Blockgrafer och artikulationspunktsgrafer
Övningar
Kapitel 4. Träd
Beskrivning av träd
Centers och centroider
Träd av block och artikulationspunkter
Oberoende cykler och samcyklar
Matroider
Övningar
Kapitel 5. Anslutningar. ,
Connectivity och edge connectivity
Grafiska versioner av Mengers teorem
Andra varianter av Mengers sats 70
Övningar 74
Kapitel 6. Partitioner 76
Övningar 81
Kapitel 7. Traverserande grafer 83
Euler-grafer 83
Hamiltonska grafer 85
Övningar 88
Kapitel 8. Kantdiagram 91
Vissa egenskaper hos kantgrafer 91
Karakterisering av kantgrafer 94
Speciella kantgrafer 99
Kantgrafer och genomgångar 101
Totala grafer 103
Övningar 104
Kapitel 9. Faktorisering 106
1-faktorisering 106
2-faktorisering 111
Träighet 113
Övningar 116
Kapitel 10. Beläggningar 117
Täckningar och självständighet 117
Kritiska hörn och kanter 120
Kustkärna 122
Övningar 124
Kapitel I. Planaritet 126
Plana och plana grafer. 126
Ytterplansgrafer 131
Pontryagins sats - Kuratovsky 133
Andra karakteriseringar av plana grafer 138
Genus, tjocklek, storlek, antal korsningar 141
Övningar 148
Kapitel 12. Målarbok 151
Kromatiskt nummer 152
Femfärgssats 155
Fyrfärgshypotes 156
Heawoods sats om färgläggning av kort 162
Unikt färgbara grafer 164
Kritiska grafer 167
Homomorphisms 169
Kromatiskt polynom 172
Övningar 175
Kapitel 13. Matriser 178
Adjacency-matris 178
Incident Matrix 180
Cykelmatris 183
Granskning av ytterligare egenskaper hos matroider 186
Övningar 187
Kapitel 14. Grupper 189
Graf automorfism grupp 193
Operationer på permutationsgrupper 194
Grafkompositionsgrupp 195
Grafer med denna grupp 198
Symmetriska grafer 201
Grafer med starkare symmetri 204
Övningar 206
Kapitel 15. Överlåtelser 209
Markerade kolumner 209
Polyas uppräkningssats 211
Uppräkning av räkningar 216
Uppräkning av träd 219
Potensgruppsuppräkningssats 224
Lösta och olösta problem med grafuppräkning 225
Övningar 230
Kapitel 16. Digrafer 232
Diagram och anslutningsbarhet 232
Orienterad dualitet och konturlösa digrafer 234
Digrafer och matriser 237
Genomgång av problemet med att återställa turneringar 244
Övningar 244
Bilaga I: Diagram 248
Bilaga II. Diagramdiagram 260
Bilaga III. Träddiagram 266
Referenser och namnregister 268
Beteckningsindex 291
Ämnesregister 293
2012-07-26 kl 13:02 Kapitel 4. Grafer.
Kapitel 5. Diagram.
Kapitel 6. Uppräkning av maktgruppen.
Kapitel 7. Superposition.
Kapitel 8. Block.
Kapitel 9. Asymptotik.
Kapitel 10. Olösta problem.
Bilaga I
Bilaga II.
Bilaga III.
Bibliografi.
Namnindex.
Sakregister.
Beteckningsindex.
2012-07-26 kl 13:03
 |
Diestel R. Graph Theory - Springer, 2005 - 410 sidor. |
Innehåll
Förord. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1. Grunderna. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Matchning, täckning och packning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3. Anslutning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4. Plana grafer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5. Färgläggning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6. Flöden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7. Extrem grafteori. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8. Oändliga grafer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
9. Ramsey Theory for Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
10. Hamilton cyklar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
11. Slumpmässiga grafer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
12. Minderåriga, träd och WQO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
A. Oändliga mängder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
B. Ytor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Tips för alla övningar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Symbolindex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Översättning från engelska och förord V. P. Kozyreva. Ed. G.P. Gavrilova. Ed. 2:a. - M.: Redaktionell URSS, 2003. - 296 sid. — ISBN 5-354-00301-6 På senare tid har grafteori uppmärksammats alltmer av specialister inom olika kunskapsområden. Tillsammans med sina traditionella tillämpningar inom vetenskaper som fysik, elektroteknik, kemi, har den också trängt in i vetenskaper som tidigare ansågs långt ifrån det - ekonomi, sociologi, lingvistik, etc. Nära kontakter av grafteorin med topologi, gruppteori och sannolikheter . Ett särskilt viktigt samband finns mellan grafteori och teoretisk kybernetik (särskilt automatteori, operationsforskning, kodningsteori, spelteori). Grafteori används i stor utsträckning för att lösa olika problem på datorer. Under de senaste åren har ämnet grafteori blivit betydligt mer mångsidigt; antalet publikationer ökade kraftigt. Den här boken skrevs av en av de framstående specialisterna inom diskret matematik. Trots den lilla volymen och sammanfattningen av presentationen täcker boken ganska fullt ut det aktuella tillståndet för grafteorin. Det kommer säkerligen att vara användbart för studenter vid universitet och tekniska skolor och kommer utan tvekan att vara av intresse för en bred krets av vetenskapsmän som är involverade i tillämpningar av diskret matematik.
Introduktion Öppning!
Problemet med Königsbergsbroarna
Elektriska kretsar
Kemiska isomerer
"Runt världen"
Fyrfärgshypotes
Grafteori på 1900-talet Grafer
Typer av grafer
Rutter och anslutningar
Grader
Ramsey problem
Extrema grafer
Skärningsgrafer
Operationer på grafer
Övningar Block
Ledpunkter, broar och block
Blockgrafer och artikulationspunktsgrafer
Övningar Träd
Beskrivning av träd
Centers och centroider
Träd av block och artikulationspunkter
Oberoende cykler och samcyklar
Matroider
Övningar Anslutningsmöjligheter
Connectivity och edge connectivity
Grafiska versioner av Mengers teorem
Andra varianter av Mengers sats
Övningar Skiljeväggar
Övningar Diagramövergångar
Euler-grafer
Hamiltonska grafer
Övningar Kantgrafer
Några egenskaper hos kantgrafer
Karakterisering av kantgrafer
Speciella kantgrafer
Kantgrafer och övergångar
Totala grafer
Övningar Faktorisering
1-faktorisering
2-faktorisering
Träighet
Övningar Beläggningar
Täckningar och oberoende
Kritiska hörn och kanter
kustkärna
Övningar Planhet
Plana och plana grafer
Outerplanar grafer
Pontryagin-Kuratowskis teorem
Andra karakteriseringar av plana grafer
Genus, tjocklek, storlek, antal korsningar
Övningar Målarbok
Kromatiskt nummer
Femfärgssats
Fyrfärgshypotes
Heawoods sats om färgläggning av kort
Unikt färgbara grafer
Kritiska grafer
Homomorfismer
Kromatiskt polynom
Övningar Matriser
Adjacency matris
Incidentmatris
Cykelmatris
Översikt över ytterligare egenskaper hos matroider
Övningar Grupper
Grupp av grafautomorfismer
Operationer på permutationsgrupper
Sammansättning graf grupp
Grafer med denna grupp
Symmetriska grafer
Grafer med starkare symmetri
Övningar Överföringar
Märkta grafer
Polyas uppräkningssats
Uppräkning av grafer
Uppräkning av träd
Potensgruppsuppräkningssats
Lösta och olösta problem med grafuppräkning
Övningar Digrafer
Digrafer och anslutningsbarhet
Orienterad dualitet och konturlösa digrafer
Digrafer och matriser
Granskning av frågan om turneringsrestaurering
Övningar Ansökan
Diagram
Diagramdiagram
Träddiagram Lista över referenser och namnregister
Beteckningsindex
Sakregister
, 2-Lek_Yktimaldylyktar theories.doc.
F.Harari
GRAFTEORI
M.: Mir, 1973, 300 s.
På senare tid har grafteori uppmärksammats alltmer från specialister inom olika kunskapsområden. Tillsammans med dess traditionella användningsområden i sådana spindlar, liksom fysik, elektroteknik, kemi, har den trängt in i vetenskaper som tidigare ansågs långt ifrån det - ekonomi, sociologi, lingvistik, etc. Nära kontakter mellan grafteorin med topologi, gruppteori och sannolikhetsteori har länge varit kända. Ett särskilt viktigt samband finns mellan grafteori och teoretisk kybernetik (särskilt automatteori, operationsforskning, kodningsteori, spelteori).
Grafteori används i stor utsträckning för att lösa olika problem på datorer.
De senaste åren, ämnen grafteorin har blivit mycket mer mångsidig; antalet publikationer ökade kraftigt.
Den här boken skrevs av en av de framstående specialisterna inom diskret matematik. Trots den lilla volymen och sammanfattningen av presentationen täcker boken ganska fullt ut det aktuella läget för grafteorin. Det kommer säkerligen att vara användbart för studenter vid universitet och tekniska högskolor och kommer utan tvekan att vara av intresse för en bred krets av vetenskapsmän som är involverade i tillämpningar av diskret matematik.
Översättningsredaktörens förord 6
Inledning 9
Kapitel 1. Upptäckt! 13
Königsberg Bridges Problem 13
Elektriska kretsar 14
Kemiska isomerer 15
"Jorden runt" 16
Fyrfärgshypotes 17
Grafteori under 1900-talet 18
Kapitel 2. Kolumner 21
Typer av grafer 21
Rutter och anslutningar 26
Grader 27
Ramsey Problem 28
Extrema grafer 30
Skärningsdiagram 33
Operationer på grafer 35
Övningar 38
Kapitel 3. Block 41
Ledpunkter, broar och block 41
Blockgrafer och artikulationspunktsgrafer 45
Övningar 46
Kapitel 4. Träd 48
Beskrivning av träd 48
Centrum och tyngdpunkter 51
Träd av block och ledpunkter 53
Oberoende cykler och samcykler 54
Matroider 57
Övningar 59
Kapitel 5. Anslutningar 60
Anslutningsmöjligheter och kantanslutningar 60
Grafiska versioner av Mengers sats 64
Andra varianter av Mengers sats 70
Övningar 74
Kapitel 6. Partitioner 76
Övningar 81
Kapitel 7. Traverserande grafer 83
Euler-grafer 83
Hamiltonska grafer 85
Övningar 88
Kapitel 8. Kantdiagram 91
Vissa egenskaper hos kantgrafer 91
Karakterisering av kantgrafer 94
Speciella kantgrafer 99
Kantgrafer och genomgångar 101
Totala grafer 103
Övningar 104
Kapitel 9. Faktorisering 106 1-faktorisering 106 2-faktorisering 111
Träighet
113
Övningar 116
Kapitel 10. Beläggningar 117
Täckningar och självständighet 117
Kritiska hörn och kanter 120
Kustkärna 122
Övningar 124
Kapitel 11. Planaritet
126
Plana och plana grafer 126
Ytterplansgrafer 131
Pontryagins sats - Kuratovsky 133
Andra karakteriseringar av plenumdiagram 138
Genus, tjocklek, storlek, antal korsningar 141
Övningar 148
Kapitel 12. Målarbok 151
Kromatiskt nummer 152
Femfärgssats 155
Fyrfärgshypotes 156
Heawoods sats om färgläggning av kort 162
Unikt färgbara grafer 164
Kritiska grafer 167
Homomorphisms 169
Kromatiskt polynom 172
Övningar 175
Kapitel 13. Matriser 178
Adjacency-matris 178
Incident Matrix 180
Cykelmatris 183
Granskning av ytterligare egenskaper hos matroider 186
Övningar 187
Kapitel 14. Grupper 189
Graf automorfism grupp 193
Operationer på permutationsgrupper 194
Grafkompositionsgrupp 195
Grafer med denna grupp 198
Symmetriska grafer 201
Grafer med starkare symmetri 204
Övningar 206
Kapitel 15. Överlåtelser 209
Markerade kolumner 209
Polyas uppräkningssats 211
Uppräkning av räkningar 216
Uppräkning av träd 219
Potensgruppsuppräkningssats 224
Lösta och olösta problem med grafuppräkning 225
Övningar 230
Kapitel 16. Digrafer 232
Diagram och anslutningsbarhet 232
Orienterad dualitet och konturlösa digrafer 234
Digrafer och matriser 237
Genomgång av problemet med att återställa turneringar 244
Övningar 244
Bilaga I: Diagram 248
Bilaga II. Diagramdiagram 260
Bilaga III. Träddiagram 266
Referenser och namnregister 268
Beteckningsindex 291
Ämnesregister 293
Ämnesindexdiagram automorfism 190 grund av samcykler 55
Cykler 55 block 41 valens av vertex 27 vertex av graf 22, 126
- isolerad 28
- incident till kant 22
- slut 28
- kritisk 121
- stationär 201
- digraf 232
- kringutrustning 51
- Central 51
- tyngdpunkt 52 vertex bas 237 hörn liknande 201
- intilliggande 22, 213 vertexvikt 52 funktionsvikt 213 gren 56
- till toppen 52 virvel 187 exteriör av cykeln 134 konvex polyeder 130 Ulams hypotes 25, 26, 48, 58, 202,
244
- Hadwiger 161, 162
- fyra färger 151, 156-162, 164,
167, 172 graf homomorfism 169
- full beställning l 169
- elementär 169 homomorf bild av grafen 196 gränsoperator 54 yta 127
- extern 127
- intern 127 count asymmetrisk 190
- acyklisk 48
- grundläggande 132
- oändliga 36
- 45 block
- - och artikulationspunkter 53
- vertex-kritisk 121
- vertex-symmetrisk 201
- ytterplanar 131
- - max 131
- ganska osammanhängande 28
- Hamilton 85
- geometriskt dubbel 138
- David 29
- tvåhjärtblad 31
- ytterligare 29
- intervall 35
- klicka 34
- kombinatorisk dual 139
- kritisk 167
- kubik 28
- Levi 205, 206
- McG 205
- regisserad 23
- odelbar 41
- oreducerbar 123
- unikt färgsättbar 164
- enkelcykel 58
- korsningar 33
- Petersen 113
- plan 127
- - max 128
- lägenhet 127
- underavdelningar 101
- komplett 29 graf komplett bipartite 32
- - n-slag 37
- semi-irreducerbar 123
- märkt 23
- godtyckligt Hamiltonian 89
- - acceptabel 89
- enkel 197
- kantkritisk 121
- kant-vanlig 202
- ribbsymmetrisk 201
- costal 91, 94
- - itererade 91
- ordinarie 28
- självkompletterande 29
- reducerbar 123
- symmetrisk 201
- komposit 197
Toroidal 142
- totalt 103
- 45 artikulationspunkter
- triviala 22
- Hiwooda 204
- Euler 83
- n-färgbar 152
- n-transitiv 204
- n-unitransitiv 204
- n-kromatisk 152
- \alfa-permuterbar 206 sammansättningsgraf 196 grafoid 58 homeomorfa grafer 132
- isomorfisk 24, 190
- cospectral 188 grupp 189
- kolumn 190
- vertex 190
- dihedral 195
- omväxlande 195
- 213 konfigurationer
- Ångbad 217
- - reducerad 218
- byten 190
- costal 191
- symmetrisk 195
- effekt 194
- identiska 195
- cykliska 195 grupper identiska 190
- isomorft 190 träd 48
- block och ledpunkter 54
- rot 219
- med hängande rot 220
- inkommande 235
- utgående 235 block diagonal 47
"Hasse diagram" 73 diameter 27 rutt längd 27 lägger till en vertex 25
- kanter 25 komplement till grafen 29 nåbarhet 133 arborealitet av grafen 113 båge 23, 232 djur 227 gitterbeläggning, 2, 227 stjärna (tass, gäng) 32 isomorfism 24 invariant 24 förekomst av kant och hörn 2 källa 2 distor 1 källa 235 karta lägenhet 127
- - med rotkant 227 kvadrat av graf 27 kvadratrot av graf 38 cell 204 antal punkter 243 klick av graf 34 coboundary 55 coboundary operator 54 kodträd 56 hjul 63 komplex 20 sammansättning av grafer 37, 196
- grupper 194 komponenter 27
- udda 108
- ensidig 233
- stark 233
- svag 233 kondensation 234 krets 233
- Euler 240 konfiguration 213 konjunktion 40, 243 krona av grafer 198 cocycle 55 grovhet (korn, grovhet) 146 Burnsides lemma 212, 214 skog 48 matris linje 71 linjär subgraf av en graf 180
Digraph 179
Väg 26
- stängt 26
- ofullkomlig 119
- öppet 26
- perfekt 119
- Y-reducerbar 120 nåbarhetsmatris 238
- ISO-incidenter
- samcyklar 184
- omgångar 238
- halva grader av inflygning 239
- - utfall 239
- sparsam 241
- angränsningar till graf 179
- - digraf 237
- cykler 183 matrissats om träd 178,
181, 239 matroid 57
- binär 188
- grafik 180
- grafik 180
- samcykler av graf 57
- grafcykler 57
- Euler 188 polynom av grafträd 187 uppsättning hörn 22
- externt stabil 118
- invändigt stabil 118
- oberoende 57, 108, 118
- skiljer 64
- kanter 22 bro 41 multigraf 23 ärftlig egendom 119 epigraf 24 oberoende matrisenheter 71 omkrets 27 sammanslutning av grafer 36 enfärgad klass 152 halsband 212-215, 224, 225 grannskap av en vertex 197
- sluten 197 miljö 27 orbit 211 digraf 232
- konturlös 235
- kontrafunktionell 236 disjunkt digraph 233
- omvänd 234
- ensidig 233
- primitiv 246
- costal 245
- stark 233
- svag 233
- strikt ensidig 244
- - svag 244
- funktionell 236
- Eulerian 240 graforientering 246 skelett 55 par kopplingar 62 matchande 119
- största 119 listningsraden för konfigurationer 213
- - - figurer 213 loop 23 subgraf 24
- linjär 180
- kärna 24
- genererade 24
- även 227 vertex som täcker 117
- kant 117 polyeder 127 helfärgad 170 komplett uppsättning invarianter 24 graf semigrupp 208 halvkrets 233 halvväg 233 halvväg 233 halvgrad 232
- utfall 232 grupporder 190 n-vägsföljare 204
principen om orienterad dualitet 234, 235 produkt av grafer 36
- grupper 190
- elementmässigt 239 cocycle space 55
- cyklar 55 pseudograf 23 väg 233 partition av graf 76
- grafik 76
- nummer 76 skär 55 rang samcyklisk 56
- cyklisk 55 simplex dimension 20 avstånd i diagram 27
- - digraph 233 färgningsdiagram 152
- platt kort 156
- hela 170
- revben 159
- t färgar 172 kanter multiplar av 23
- oberoende 108
- liknande 01, 2
- intill 22 kanter av graf 22
- infaller i vertex 22
- kritisk 121
- underbruten 101
- symmetrisk 221 typ av kolumn 142
- polyhedron 142 nätverk 70 system av olika representanter
72 stabilisator 211 vertex grad 27
- kolumn 27
- grupper 190
- revben 202 dränera 235 sammandragning 137
- elementär 137 summan av kolumner 37
- grupper 193 Vinet-Cauchy sats 181
- om interpolation av homomorfismer
171
- ungefär fem färger 151, 155, 156
- Polya uppräkning 211-215, 217,
218
- - effektgrupp 224
- Hiwooda om färgläggningen av Karts 162-164
- BEST 240 graftjocklek 145 ledpunkt 41 transitiv trippel 241 triangel 26
- udda 95
- jämn 95 turnering 241 match turnering 245 theta graph 85 vertex borttagning 25
- kanter 25 graf som lägger 126 ekvation av olikhet egenskaper för träd 221
- Euler-Poincaré 57 graffaktor 106 graffaktorisering 106 figur 213 Otterformel 222
- Euler för polyhedra 127 anslutningsfunktion 62 anslutning 60
- lokal 66
- ensidig 233
- costal 60
- stark 233
- svagt 233 ackord 55 kromatisk klass 159
- polynom 173 färggraf för grupp 199 centrum av graf 51
träd tyngdpunkt 52 kedjor disjunkta 64
- Kantsönderdelning 64 kedja 26
- omväxlande 109
- geodetisk 27
- enkel 26 cykel 26
- Hamilton 85
- kolumn ja 58
- matroid 57
- enkel 26
- Euler 83 cyklisk trippel 241 cyklisk grafvektor 54 cyklisk gruppindex 212 akromatiskt nummer 170
- Independence vertex 118
- - costal 118
- korsningar 33
- vertexbeläggningar 117
- - costal 117
- Ramsay 30
- - costal 104
- korsningar 148
- Hadwiger 177
- kromatisk 152
- n-kromatisk 177 exponentiering 208 excentricitet 51 grafelement 103 angränsande element 103 grafendomorfism 208 vertexkärna 125
- kant 122 kedja, 54 bas, 1, 237 skelett, 1, 127 kedja, 1, 54 gitter, 2, 227 gitter, 3, 227 n-cell 204 n-komponent 63 n-kub 37 n-väg 204 n-färg 152
- kant 159 n-anslutning 63 n-faktor 106 n-faktorisering 106
P-set 119
Jag gillar inte citat. Berätta vad du vet.
R. Emerson (1803-1882) - amerikansk författare och filosof.
| Förord | |||
| Introduktion | |||
| Kapitel 1. | Öppning! | ||
| Problemet med Koenigsbergbroarna | |||
| Elektriska kretsar | |||
| Kemiska isomerer | |||
| "Runt världen" | |||
| Fyrfärgshypotes | |||
| Grafteori på 1900-talet | |||
| Kapitel 2. | Grafer | ||
| Typer av grafer | |||
| Rutter och anslutningar | |||
| Grader | |||
| Ramsey problem | |||
| Extrema grafer | |||
| Skärningsgrafer | |||
| Operationer på grafer | |||
| Övningar | |||
| Kapitel 3. | Block | ||
| Ledpunkter, broar och block | |||
| Blockgrafer och artikulationspunktsgrafer | |||
| Övningar | |||
| Kapitel 4. | Träd | ||
| Beskrivning av träd | |||
| Centers och centroider | |||
| Träd av block och artikulationspunkter | |||
| Oberoende cykler och samcyklar | |||
| Matroider | |||
| Övningar | |||
| Kapitel 5. | Anslutningsmöjligheter | ||
| Connectivity och edge connectivity | |||
| Grafiska versioner av Mengers teorem | |||
| Andra varianter av Mengers sats | |||
| Övningar | |||
| Kapitel 6. | Skiljeväggar | ||
| Övningar | |||
| Kapitel 7. | Diagramövergångar | ||
| Euler-grafer | |||
| Hamiltonska grafer | |||
| Övningar | |||
| Kapitel 8. | Kantgrafer | ||
| Några egenskaper hos kantgrafer | |||
| Karakterisering av kantgrafer | |||
| Speciella kantgrafer | |||
| Kantgrafer och övergångar | |||
| Totala grafer | |||
| Övningar | |||
| Kapitel 9 | Faktorisering | ||
| 1-faktorisering | |||
| 2-faktorisering | |||
| Träighet | |||
| Övningar | |||
| Kapitel 10. | Beläggningar | ||
| Täckningar och oberoende | |||
| Kritiska hörn och kanter | |||
| Kustkärna | |||
| Övningar | |||
| Kapitel 11. | Planhet | ||
| Plana och plana grafer | |||
| Outerplanar grafer | |||
| Pontryagin-Kuratowskis teorem | |||
| Andra karakteriseringar av plana grafer | |||
| Genus, tjocklek, storlek, antal korsningar | |||
| Övningar | |||
| Kapitel 12. | Målarbok | ||
| Kromatiskt nummer | |||
| Femfärgssats | |||
| Fyrfärgshypotes | |||
| Heawoods sats om färgläggning av kort | |||
| Unikt färgbara grafer | |||
| Kritiska grafer | |||
| Homomorfismer | |||
| Kromatiskt polynom | |||
| Övningar | |||
| Kapitel 13. | Matriser | ||
| Adjacency matris | |||
| Incidentmatris | |||
| Cykelmatris | |||
| Översikt över ytterligare egenskaper hos matroider | |||
| Övningar | |||
| Kapitel 14. | Grupper | ||
| Grupp av grafautomorfismer | |||
| Operationer på permutationsgrupper | |||
| Graf-sammansättning grupp | |||
| Grafer med denna grupp | |||
| Symmetriska grafer | |||
| Grafer med starkare symmetri | |||
| Övningar | |||
| Kapitel 15. | Överföringar | ||
| Märkta grafer | |||
| Polyas uppräkningssats | |||
| Uppräkning av grafer | |||
| Uppräkning av träd | |||
| Potensgruppsuppräkningssats | |||
| Lösta och olösta problem med grafuppräkning | |||
| Övningar | |||
| Kapitel 16. | Digrafer | ||
| Digrafer och anslutningsbarhet | |||
| Orienterad dualitet och konturlösa digrafer | |||
| Digrafer och matriser | |||
| Granskning av frågan om turneringsrestaurering | |||
| Övningar | |||
| Bilaga I: Diagram | |||
| Bilaga II. Diagramdiagram. | |||
| Bilaga III. Träddiagram | |||
| Lista över referenser och namnregister | |||
| Beteckningsindex | |||
| Sakregister | |||
30 år har gått sedan publiceringen av F. Hararis monografi "Graph Theory", men dess attraktiva egenskaper har inte bleknat alls. Den sammanslagning av terminologi som författaren genomförde och spreds brett tack vare denna bok har blivit allmänt accepterad. Undervisning i grafteori med hjälp av boken av F. Harari bedrivs vid många universitet i vårt land. Under den senaste tiden har tillämpningsområdet för grafteori utökats avsevärt - inom konstruktionen av stora datorsystem och inom programmering, inom ekonomi och transport, inom genetik och biologi, etc. En betydande ökning av publikationer fortsätter, ett antal läroböcker och monografier har publicerats, bland vilka vi kan notera böckerna av A.A. Zykov "Elements of Graph Theory" (M.: Nauka, 1987) och V.A. Emelichev et al. "Lectures on teorigraferna" (M.: Nauka, 1990).
Ett stort antal problem som anges i boken som olösta hittade sin lösning, och några av dem löstes av många elever av F. Harari. F. Harari själv, som nu är över 80 år, arbetar fortfarande fruktsamt och publicerar. Särskilt betydande framsteg under den senaste tiden har uppnåtts för att konstruera effektiva algoritmer för att lösa grafteoretiska problem, bland vilka det är värt att notera algoritmer för att konstruera ett maximalt flöde (se: Adelson-Velsky G.M., Dinits E.A., Karzanov A.V. Strömmande algoritmer. M.: Nauka, 1975). Och detta trots att många problem inom grafteorin - att hitta minimala färger, täckningar, maximala kompletta subgrafer, Hamiltonska cykler etc. - är NP-kompletta, d.v.s. algoritmiskt komplex (se: Gary M., Johnson D. Datorer och svårlösta problem. M.: Mir, 1982). Bristen på algoritmer i F. Hararis bok kompenseras delvis av N. Christofides bok "Graph Theory. Algorithmic Approach" (M.: Mir, 1978). En genomgång av resultat på grafteori finns i verken: Kozyrev V.P. Grafteori // Resultat av vetenskap och teknik. VINITI, sir. teori förmodligen, mat. statistik. och teori. cybern. 1972. T. 10. P.25--74; Kozyrev V.P., Yushmanov S.V. Grafteori (algoritmiska, algebraiska och metriska problem) // Results of Science and Technology. VINITI, sir. teori förmodligen, mat. statistik. och teori. cybern. 1985. T. 23. P.68--117; Kozyrev V.P., Yushmanov S.V. Representation av grafer och nätverk (kodning, placering och stapling) // Results of Science and Technology. VINITI, sir. teori förmodligen, mat. statistik. och teori. cybern. 1990. T. 27. P.129--196.
V.P.Kozyrev
När jag var 14 år var min pappa så dum att jag knappt kunde stå ut med honom. När jag fyllde 21 blev jag förvånad över att se hur vis gubben hade blivit under dessa 7 år.
Mark Twain
Det finns flera anledningar till det växande intresset för grafteori. Det är ett obestridligt faktum att grafteori används inom områden som fysik, kemi, kommunikationsteori, datordesign, elektroteknik, maskinteknik, arkitektur, operationsforskning, genetik, psykologi, sociologi, ekonomi, antropologi och lingvistik. Denna teori är också nära besläktad med många grenar av matematiken, inklusive gruppteori, matristeori, numerisk analys, sannolikhetsteori, topologi och kombinatorisk analys. Det är också säkert att grafteori fungerar som en matematisk modell för alla system som innehåller en binär relation. Grafer är engagerande och estetiskt tilltalande på grund av deras presentation som diagram. Även om grafteorin innehåller många resultat som är elementära till sin natur, innehåller den också ett enormt överflöd av mycket subtila kombinatoriska problem som är värda uppmärksamheten från de mest sofistikerade matematikerna.
Tidiga versioner av denna bok dök upp 1956, när Institutionen för matematik vid University of Michigan regelbundet började undervisa i kurser i grafteori och kombinatorisk analys. Det noterades att det ur metodisk synpunkt är olämpligt att bevisa alla påståenden som formulerats. Detta gjorde att kursen kunde innehålla betydligt fler kända resultat än vad som annars hade varit möjligt. Således kan boken användas som en manual, skriven på traditionellt sätt enligt "Mohrs metod", där eleven ökar sina kunskaper i matematik, försöker bevisa alla satser formulerade utan bevis. Observera dock att några av de utelämnade bevisen är både svåra och långa. De som behärskar innehållet i denna bok kommer att kunna fortsätta studera speciella ämnen och tillämpa grafteori på andra områden.
Boken som erbjuds läsaren försöker presentera olika forskningsområden inom grafteori i deras logiska följd, ge en historisk exkursion och förklara presentationen med hjälp av ritningar som illustrerar begrepp och resultat. Dessutom är tre bilagor försedda med diagram över grafer, riktade grafer och träd. Fokus i boken ligger på satser, även om algoritmer och tillämpningar ibland nämns.
Övningarna som erbjuds i slutet av varje kapitel (förutom det första) skiljer sig markant från varandra i sin svårighetsgrad. Siffrorna på de övningar som inte är enkla och som inte följer direkt av de resultat som givits tidigare är inskrivna i fetstil. Särskilt svåra övningar är också markerade med en asterisk. För att behärska materialet som presenteras i boken rekommenderas läsaren att bekanta sig med varje övning. Många av de "enklare" övningarna kan tyckas mycket svåra för läsaren om han inte har studerat materialet i motsvarande kapitel.
Vi råder läsaren att inte fastna i kapitel 2 och dess många övningar, som i sig kan användas som en förkortad kurs i grafteori för förstaårs- eller gymnasieelever. Läraren hittar i denna bok material för en enterminskurs i grafteori. Samtidigt kan hela boken ligga till grund för en årslång kurs. Några av de sista kapitlen kan rekommenderas som ämnen för avancerade seminarier. Eftersom det enda kravet för att läsa den här boken egentligen är den svårfångade egenskapen som kallas "matematisk mognad", kan den användas som en lärobok för studenter på grund- och forskarnivå. För att förstå de fyra sista kapitlen är det bra att vara bekant med elementär gruppteori och matristeori.
Jag anser att det är min plikt att uttrycka tacksamhet till många av mina vänner för deras ovärderliga hjälp och råd vid utarbetandet av denna bok. Lovell Beinecke och Gary Chartrand har varit de mest hjälpsamma genom åren!
Under det senaste året har mina elever Dennis Geller, Bennett Manvel och Paul Stockmeyer varit särskilt entusiastiska när det gäller att dela med sig av sina kommentarer och förslag. Jag fick också mycket hjälp av Stefan Hedetniemi, Edgar Palmer och Michael Plummer. Senast har Branko Grünbaum och Dominic Welsh varit vänliga nog att läsa hela boken ordentligt. Jag är personligen ansvarig för alla fel och mest tveksamma passager i presentationen.
Under de senaste tjugo åren av grafteoretisk forskning har jag fått publikationsstöd från Air Force Research Command, National Institutes of Health, National Science Foundation, Navy Office of Scientific Research och Rockefeller Foundation. Under denna tid var jag glad över att kunna dra nytta av gästfriheten inte bara från University of Michigan, utan också från andra utbildningsinstitutioner som jag hade möjlighet att besöka. Bland dem finns Institute of Advanced Studies, Princeton University, Tavistock Institute of Sociology i London, University College London och London School of Economics. Alice Miller och Anna Jenn från Group Dynamics Research Center skrev sakkunnigt och snabbt om manuskriptet. Slutligen är jag särskilt tacksam till Addison-Wesley för deras tålamod att vänta på detta manuskript under de tio år som gått sedan kontraktet tilldelades, och för deras omfattande hjälp med att få boken publicerad.
Frank Harari
Frank Harary
Enastående amerikansk matematiker, specialist inom området diskret matematik. Född i New York, i en familj av judiska invandrare från Mellanöstern. Han tog examen från Brooklyn College och tog en kandidatexamen 1941 och en magisterexamen 1945. 1948 tog han en doktorsexamen från University of California i Berkeley. Från 1948 till 1985 tjänstgjorde som professor vid University of Michigan. Sedan 1987 - extraordinär (senare hedersprofessor) vid University of Las Cruces (New Mexico).
Frank Harari är författare till ett flertal vetenskapliga arbeten, böcker och artiklar om grafteori och dess tillämpningar inom olika kunskapsområden, särskilt inom samhällsvetenskaperna, inklusive lingvistik, sociologi, statsvetenskap, psykologi, etc. Han har hållit föreläsningar om grafteori mer än vid tusentals vetenskapliga konferenser i 87 länder. Många av hans studenter, inklusive 16 doktorer i vetenskap, blev framstående vetenskapsmän. Han var grundare och medlem av redaktionerna för flera vetenskapliga tidskrifter ägnade åt diskret matematik, och tilldelades hedersgrader av amerikanska och europeiska universitet. Hans klassiska verk "Graph Theory" (1969) har blivit en uppslagsbok för alla specialister inom denna gren av matematik.
