date-created: 2024-05-14 12:45:47 date-modified: 2024-07-04 07:10:53

Eulers Formel

anchored to 115.00_graphentheorie_anchor proceeds from 115.04_Darstellung_von_graphen

Satz (10) | Eulers Formel

(gibt auch noch weitere Beweise, die man sich anschauen kann!)
siehe hier

[!Definition] Eulers Formel

Sei $G$ ein zusammenhängender, planarer Graph mit $n$ Knoten und $m$ Kanten und $\pi$ ist eine ebene Zeichnung von $G$ mit $f$ Flächen.

Was wird uns Eulers Formel hier aussagen? #card

Es gilt jetzt: $$n+f=m+2$$ Anders beschrieben mit: $$\mid V\mid +\mid F\mid =\mid E\mid +2$$

Beweis

Durch Induktion über die Anzahl$derKanten:Seiferner$n=0$,dannhabenwireinenKnotenohneKante,alsoZeichnungistnurKnotenmitAußenfacette.$n= 1, f_{1}$undsomit$n+f = m +2$,funktioniert.\ast \ast Induktionsschritt\ast \ast :Sei$G = (V,E)$einGraphmit$m$Kanten.WirsetzeneineFallunterscheidungan:\ast \ast Fall1\ast \ast :$G$hateinenKnoten$v$vomGrad1.L\ddot{o}schenwirjetzt$v$,dann$G’ = G \setminus{ v }$F\ddot{u}r$G’$giltjetzt:$n’ = n-1, m’= m-1 ,f’= f$undgem\ddot{a}ßderInduktionsvoraussetzungfolgtjetzt:$$\begin{array}{r}{n}^{\prime }+f^{\prime }=m^{\prime }+2n-1+f=m-1+2=n+f=m+2\end{array}$$\ast \ast Fall2\ast \ast :AlleKnotenhabenGrad$\geq2$L\ddot{o}schenwirjetztwiederKante$e$aus$G$undsomit$G’ = G \setminus { e }$(beliebiginunseremGraphen)Dadurchfolgtjetzt:$G’$hat$n’ = n$Knoten(aberwenigerKanten)$m= m -1$,unddieFacetten:$f’ = f-1$Dadurchgiltnun:$n’ + f’ = ,’ +2= n+f-1 = m-1 +2$undsomit$= n+f = m +2$EsbraucheineFallunterscheidung,weilwirdamitgarantierenk\ddot{o}nnen,dasswirkeinenKnotenl\ddot{o}schen,derunterUmst\ddot{a}ndendieVerteilungderFacettennichtverringert/ver\ddot{a}ndert.Wennwirfordern,dassderGrad$\geq 2$ ist, dann wissen wir immer, dass es eine Kombination zwischen den Punkten geben muss ( also kein Knoten, der einfach nirgens angebunden ist)..

Ferner können wir für Facetten und Kanten folgern: Aus dieser Betrachtung heraus können wir folgern:

[!Attention] jede Kante trennt / berührt eine Facette von beiden Seiten Denn wenn sie mehr schneiden würde, dann heißt es, dass wir keinen planaren Graphen haben –> Es funktioniert einfach nicht, dass ein Graph in seiner Struktur dann mehr als nur zwei Facetten hat ( auf der einen und anderen Seite dessen!)

Satz(11) | Eulers Formel | Allgemeiner

[!Definition] Verallgemeinerung Eulers Formel Sei $G = (V,E)$ein\ast \ast planarerGraph\ast \ast mit$n$Knotenund$m$Kanten,sowie$\pi$alseine\ast \ast ebeneZeichnung\ast \ast von$G$-m\ddot{o}glicherweisemitSchleifenundMehrfachkanten-mit$f$Facettenund$k$ Zusammenhangskomponenten.

Unter dieser Betrachtung gilt jetzt allgemein:

Was gilt, bzw wie ist die allgemeine Formel von Euler? #card

$$n-m+f=k+1$$

Beweisen der Aussage

Wir können diese allgemeine Euler-Aussage unter Betrachtung von Induktion beweisen, möchten sie hier aber unter Anwendung von Satz (10) Eulers Formel beweisen:

Wir wollen ferner eine Induktion über die Anzahl der Zusammenhangskomponenten $k$durchf\ddot{u}hren.\ast \ast Induktionsanfang\ast \ast :Seijetzt$k = 1$(also1Zusammenhangskomponente).DanngiltnacheulersFormel:$n + f = m+2$(wiein\ast \ast Satz10\ast \ast bereitsbetrachtet.)Fernergiltalsoauch:$$n-m+f=k+1$$\ast \ast Induktionsschritt\ast \ast :SeifernereinGraph$G = (V,E)$mit$k>1$Zusammenhangskomponenten.Wirf\ddot{u}genjetztzwischen2Zusammenhangskomponenten(eine)\ast \ast planareKanteein\ast \ast (alsoplatte,diesichnicht\ddot{u}berschneidet),diediese\ast \ast Zusammenhangskomponenten\ast \ast miteinanderverbindet(verbindenkann.)Es\ast \ast entsteht\ast \ast jetztdadurcheinneuerGraph$G’$mit$k’ = k - 1 ZsH$Komponentenundfernermit$n’ = n$Knotenudn$m = m +1$Kanten,sowie$f’ = f$ Facetten. Nach IV können wir jetzt entsprechend umformen #nachtragen

[!Attention] Übung Beweis der Aussage ohne Anwendung von Satz 10 kann durchgeführt werden. Wenn man das kann, dann scheint man gut vorbereitet zu sein.

Folgerungen aus Eulers Formel

Satz (12) | Eigenschaft $G$mit$n\geq 3$

[!Definition] #card

Für jeden einfachen Graphen $G = (V,E)$mit$n\geq 3$Knoten,sowie$m$Kantenund$f$Facettengiltferner::$$m\le 3n-6$$bzw.$$\mid E\mid \le 3\mid V\mid -6$$undfernerauch$f \leq 2n -4$

Beweis dieser Aussage

Im Kontext befinden wir uns in zusammenhängenden Graphen. (Wenn er nicht zusammenhängend ist, dann hat er halt weniger Kanten/)

Wir wollen durch zweifaches Abzählen der Kanten-Facetten Inzidenzen.

• Eine Kante ist zu höchstens zwei Facetten Inzidenz.
• Ferner: Brauch es mindestens 3 Kanten, um eine Facette zu bilden (anzugrenzen zu haben)

und somit: $$\begin{array}{rl}2m& \ge \mid Inzidenzen\mid \ge 3f\\ & ⟹f\le \frac{2}{3}m\end{array}$$\ast \ast OhneBeachtungderAllgemeinehit\ast \ast seidann:$G$einZusammenh\ddot{a}ngenderGraph-wenneresnochnichtist,dannf\ddot{u}genwirneueKantenein!.Esfolgtjetzt:$\implies m + n + f - 2$ ( wie in Satz (10) Eulers Formel) $\leq n + \frac{2}{3} \cdot m -2$(eingesetzt,ausderobigenBetrachtung).$\implies m \leq 3n -6\implies f \leq \frac{2}{3} m \leq \frac{2}{3}( 3n-6) \leq 2n-4$JedeKanteistzuh\ddot{o}chstens2Facetten\ast \ast inzident\ast \ast ,dadurch$2m$wirhabenferner$n$ Kanten.

(Edge Case: zwei Kanten, in Linie zu drei Knoten).

[!Korollar] Hilft beim evaluieren, ob ein Graph planar ist! warum #card Wir können jetzt einfach die Knoten/Kanten zählen und schauen, ob die Werte entsprechend der Formel von Euler ist.

Also ob: $$\mid E\mid \le 3\mid V\mid -6$$ gilt!

Korollar (13) | Knotengrad avg <6

[!Korollar] Der avg Knotengrad in einfachen,planaren Graph ist <6 Der durchschnittliche Knotengrad in einem einfachen planaren Graphen ist $<6$ #card Ein Beweis liefert die Übung 115.82_uebung02

Beschrieben wird der AVG folgend: $$\frac{\sum _{v\in V}\mathrm{deg}(v)}{\mid V\mid }\le 6$$

-> kann in einer Zeile bewiesen werden!.

(14) Korollar |

[!Korollar] Korollar 14

Was gilt für einen planaren Graph bezüglich der Grade von Knoten? #card

Ein einfacher planarer Graph hat mindestens einen - genauer mind 3 - Knoten vom Grad höchstens 5.

Weiterhin hat dieser - logischerweise - keinen isolierten Knoten

Nicht Planare Graphen

Neben den planaren Graphen existieren auch solche, die es nicht sind - trotz, dass die Konstruktion eigentlich sehr schwer scheint, dass man nicht immer einen planaren Graphen zeichnen kann.

Als Beispiel dafür dienen etwa die vollständigen Graphen.

Satz (15) | bipartite Graphen, die nicht planar sind

[!Satz] $K_{3,3} K_{5}$ sind nicht planar #card Aus der Betrachtung heraus sind die beiden bipartiten Graphen vollständige bipartite Graphen $K_{3,3}$und$K_{5}$nichtplanar.>{>}_{W}iek\ddot{o}nnenwirdasbeweisen?!>>>\ast \ast Beweisen\ast \ast :>Daf\ddot{u}rk\ddot{o}nnenwir[Satz(12)Eigenschaft$G$mit$n geq 3$](#Satz%20(12)%20Eigenschaft%20$Gn%20geq%203$)anwenden,undeinfachdieKnoten/Kantenz\ddot{a}hlenunddannherausfinden,dasser\ast \ast nichtplanarist\ast \ast .>>Bei$K_{5}$wissenwir:>$n = 5, m = 10 \leq 3 \cdot 5-6 = 9$was\ast \ast nichtderVoraussetzungentspricht\ast \ast .>>Betrachtenwirjetztnoch$K_{3,3}$erhat:>$n = 6, m=9; 9 \leq 3 \cdot 6 - 9 =9$ und gilt somit ( obwohl er nicht planar ist). ( Also die Formel sagt nicht immer etwas darüber aus!).

Wir können stattdessen annehmen, dass er planar ist und dann schauen, ob das stimmt. Wir wissen noch aus Satz (9) Eigenschaft bipartiter Graph -> Bezug zu Kreisen, dass ein Graph bipartite ist, wenn er keinen Kreis ungerader Länge hat. Daraus können wir jetzt folgern, wie viele Facetten dieser haben würde: (das gilt für bipartite Graphen): -> In einer planaren Zeichnung muss jede Facette von mindesten 4 Knoten begrenzt sein. Ferner möchten wir dafür jetzt eine doppelte Abzählung der Kanten-Facetten-Inzidenzen (wie bei [Satz (12) Eigenschaft $G$mit$n geq 3$](#Satz%20(12)%20Eigenschaft%20$Gn%20geq%203$))betrachten.>Undwirk\ddot{o}nnen,wieobigdannwiederdiverseWerteund>Abh\ddot{a}ngigkeitenbetrachtenundresultieren:>$$\begin{array}{rlr}>2m& \ge 4f& \\ >2m& =18\ge 4f& \\ >& =4(m+2-n)=20& \text{ Eulers Formel einsetzen fu¨r }>f\\ >& =\text{ Widerpsruch},18\ngeqq 20>& \end{array}$$ Das heißt also wir können es dadurch zeigen, dass wir abzählen und ferner einsetzen, um die Werte berechnen zu können.

(wichtig für Aufgabe 2)

Lemma (16) | $G$planar$\implies$jederUntergraphvon$G$istplanar>[!Lemma]$G$istplanar$\implies$ alle untergraphen sind planar

Warum gilt das? #card

Das folgt aus der Betrachtung, dass das Entfernen einer Kante in einem planaren Graphen die Fähgikeit planar dargestellt zu werden nicht weiter beinflusst, da keine neue Kanten gewonnen werden, sondern nur vorhandene angepasst werden.

Satz von Kuratowski | Unterteilung

[!Bsp] Satz von Kuratowski:

Sei $G$einGraphund$e = uv$eineKantevon$G$.>{>}_{W}asistjetztf\ddot{u}rdieseKante$e$ möglich? Was können wir “Unterteilen”? Was gilt ferner für diese Knoten?_ #card

Wir können die Kante $e$nun\ast \ast unterteilen\ast \ast ,indemwirsiedurcheinen\ast \ast Weg\ast \ast$u,u_{1},\dots,u_{k,v}$unterteilen-->alsowirzerteilendieKanteundf\ddot{u}genneueKnotenundKantenein,dieunssomitmiteiner\ddot{a}quivalentenVerlaufresultierenlassen-hieraberdieKantenunaufgeteiltwurde.>>Fernergiltf\ddot{u}rdie\ast \ast neuenKnoten\ast \ast :$\deg(u_{i}) =2$indemGraphen.![](Pasted>[!Tip]Graph$H$=Unterteilungvon$G$

#card

Wir nennen jetzt einen Graphen $H$\ast \ast Unterteilung\ast \ast von$G$,wenndurchdieUnterteilunggewisserKantenderGraph$G$ entstehen kann.

Korollar (17) | Planar $\Longleftrightarrow$ jede Unterteilung ist planar

[!Korollar] Planar Folgerung

Was folgt für einen Graphen, der planar ist, und warum folgt das? #card

Sofern er planar ist $\Longleftrightarrow$jedeUnterteilungistplanar>>EinbeliebigerGraphist\ast \ast genaudann\ast \ast planar,wennjedeseinerUnterteilungen-diem\ddot{o}glichsind-planarist.>>Auchhiersehenwirwieder,dassdieUnterteilungenvon$K_{3,3},K_{5}$\ast \ast nichtplanarsind\ast \ast undsieessomitauchnicht!>>Warumfolgtdas?>>Schauenwiruns$K_{5}$ an, dann können wir durch Unterteilungen keine Planarität erhalten!

Auch wenn wir die neuen Kanten planar zeichnen können, wird das nicht funktionieren, weil man ja auch eine Jordan-Kurve ziehen könnte.

Satz (18) | Kuratowski | Planar $\Longleftrightarrow~ \not \exists$isomorpherGraphzu$K_{5},K_{3,3}$>WirdalseinerderwichtigstenS\ddot{a}tzebetrachtet-vonihr!AusderobigenBetrachtungundfernerderErkenntnis,dasswirsehrstarkbeweisenk\ddot{o}nnen,dass$K_{5},K_{3,3}$ nicht planar sind, können wir jetzt weitere Betrachtungen übernehmen:

[!Definition] Kuratowski | Satz (18)

Wann ist ein Graph planar? Im Bezug auf Unterteilungen! #card

Ein Graph $G$istgenaudannplanar,wenn$G$\ast \ast keinen\ast \ast zueinerUnterteilungvon$K_{5}\lor K_{3,3}$\ast \ast isomorphenUntergraphen\ast \ast enth\ddot{a}lt.>>(manm\ddot{u}sstealsoherausfindenk\ddot{o}nnen,obeinUntergrapheinesGraphen$G$)isomorphzueinerVarianteeinerUnterteilungvondenbeidenGraphenist.-->amschnellstenetwadurch\ddot{U}berpr\ddot{u}fungderQuantit\ddot{a}tderKnoten/Kanten>>DerBeweisistlang-ganzeVorlesung.Mankannsoetwazeigen,dassder\ast \ast Petersen-Graph\ast \ast ein\ast \ast Unterteilung\ast \ast von$K_{3,3}$ist:EswirdjedeKanteimmernur\ast \ast einmalgenutzt\ast \ast :unddannerh\ddot{a}ltmandie\ast \ast Unterteilung\ast \ast von$K_{3,3}$

es gibt noch eine alternative Beschreibung des Satzes ( welcher scheinbar viel öfter genutzt und angewandt wird). Man kann ihn also auch anders formulieren: Satz (20) Satz von Menger

Dieser kann uns dabei helfen ebenfalls eine Verkleinerung des Graphen und dadurch eine Ähnlichkeit zu einem $K_{5} \lor K_{3,3}$ Graphen finden zu können.

[!Definition] Satz Kuratowski | aber von Wagner

Unter Betrachtung des Satzes von Wagner, wann ist ein Graph planar? #card

Sei G ein einfacher Graph, dann gilt: G ist planar $\Longleftrightarrow$wennerkein\ast \ast Minor\ast \ast von$K_{5}, K_{3,3}$ ist Also gleiche Idee, aber andere Umsetzung der Idee. Hier durch die Kontraktion motivierte Komprimierung des Graphen, bis er einen der gesichert Nicht-Planaren Graphen entspricht