Graphentheorie 2 – Dr. Schaudt

Graphentheorie2–Dr.Schaudt
0.GrundlegendeDefinitionen
•
•
Definitionen:Graph,Multigraph,zugrundeliegenderGraph,Orientierung,stabil,k-färbbar,
chromatischeZahl,Pfad/Weg,Kreis,zusammenhängend
Satz0.1:Bipartit⟷alleKreisesindgerade
Beweis
1.GerichteteGraphen
1.1WegeingerichtetenGraphen
•
•
•
•
•
Definitionen:gerichteterPfad/Weg/Kreis,erreichbar,starkeZHK,starkzusammenhängend,
Turnier,Vorgänger,Nachfolger
Satz1.1:Genthälteinenger.WegderLängex(G’)-1
Beweis
Korollar1.2:TurnierebesitzeneinenHamiltonweg
Beweis
Satz1.3:GhateinestabileMengeX,sodassjederKnotenüberzweiKnotenerreicht Beweis
werdenkann Korollar1.4:JedesTurnierbesitzteine‚graueEminenz’ Beweis
1.2KreiseingerichtetenGraphen
•
•
•
•
Definitionen:Panzyklizität
Satz1.5:Jedesstark-zusammenhängendeTurnieristpanzyklisch(undbesitzt dahereinenHamiltonkreis)
Satz1.7:DasHamiltonkreis/-Weg-EntscheidungsproblemistNP-vollständig
Satz1.9:HatjederKnotenn/2Vorgänger&n/2Nachfolger,soistderGraph hamiltonsch
Beweis
Beweis
Beweis
1.3Anwendungsbeispiele
•
•
•
•
•
•
•
•
Beispiele:Jobsequencing,Einbahnstraßensysteme
Definitionen:(starker)k-Kantenzusammenhang,Adjazenzmatrix,Abstand,Durchmesser,primitive
Matrix
Satz1.10:Esgibteinestarkzsh.Orientierung,wennG2-zusammenhängendist
Beweis
SatzvonNash-Williams:Eink-kanten-stark-zsh.Graphhateine
k-kanten-stark-zsh.Orientierung
Satz&Korollar1.12/1.13:Tstarkzmh.⟷Adjazenzmatrixprimitiv
Beweis
SatzvonPerron-Frobenius:FürjedeprimitiveMatrixexistierteindeutiges
Eigenwert/Eigenvektorpaar,sodassdieRangfolgenerstellungkonvergiert
VerfahrenzurRangfolgenerstellung
2.FlüsseundZirkulationen
2.1GruppenwertigeFlüsse
•
•
•
•
•
Definitionen:Fluss,Bilanz,H-wertigerFluss,H-Fluss,k-Fluss,Flusszahlφ,Fundamentalkreis
Satz&Korollar2.1/2.2(Tutte):JederGraphbesitzteinFlusspolynom,welchesnur Beweis
vonderOrdnungderGruppeHabhängt
Lemma&Satz2.3/2.4:Ghateinenk-Fluss⟷GhateinenZ_k-Fluss Beweis
Bemerkung:Orientierungegal!
Satz2.5:Graphen⟷Flüsse Beweis
2.2Flüsse&Färbungen
•
Definitionen:planar,dualerGraphG*,Baumordnung,normalerSpannbaum
•
•
Satz2.6:FürplanareGraphengilt:x(G)=φ(G*) Lemma2.7:Zsh.MultigraphenhabenzujederWurzeleinennormalenSpannbaum
Beweis
Beweis
2.3Flussvermutungen
•
•
•
•
•
•
•
•
Definitionen:Minor,Snark
Satz2.8:JederMultigraphohneSchnittkantehateinenk-Fluss,füreink
Vermutung2.9:FüralleGraphenreichtk≤5
Vermutung2.10:OhneeinenPetersen-Minorreichtsogark≤4
Bemerkung:Vermutung2=Snark-SatzimpliziertdenVier-Farben-Satz Vermutung2.11:OhneSchnittaus1oder3Kantenreichtsogark≤3
SatzvonGrötzsch:JederplanareGraphohneDreieckist3-färbbar
Satz2.13(Seymour):JederGraphohneSchnittkantehateinen6-Fluss Beweis
Beweis
Beweis
3.Graphenfärbungen
3.1KritischeGraphen
•
•
•
•
•
•
•
Definitionen:k-kritisch,(Knoten-)Schnittmenge,(u,v)-KomponentevomTyp1/2
Satz3.1:IstGk-kritischgiltδ(G)≥k-1
Korollar3.2:InGk-chromatischgibtesmind.kKnotenmitGradmind.k-1
Satz3.3:Jederk-kritischeGraphist(k-1)-kantenzsmh.
Satz3.4:IneinemkritischenGraphengibteskeineSchnittmenge,dieeineCliqueist
Satz3.5:Hateink-kritischerGrapheineSchnittmenge(u,v),sogibtesgenaueine
Typ1-undeineTyp2-(u,v)-Komponente
Korollar3.6:Gk-kritischmitSchnittmengeu,vdanngiltd(u)+d(v)≥3k-5
Beweis
Beweis
Beweis
Beweis
Beweis
Beweis
3.2DieVermutungvonHadwiger
•
•
•
•
Vermutung(Hadwiger):EinGraphmitx(G)=kenthälteinenK_kalsMinor
Bemerkung:DerFallk=5impliziertdenVier-Farben-Satz Satz3.8:DieVermutunggiltfürk=1,2,3,4 Ex-VermutungvonHajós:WieHadwigernurmittopol.Minoren
Beweis
Beweis
3.3FärbungenvonGraphenaufFlächen
•
•
•
•
•
•
Definitionen:Fläche,geschlosseneFläche,zusammenhängendeSumme,Triangulierung,EulerCharakteristik,chromatischeZahleinerFläche
Satz:JedegeschlosseneFlächeisthomöomorphzuS^2,einerSummevonT^2odereinerSumme
vonRP^2
SatzvonEuler-Poincaré:FürGeingebettetaufFgiltm≤3n-3x
Satz3.11:DiechromatischeZahleinesGrapheneingebettetaufFistbeschränkt
Beweis
durcheineZahlabhängigvonderEuler-Charakteristik
Satz3.12:Seix≤0,dannistjederh-kritscherGraphaufFgleichK_h
Beweis
Satz3.13:DiechromatischeZahlvonT^2ist7unddievonRP^2+RP^2ist6.
Beweis
3.4Listenfärbungen
•
•
•
•
•
•
•
•
Definitionen:k-listenfärbbar,ListenchromatischeZahl,fast-trianguliert,ListenchromatscherIndex,
Kern,kern-perfekt
Bemerkung:EsgibtbipartiteGraphenmitbeliebighoherlistenchromatischerZahl
Satz3.15:HatGeinensehrhohenDurchschnittsgrad,istauchseinelistenchromatischeZahlhoch
Satz3.16&Lemma3.17:JederplanareGraphist5-listenfärbbar Beweis
Vermutung3.18:DerlistenchromatischeIndexentsprichtimmerderlistenchromatischenZahl
Satz3.19:FürbipartiteGraphengiltdieVermutung
Beweis
Lemma3.20:ExistierteinebestimmteOrientierungvonG,sogibteseine
Beweis
Listenfärbung
SatzvonGale&Shapley3.21:JederbipartiteGraphmitPräferenzlistenbesitzteinstabiles
Matching
Fragen:
• Satz3.5:Warumkannesnichtmehrals2Komponentengeben?

Download Report