date-created: 2024-04-30 10:48:38 date-modified: 2024-07-02 11:11:50

Graphentheorie | Tutorium

anchored to 115.00_graphentheorie_anchor

Overview

Das Tutorium dient der Nachbearbeitung der Inhalte - des Übungsblattes und bietet somit die Möglichkeit fehler / Fragen etc stellen zu können. Ferner wird ermöglicht, zusätzliche Inhalte einsehen und verstehen zu können.

Platonische Körper

Platonische Körper 3D, Flächen sind alle reguläre, gleichseitige Dreiecke/$n$-Ecke $p$-gone: eine konvexe Struktur, die auf einem Kreis $p$ Punkte gleichverteilt darstellt und somit die Möglichkeit bietet, eine Struktur zu stellen. Konvex:nicht nach innen gerichtet, also gerade

[!Quote] Meisten Profs Die meisten Profs scheinen wohl die platonischen Körper in ihren Büros stehen zu haben, aber Lena nicht!

[!Question] Fragen: Wie viele kann man davon herstellen?

Wir wollen zeigen, dass es nur 5 geben kann!: Betrachten wir dafür folgende Grundparameter: $p$ Anzahl Kanten von einer Facetten - Facette ist konvexes $p$-gon) $f$ Anzahl aller Facetten $m$ Anzahl aller Kanten $n$ Anzahl aller Knoten $q$ Grad von den Knoten

Bei einem Würfel:

$p=4,f=6,m=12,n=8,q=3$

Es gilt ferner: $f\cdot p=2m$ –> Anzahl aller Facetten, da dann alle Kanten zählen und den Grad betrachten.

Wir können jetzt durch Anwendung der doppelten Abzählung die Kanten zählen. (dabei ist am Ende jede Kante doppelt gezählt)

$q\cdot n=2m$: Betrachten wir den Grad der Knoten und addieren die Anzahl der Knoten mit dieser, da wir so die Menge quantifizieren können.

Ferner noch

Wir können damit jetzt die mögliche Menge/Quantität von $P-$gonen beweisen: Dafür: $$\begin{array}{rlr}& \frac{2m}{q}+\frac{2m}{p}=m+2& \mid :2m\\ =& \frac{1}{q}+\frac{1}{p}=\frac{1}{2}+\frac{1}{m},& p\ge 3,q\ge 3\end{array}$$ Es muss nun gelten, dass $q=3\vee p=3$, denn sonst: $$\frac{1}{q}+\frac{1}{p}\le \frac{1}{4}+\frac{1}{4}=\frac{1}{2}<\frac{1}{2}+\frac{1}{m}$$ (Denn mit $\frac{1}{4}$ approxmieren wir, und können dann folgern, dass unser Wert kleiner 1/2 sein wird!)

Sei jetzt ferner $p=3$, dann ist $q\le 5$, denn sonst: $$\frac{1}{q}+\frac{1}{p}\le \frac{1}{3}+\frac{1}{6}=\frac{1}{2}<\frac{1}{2}+\frac{1}{m}$$ Analog gilt das auch für $p\le 5,q=3$

Daraus folgt nun: Es gibt nur folgende Kombinationen von $(p,q)$-Paare: $$\begin{array}{r}(3,3),(3,4),(3,5),(4,3),(5,3)\end{array}$$

[!Tip] Faszination Dieser Beweis ist wundebar, weil er Eulers Formel anwendet und in seiner Struktur gut aufgebaut und toll ist.

Ferner kann man dann diese $P-$gone auf diese Menge limitieren.

Graphen-Isomorphie

Graphen-Isomorphie ist bekannt $NP$ schwer, auch wenn man es noch nicht zeigen konnte.

Es kann ein $NP$ Problem sein, wo man nicht weiß, ob es $NP$ schwer ist.

[!Attention] 2015 kam entsprechend ein Algorithmus heraus, der das etwas zeigen konnte nature_2015_isomorph_graphs

Betrachten wir zwei Graphen, dann können wir - wie empfohlen - einfach die einfachen Parameter betrachten:

• Gibt es genauso viele Knoten,Kanten bei beiden Graphen?
• Ist die Verteilung der Grade gleich?

Man kann durch Probieren entsprechend eine Verteilung finden und erhalten.

[!Question] Wann spricht man von isomorphen Graphen und wann vom gleichen?

Wenn man einen gleichen Graph verschieden zeichnet, wird es der gleiche sein, auch wenn dabei eine Identitätsfunktion bzw. Permutation des Graphen. Das ist teils etwas schwamming, weil verschiedene Embeddings vom selben Graph so eventuell auch anders/ falsch erkannt werden kann..

Tutorial on DayPlanner-20240507

wir haben zwei Graphen betrachtet und gefragt, ob sie planar sind.

erster Graph:

\begin{document}

\begin{tikzpicture}
    \node[shape=circle,draw=black] (A) at (0,0) {A};
    \node[shape=circle,draw=black] (B) at (2,0) {B};
    \node[shape=circle,draw=black] (C) at (-1,1) {C};
    \node[shape=circle,draw=black] (D) at (3,1) {D};
    \node[shape=circle,draw=black] (E) at (3,2) {E};
    \node[shape=circle,draw=black] (F) at (-1,2) {F};
    \node[shape=circle,draw=black] (G) at (1,3) {G};

	\path [->] (A) edge node[left] {} (B);
	\path [->] (B) edge node[left] {} (C);
	\path [->] (B) edge node[left] {} (G);
	\path [->] (B) edge node[left] {} (D);
	\path [->] (A) edge node[left] {} (B);
	\path [->] (A) edge node[left] {} (G);
	\path [->] (A) edge node[left] {} (C);
	\path [->] (D) edge node[left] {} (F);
	\path [->] (D) edge node[left] {} (E);
	\path [->] (E) edge node[left] {} (F);
	\path [->] (E) edge node[left] {} (G);
	\path [->] (F) edge node[left] {} (G);
	\path [->] (F) edge node[left] {} (C);
	\path [->] (F) edge node[left] {} (A);
	\path [->] (G) edge node[left] {} (C);
\end{tikzpicture}
\end{document}

Das könnten wir am einfachsten herausfinden, indem wir die Menge von Kanten und Knoten betrachten und dann die Formel anwenden: Für den Graphen gilt: $n=7,m=16$ $m<3\cdot 7-6=15$

[!Tip] planarität schnell einfach finden Wir können die Formel relativ schnell anwenden,um so schnell rausfinden zu können ob ein Graph planar ist oder nicht.

Es war noch ein weiterer Graph gegeben, den wir auf Planarität prüfen wollten. Hierbei war dieser dann als $K_{3,3}$ unterteilbar.

\begin{document}
\begin{tikzpicture}

    \node[shape=circle,draw=black] (A) at (1,0) {A};
    \node[shape=circle,draw=black] (B) at (2,0) {B};
    \node[shape=circle,draw=black] (C) at (3,1) {C};
    \node[shape=circle,draw=black] (D) at (0,1) {D};
    \node[shape=circle,draw=black] (E) at (0,2) {E};
    \node[shape=circle,draw=black] (F) at (2,3.5) {F};
    \node[shape=circle,draw=black] (G) at (2,1.5) {G};
    \node[shape=circle,draw=black] (H) at (1,1.5) {H};
    \node[shape=circle,draw=black] (I) at (1.5,2.5) {I};


	\path [->] (A) edge node[left] {} (B);
	\path [->] (B) edge node[left] {} (C);
	\path [->] (C) edge node[left] {} (F);
	\path [->] (F) edge node[left] {} (E);
	\path [->] (E) edge node[left] {} (D);
	\path [->] (D) edge node[left] {} (G);
	\path [->] (D) edge node[left] {} (A);
	\path [->] (A) edge node[left] {} (H);
	\path [->] (H) edge node[left] {} (G);
	\path [->] (H) edge node[left] {} (I);
	\path [->] (I) edge node[left] {} (G);
	\path [->] (I) edge node[left] {} (E);
	\path [->] (I) edge node[left] {} (G);
	\path [->] (H) edge node[left] {} (F);
	\path [->] (G) edge node[left] {} (C);
\end{tikzpicture}
\end{document}

Wir können ihn jetzt in einen $K_{3,3}$ umschreiben, wenn wir ferner die Knoten $D,F,B$ nehmen und die Verbindungen dazwischen minimieren. Also wir sehen sie als Unterteilungen an und können dadurch dann so minimieren, dass der $K_{3,3}$ resultiert.

[!Question] Wie finden wir schnell heraus, ob wir ihn als planar oder als $K_{3,3}$ oder $K_5$ finden können? Es wird empfohlen kurz zu probieren, ob man einen Untergraph finden kann. Dabei relevant:

• bei vielen Kanten / Knoten: Formel anwenden
• vei vielen Kanten / Knoten: vermutlich einen K5 suchen
• sonst versuchen $K_{3,3}$ etc

Es wurde gefragt, wie man einen planaren Graphen am besten systematisch erstellen kann. –> Es wurde einfach ausprobieren und anschauen vorgeschlagen.

Eulers Formel | Induktion über Facetten

Wir wollen Satz (10) Eulers Formel nochmal induktiv beweisen:

betrachte Eulers Formel $n+f=m+2$

Wir wollen über Induktion über Facetten zeigen, dass die Formel gilt.

Induktionsanfang: Wir betrachten einen Graph mit nur einer Facette: Es handelt sich also um einen Baum: ( welcher zusammemhängend sein muss).

Wir wissen: Kanten eines Baumes : $n-1$

• Kanten $m=n-1$
• Facetten $f=1$
• somit gilt:
• $n+1=n-1+2⟺n+1=n+1$ passt.

Induktionsschritt: sei $G$ ein Graph mit $f>1$ Facetten. Sei $e$ weiter eine Kanten die $2$ Facetten trennt (betrachte man also einen Graph mit geschlossenem Kreis). Wir entfernen sie und somit: $G^{\prime }=G\setminus e$ hat jetzt $f^{\prime }=f-1$ Facetten und ferner $m^{\prime }=m-1$ (Kanten), wobei die Knoten unverändert bleiben $n=n$. Nach der IV gilt: $n^{\prime }+f^{\prime }=m+2=n+f-1=m-1+2⟺n+f=-2$

Sei $G=(V,E)$ mit $\mid |\ge 11$ Knoten und $G^{\prime }=(V,V\text{ u¨ber }2\setminus E)$ Zu Zeigen: nur einer der beiden Graphen kann planar sein.

Wir könnten hier die Formel anwenden um zu schauen, ob die Menge von Knoten / Kanten richtig ist, um dann die Formel $M\le 3n-6$ hat.

Betrachten wir, dass $G$ jetzt planar ist. Dann gilt dafür: $m\le 3n-6$ Somit folgt: $\mid E\mid =m,|V\mid =n$ Für den anderen Graphen $G^{\prime }$ gilt jetzt: $\mid E^{\prime }|=|v\text{ u¨ber }2-|E\mid =\frac{n(n-1)}{2}-|E\mid \ge \frac{n(n-1)}{2}-3n+6$ -> Eingesetzt und Binomialkoeffizent umgeformt! $=\frac{n^2}{2}-3,5n+6$ | Es handelt sich um eine Abschätzung, dass es also garantiert größer 28 ist. –> Das gilt für alles $\ge 11$ denn der Vergleich beider Terme wird durch eponentielles Wachstum garantiert größer wachsen: $$\frac{n^2}{2}-3,5n-6\le 3n-6$$

Ferner folgt jetzt: Sete $n=11$ Dann $\mid E^{\prime }|=28>3\cdot 11-6=27$ was ein Widerspruch ist | Es sollte aber planar sein und somit kleiner! (Ist es aber nicht) Also $\mid E^{\prime }\mid =28<3\cdot 11-6=27$

Es zu zeigen, dass es für $n\ge 11$ gilt, kann man nicht zwingend unter Betrachtung, dass der nachfolgende Graph ein Teilgraph sein muss - wo wir schon gezeigt haben, dass es nicht planar ist -. Daher ist es besser es einfach abzuschätzen, da wir hier allgemeiner Argumentieren können.

Paul Erdos: -> Das Buch der schönen Beweise | Book of Proofs

Tutorial on DayPlanner-20240514

Wir wollen den Beweis für den 115.05_Kontraktion Satz von Menger nochmal betrachten und ferner auf eine andere Weise herleiten - weil diese Struktur der Dozentin besser bzw intuitiver gefällt //

Wir owllen also wieder zwei Fälle betrachten: $\mid T\mid \ge |W\mid$ das ist klar und daraus folgt, dann entsprechend der Satz.

$\mid T\mid \le |W\mid$ ist schwieriger. Nehmen wir an, dass $\mid T\mid =k$.

Wir wollen über Induktion der Kanten einne Beweis führen:

Induktionsanfang: $M=0$, dann gilt: $\mid A\cap B|=l$ und es gibt $k$ triviale Wege.

Induktionsschritt: G hat Kante $(x,y)$, welche wir benötigen, um eine Kontraktion durchführen zu können.

Angenommen $G$ hat keine $k$ disjunkten $A-B$-Wege, dann hat auch der Graph kontrahiert mit einer Katne $e$ keinen. Also $G/e$

Betrachten wir $G/e$. Wenn jetzt $G/e$ $k$ disjunkte Wege hat, dann hat auch $G$ welche.

$G/e$ hat keine $k$ disjukte Wege, dann hat $G/e$ einen $A-B$ Trenner $Y$ wobei dieser $<k$ Knoten hat – was ja aufgrund der Induktionsvoraussetzung folgt(e). Ferner ist der kontrahierte Knoten $v_e\in V$. Dadurch folgt: $X=(Y\{\setminus v_e\cup \{x,y\}\})$ ist ein valider $A-B$ Trenner von $G$ mit $k$ Knoten.

Wir betrachten noch $G\setminus e$, denn in der Kontraktion wurde die Eigenschaft der disjunkten Wege zerstört (also weil wir vielleicht ieen vorherigen Pfad, der noch existierte, dadurch verloren haben, dass das Zusammenfassen von zwei Werten dazu führte, dass dann zwei Wege gekrezut werden).

Da $x,y\in X$, ist jeder $A-X$ Trenner in $G\setminus e$ auch ein $A-B$ Trenner in $G$ Dadurch folgt:

• $A-X$ Trenner hat eine Größe mit mindestens $k$
• Nach der Induktionsvoraussetzung haben wir auch mindestens $k$ disjunktive $A-X$ Wege in $G\setminus e$

Genauso gibt es $k$ disjunktive $X-B$ Wege in $G\setminus e$

DIese Wege treffen sich nur in $X$ - denn $X$ ist der A-B Trenner! und daher gilt dann: $k,\text{ disjunkte }A-B$ Wege in $G$

Grafisch etwa:

Nachbetrachtung Übungsblatt 02

Aufgabe 2

Durchschnittsgrad a

Durchnitssgrad ist: $\frac{\sum _{v}degv}{n}=\frac{2m}{n}$ Dann kann man mit Lemma betrachten: $\le \frac{2(3n-6)}{n}$ (n muss hierbei $\ge 3$ sein, sonst passt es nicht ganz) Für $n<3$ gilt es nicht mehr / trivial

b: Wenn es gelten würde, gilt nicht mehr a und somit ist es nicht mehr möglich

Anders zu beweisen: Wir gehen vom Mindestsgrad $=1$ aus: Angenommen $<3$ Knoten haben Grad $\le 5$. Dann gilt: $\sum _v\mathrm{deg}v\ge 6(n-2)+2\cdot 1=6n-10$, was aber $<3n-6$ sein sollte.Also $m\ge 3n-5$, was im Widerspruch mit $m\le 3n-6$ steht!

c Betrachten: ZZ keine Dreiecke bedeutet : $2m\ge 4f$, also $f=\frac{1}{2}m$ Unter Anwendung von Eulers Formel: $$\begin{array}{r}n+f=m+2\\ \frac{1}{2}m\le f=m-n+2\\ m\le 2n-4\end{array}$$

drittes Übungsblatt: Am SONNTAG abgeben! Aufgabe 1: wurde schon im Tutorium gemacht, überlegen, wie man es umsetzen kann // Wenn planar ist –> dann einfach zeigen Zusammenhangszahl einfach nur angeben.

Aufgabe 2: Zeigen von Äquivalenz /

[!Tip] Ihre Aufgaben sind nie witzlos!

b: nicht notwendigerweise

Aufgabe 3: muss nicht planar sein! Er muss nur einfach sein: alos kaum

Weitere Aufgabe:

Wir haben eine Platine mit 4 Baueelementen von Typ $A$ und 5 vom Typ $B$. Jedes Bauelement hat Anschlüsse für Leitungen auf beiden Seiten der Platine.

Unser Ziel Jedes Bauelement vom Typ $A$ mit jedem Element vom Typ $B$ verbunden werden, sodass sie keine 2 Leitungen kreuzen können.

Wie ist das Möglich: Wir können dafür einfach alle Leitungen von A nach B über die obere Seite der Platine.

Man könnte zuerst die Menge von Teilen durch 2 teilen (Menge der Seiten auf der Platine). Dann hat man einen kleineren Graphen, den man pro Seite betrachtet:

Dann kann man den halbierten Graph entsprechend austesten und anschließend noch den anderen auf der anderen Seite aufzeichnen. Für unser Beispiel dann etwa:

Tut on DayPlanner-20240528

comparing previous homework together: 115.83_uebung03

Aufgabe 2:

[!Attention] Beweis als Ring ist am sinnigsten (da alle äquivalent sein müssen)

Ferner hätten wir folgend argumentieren können: $$\begin{array}{rl}(i)& ⟹(ii)\\ (ii)& ⟹(iii):\neg (iii)⟹\neg (ii)\\ (iii)& ⟹(i)\end{array}$$ also: $(i)⟹(ii)$: $\mid E\mid =3\mid V\mid -6$ gilt, Angenommen jetzt gibt es eine neue Kante $(u,v)$ dann folgt aber $\mid E\mid =3|V\mid -5$ was im Widerspruch steht

$(ii)⟹(iii)$ $\neg (iii)⟹\neg (ii)$ Wenn eine Facette $>3$ Knoten enthält, kann dort noch eine Kante zwi 2 nicht adjazente Knoten eingefügt werden.

$(iii)\to (i)$ Auch hier wieder: $2\mid E\mid =3f$ ( bzgl der Facetten) durch Einsetzen in Eulers Formel folgt: $n+f=m+2$ $n+\frac{2}{3}m=m+2$ $m=3n-6$

[!Tip] Planarer Graph $⟹$ Graph kann auch geradlinig gezeichnet werden! Dafür gibt es entsprechende Algorithmen, die einen beliebigen planaren Graphen in einen geradlinigen umwandeln kann

Wir wollen noch Lemma 23 beweisen

Wir wollen also einen Beweis dazu führen:

Beweisen wir: $\lambda (G)\le \min \mathrm{deg}(v)$ ist klar. –> Löschen wir einfach alle Kanten, die inzident zum Knoten mit kleinstem Grad sind, dann haben wir entsprechend $\lambda (G)=\min \mathrm{deg}(v)$ ( und andere Fälle können halt spezifischer passieren, das ist nur worst-case)

Jetzt noch der zweite Teil: $K(G)\le \lambda (G)$ (Informelle Idee: Wir wollen einfach immer die Knoten bei einer Kante löschen, die die höheren Grade habe ( weil wir dann wissen, dass sie noch weitere Knoten haben und wir somit nicht den “zu trennenden Knoten” löschen)) Sei $E^{\prime }$ eine minimal trennende Kantenmenge $G$: zu Zeigen: $K(G)\le |E^{\prime }|$
Betrachten wir verschiedene Fälle:

Fall1: $G$ hat einen Knoten $v$, der zu keiner Kante aus $E^{\prime }$ inzident ist. Sei dann $C$ die Komponente $G\setminus E^{\prime }$, die $v$ enthält Die Knotenmenge aus $C$, die zu Kanten in $E^{\prime }$ inzident ist, trennt dann $G\setminus C$ Damit gilt der Standard-Fall, also dass die trennende Menge beim löschen nicht einfach die teilende Menge löschen würde ( weil wir noch ein weiteres $v$ haben) Somit gilt: $K(G)\le |E^{\prime }|$

Fall 2 – Tricky part Es gilt zu zeigen:

Jeder Knoten aus $G$ ist zu einer Kante aus $E^{\prime }$ inzident.

Beweis: Sei $v$ ein beliebiger Knoten und weiterhin $C$ die Komponente, die in $G\setminus E^{\prime }$ enthält. Alle Nachbarn $w$ von $v$ also $N(v)$ mit $(v,w)\notin E^{\prime }$ liegen dann in $C$.

Aus dieser Annahme folgen jetzt zwei Betrachtungen: Entweder: $deg(v)\le |E^{\prime }|:K(G)\le |E^{\prime }\mid$ oder wir haben den Fall, dass $v\cup N(v)=V$ ( also wenn wir die Nachbarn des Knoten betrachten, dann sind damit alle des Graphen gemeint –> wir haben also eine Verbindung zwischen allen Knoten/Graphen Gilt das, dann haben wir einen vollständigen Graphen und ferner gilt dann: $K(G)=\lambda (G)=|V\mid -1$

Sei $G=(V,E)$ ein 3 zusammenhängender Graph und weiterhin $e=(x,y)\in E$ eine Kante.

Wir wollen zeigen, dass $G/e$ ( kontraktiert e, also wird irgendwie gemerged) ist jetzt 3 zusammenhängend genau dann wenn $G\setminus e$ 2 zusammenhängend ist.

Beweis: (da äqui, beidseitig!)

Beweis: $⟹$ $G\setminus e$ ist zusammenhängend $⟹G/e$ ist 3zsh

Ist also $G\setminus e$ 2 zusammenhängend:

-> In $G$ gibt es zwischen 2 Konten $u,v$ drei kreuzungsfreie Wege, von denen nur eienr die Menge $\{x,y\}$ schneidet. ( ) –> das folgt schon daher, dass wir wissen, dass $G$ schon selbst 3-zsh ist! ( Und weil wir dann also die eine Kante wegnehmen, dann ist es nur noch 2zsh weil sie fehlt!)

Dann hat auch $G/e$ diese 3 kreuzungsfreien Wege und ist somit 3zsh!

(Informell: Aus der Vorbetrachtung haben wir am Anfang eine 3ZSH und entweder schneiden wir jetzt beim löschen der Kante diese Struktur, oder wir machen es nicht. Wenn wir sie schneiden bzw löschen haben wir einen weg weniger und sie ist somit definitiv 2ZSH, oder wir schneiden sie nicht, dann ist sie noch da –> Dann gilt also die Grundeigenschaft weiter und wird nicht verletzt)

Wenn keiner der drei Wege x oder y bewegt, ist alles gut.

Wenn es nur einer ist, passt das auch noch.

Beweis $⟸$ Sei $G/e$ jetzt auch 3zsh und ferner sind $u,v\in V\setminus \{x,y\}$ Dann igbt es jetzt in $G/e$ zwischen den Knoten $u,v$ 3 kreuzungsfreie Wege ( Voraussetzung mit dem neuen Knoten) wovon dann maximal einer über $v_e$ läuft –> das ist der kontrahierte Knoten, der bei der Kombination der beiden Knoten auftritt / passiert.

Es folgt dann, dass wir also 2 kreuzungsfreie Wege in $G/e$ haben ( dabei kann er auch weiterhin 3zsh sein, weil das inklusiv ist!)

[!Important] Diese Aussage gilt tatsächlich für alle Zusammenhängende Graphen $k,k-1$

Neuer Beweis der selben Aussage! )_

Beweis $⟹$ in G$k$ gibt es $3$ kreuzungsfreie Wege zwischen zwei Knoten $u,v$ von denen höchstens einer über $v_e$ läuft. Dadurch folgt: IN $G\setminus \{x,y\}$ gibt es mindestens 2 kreuzunfgsfreie Wegen zwischen $u,v$.

Beweis: $⟸$ Wenn es jetzt $G$ als 2zsm und ohne die Kante $\{x,y\}$ gibt, dann gibt es zu zwei Knoten $u,v$ 2 kreuzungsfreie Wege zwischen beiden. In G gibt es zu 2 Knoten $u,v$ 3 kreuzungsfreie Wege von Elemente höchstens $x,y$ oder beide bentutzt da $G\setminus xy$ 2 zsm ist Dadurch folgt $G/e$ gibt 3 kreuzunsgfreie Wege!

Übungsblatt: Aufgabe 1b mit Lemma 26 und dem obigen Beweis gut machbar

Aufgabe 2: Widerspruch versuchen?

Aufgabe 3: soll einfach sein.

[!Question] $\exists$ Funktion Gibt es eine Funktion $f:\mathbb{N}\to \mathbb{N}$, sodass ein Graph mit Minimalgrad $k$ (kleinster Grad im Graph) mindestens $f(k)$ $k$-zsh sind?

Wir suchen Graphen mit Zsm k und möchten dann wissen, ob dann dessen zusammenahng gemäß des minimalgrad-$k$ steht oder nicht.

Wenn 2-zsh Graph, dann soll mindestens 2 der Minimalgrad sein.

( Wenn wir einen Knoten betrachten, der von X nach Y verbunden ist, dann hat man darüber halt definitiv $k$ Wege, sodass das gelten muss!)

Nein das geht nicht, betrachten wir den $K_5$ 2-mal. also zwei davon unabhängig voneinander fliegend. Hierbei gilt: $K_{\frac{1}{2}}$ für jeden Graphen.

AAlso: Wir wollen über den Minimalgrad argumentieren, um herauszufinden, ob etwas $k$ zsh ist ( was nicht geht!)

Idee dann: hoher minimal-Grad aber dennoch nicht $k$-zsh ( kann mat mit einem Beispiel zeigen:

zeichne zwei $K_5$ die unabhängig voneinander sind. Dabie haben wir einen einzelnen Knoten, der beide verbindet ( mit hohem Grad).

Dadurch folgt jetzt: für $f(k=2)$ stimmt das nicht weil er nur 1 zsm ist!

–> Wir können also nicht darüber argumentieren, ob etwas $k$ zsm ist oder nicht

Maximal dass etwas maximal $k$ zsh ist ( weil wir maximal viele Verbindungen haben können).

Sei $G=(V,E)$ und $X\subseteq V$ und $a,b,\in G\setminus X$ wei durch $X$ getrennte Knoten.

Zeige, dass $X$ sit genau dann eine minimale $a-b$ trennende Knotenmenge, wenn jeder Knoten $v\in X$ auch in der Komponente $C_a$ von $G\setminus X$ die $a$ enthält, als auch in der Komponente $C_b$ - selbiges Prinzip - einen Nachbar hat.!

Graph G hat Knoten a und b in sich. Irgendwo ist ein Trenner $X$ und dann sagen wir. Wenn es ein Minimaler-Trenner ist, dann hat jeder Knoten aus dem Trenner eine Verbindung zu den getrennten Knoten ( eine Aussage die wir oft einfach angenommen haben,)

Beweis $⟸$ Angenommen x e X hat keinen Nachbar in Cb Dann können wir den Knoten x aus dem Trenner entfernen weil er keinen Mekrwert liefert

Das heist: X’ = X ohne X trennt auch a/ b. Das ist analog für Komponente a.

Wenn wir. Einen Trenner haben und ein Knoten, der Nachbar in a und b hat, dann folgt, dass ohne diesen Knozen kein Trenner mehr vorliegt, er also essentiel für den Trenner ist.

Bedingung ist, dass sie unterschiedliche Nachbarn haben –> damit es global gilt.

Sonst geht es um einen minimalen Trenner von X ( kleinste Menge )

Meist nutzen wir aber nur die erste Richtung oft, weil sie über Existenz von Nachbarn spricht

Termin am DayPlanner-20240611

Wir bestimmen die chromatische Zahl des Würfelgraphen $Q_2$, wobei dieser immer $2^n,n\cdot 2^{n-1}$ Kanten!

Beim $Q_2$ sind es nur 2 Farben

Beim $Q_5$ sind es auch wieder 2

Wir wollen zeigne dass $Q_n$ bipartit ist.

Beweis: Knoten können mit $n$-Tupel aus $\{0,1\}$ dargestellt werden und es gibt eine Kante zwischen zwei Knoten, wenn sich die Tupel an genau einer Stelle unterscheiden ( also ungleich sind!) Wir teilen dann $V=X\vee Y$. Dabei enthält $X$ alle Knoten mit gerade Anahl von $1$sen und übens die ungerade Anzahl von $0$sen. Es gibt nur Kanten zwischen $Y,X$.

[!Attention]

Tatsächlich rechnen sich die 30ECTS pro Semester auf das ganze halbe Jahr, wobei dann also die 2 Monate Pause auch mit reinzählen.

Da wir ja aber nur 14 Wochen haben, wo sich das ganze verteilt, sind das tatsächlich keine 40hr Wochen, sondern eher 60hr xd

Termin am DayPlanner-20240618

Kantenfärbung ist ${\mathcal{X}}^{\prime }(G)$!

Betrachten wir einen $G=(V,E)$, welcher ein $k$-regulärer Graph ist.

Zu Zeigen, dass, wenn $G$ einen Schnittknoten hat, dann ist ${\mathcal{X}}^{\prime }(G)\ge k+1$ (für Knotenfärbung wäre das einfach), aber wir betrachten hier Kantenfärbung:

Der Term der Schnittknoten bereitet Verwirrung, daher folgend die Definition / Idee eines solchen Knotens.

Wir wollen diese Aussage ferner unter Anwendung des Widerspruches lösens: Angenommen wir haben Kantenfärbung ${\mathcal{X}}^{\prime }(G)=k$, also mit $k$-Farben. Ferner betrachten wir etwa einen Knoten, dann muss dieser genau $k$-Farben haben, denn er hat ja $k$-Kanten, die an diesem sind. (Dass es $\ge k$ sein muss, folgt aus Lemma 23!)

Wir betrachten jetzt $G\setminus v$ ohne den Schnittknoten - welcher den Graphen komplett trennen kann. Dieser besteht dann aus $\ge 2$ Komponenten - weil wir ja getrennt haben.

Wir wissen, dass dieser Knoten $v$ dann zu beiden Komponenten verbunden sein muss und ferner eine Farbe aufweisen muss! Sei dann etwa die Farbe $c_1$ die den Knoten $v$ mit der Komponente $C_1$ verbinden kann.

Wenn wir diese jetzt entfernen und ferner schauen, wie viele Knoten in der Komponente $C_1$ dann noch die Farbe 1 und weiter eine Farbe 2 $c_1,c_2$ aufweist ( hierbei ist wichitg, dass $c_2\in C_2$ also garantiert in der anderen Komponente ist!), dann können wir über die Nachbar*innen von diesem Knoten sagen, dass diese diese beiden Farben enthalten, aber unser spezifischer Knoten selbst hat dann eine der Farben nicht –> Dadurch ist er der einzige Knoten mt ungeradem Grad und somit ist es kein valider Graph –> wie wir ganz am Anfang gezeigt haben.

Sei ein adjazenter Knoten zu $v$ $C_1,u\in C_1$ und die Farbe für die Kante $(u,v)$ sei dann $c_1$. Ferner betrachten wir noch einen anderen Knoten $w\in C_2,$ adjazent zu $v$

selbiges für Farbe 2

Erstelle jetzt den Teilgraphen H in C1 der alle Kantn mti Farbe 1u und 2 enthlat, dann ist aber der betrachtete Knoten von ungeradem Grad und gleichzeitig der einzige mit dieser Eigenschaft –> damit ist der Teilgraph kein valider Graph!

Fußball-Aufgabe

Das einzige Interessant am Fußball!

Betrachten wir einen Fußball, dieser hat schwarze 5-Ecken und weiße 6-Ecke.

An jeder Ecke eines solchen $5$-Ecks oder 6-Ecks treffen sich genau 1x 5-Eck und 2x 6-Ecken

Wir können diese Struktur als Planaren Graphen betrachten! Und weil er planar ist, können wir dann eulers Formel anwenden! ($n+f=m+2$)

Wir müssen die Menge von Kanten erörtern –> jedes Hexagon gibt 6 Kanten und jedes Fünfeck gibt uns 5 Kanten. Da wir sie ja dann “mergen” und, wenn wir alle abzählen, somit jede Kante zweimal gezählt haben, folgt:

$$m=\frac{5\cdot S+6\cdot W}{2}$$ und wir wissen, dass jeder Knoten vo Grad 3 ist, da jeweils eine Kante eines Hexagons, und 2 Fünf-Ecken in diesen hinein-verläuft! es ist also ein $k=3$ regulärer Graph!

bestimmen wir noch $n$: $$3n=2m⟹n=\frac{5S+6W}{3}$$

es folgt für die eulersche Formel dann jetzt: $$\frac{5S+6W}{3}+S+W=\frac{5S+6W}{2}+2$$ Wenn wir das umformen, kommt heraus; $S=12$ Man hat also 12 schwarze Fünfecke, dann stellt sich die Frage, wie viele weiße Sechsecke man brauch.

Das können wir über die Menge von Ecken bei den 5-Ecken abzählen. Wir wissen, dass sie immer ein 5-Eck und 2-Sechecken aufweisen und ferner, da wir die Menge von $5$-Ecken kennen, können wir dann auflösen: $$n=60=\frac{5S+6W}{3}=\frac{60+6W}{5}=20+2W$$ somit $40=2W$ und somit $w=20$!

Übungsaufgabe 5:

Wir sollten $a,b$ für $s,t$ wählen.

Besprechung von Übung 4

Termin am DayPlanner-20240625

Fortsetzung Aufgabe 2

betrachte eine Induktion über $k$:

IA der Anfang wäre etwa: $k=2$

• Für jedes Knotenpaar $(u,v)$ gibt es einen Kreis - (siehe 1a)
• Da $2-zsh$ gibt es zwei kreuzungsfreie Wege zwischen $u$ und $v$, also damit ist es auch ein Kreis

IS: $k\to k+1$ G ist $k+1$-zsh und damit auch $k-$zsh Betrachte Knoten $v_1,v_2,\dots ,v_k,v_{k+1}$ Aufgrund der Induktionsvoraussetzung folgt: $v_1,v_2,\dots ,v_k$ (also eine Teilmenge der Knoten, obig) auf einem gemeinsamen Kreis $C$. Aufgrund des Satzes von Menger folgt dann: Betrachten wir die $k+1$-disjunkten Wege zwischen $N(v_{k+1})$ und $C$ (Gemäß Satz (20) Satz von Menger müssen es $k+1$ disjunkte Wege sein!) (Also wir betrachten einen gebildeten Kreis - welcher existieren muss nach IV, und weiterhin schauen wir eine neue Menge an, die wir hier anschließen wollen und somit betrachten wir zwei Mengen).

–> hier kann $v_{k+1}$ über die gefundenen Wege eingefügt werden und somit der Kreis erweitert

Sofern jetzt gilt $$\mid C\mid <k+1$$ also wir haben einen Kreis konstruiert, welcher kleiner ist, und wollen ihn entsprechend erweitern:

Die Argumentation ist gleich, jedoch “in die andere Richtung”

Aufgabe:

[!Question]

Zeige, dass ein Baum höchstens einen 1-Faktor besitzt. (Genauer nur einen spezifischen 1-Faktor!)

Aus der ersten Betrachtung können wir folgern:

• Sofern die Menge der Knoten ungerade ist, kann es keinen 1-Faktor geben Ferner müssen wir alo die Blätter (meistens) betrachten, weil wir da herausfinden werden, dass ein Knoten über dem Blatt eigentlich gar kein zweites Blatt habne kann ( sonst geht es schon gar nicht mehr!)

Wenn wir bei einem Blatt entsprechend eine Kante finden, kann der Baum u.U. anschließend in verschiedene Subbäume zerfallen.

In diesen können wir dann wieder prüfen, ob sie die Eigenschaften aufweisen.

(weitere Idee: Angenommen man hat 2 1-Faktorisierung, dann gibt es also 2 Faktoren und wenn man eine Faktorisierung anschaut, dann gibt es garantiert eine Kante, die noch nicht gefärbt ist und das steht im Widerspruch, weil dann )

Beweis durch Induktion: Wir haben zwei Anfänge:

• 1 Knoten -> hat keinen 1-Faktor
• genau 2 Knoten ( sind gebunden durch eine Kante)

Induktionssschritt: $n>2$

Bestimmen wir ein beliebiges Blatt $v$, und fügen die inzidente Kante von $v$ zum 1-Faktor hinzu. Lösche beide Enden der kante

-> es entsteht dadurch ein (oder auch mehrere Bäume) mit $<n$ Knoten.

Nach der IV hat jeder dieser Teilbäume höchstens einen 1-Faktor! (Und somit haben wir also genau bestimmt)

Beispiel | Satz von Hall

betrachten wir ein Beispiel für die Aussage, die vom Satz-Von-Hall:

Betrachten wir einen Kontext, wo $n$ Personen $k$ Jobs zugeteilt werden sollten.

Wir können ein Gegenbeispiel finden, wo die Aussage nicht funktioniert, weil Job $J_3$ von $P_1,P_5$ belegt wird und ferner ist somit schon kein Matching möglich.

Satz (39) Satz von Hall (bipartite Graphen)

Zusätzliche Aufgabe

[!Question] Gegeben ist ein bipartiter Graph $G=(V,E)$

wir sagen, eine ungematchte Kante ist eine Kante, welche in keinem der perfekten Matchings vorkommt.

Gib einen Algorithmus an, welcher alle ungematchten Kanten bestimmt.

Mam könnte jedes perfekte Matching finden und anschließend die $\Delta$ Menge dieser perfekten Matchings bilden, damit haben wir alle ungenutzten Kanten!

Termin am DayPlanner-20240702

1. Besprechung von Übungsaufgabe 115.85_uebung05

• Lösungen wurden vorgestellt

[!Example] Aufgabe

Seien $n,k$ natürliche Zahlen mit $2k\le n$ also $n=2k+d$, für $d\ge 0$

Ein Kneser Grpah $K(n,k)$ ist folgendermaßen definiert: 1, Knotenmenge $V(n,k)$ ist eine Familie von $k-$elementigen Untermengen $\{1,\dots ,n\}$, also $\mid V(n,k)\mid =\left(\genfrac{}{}{0ex}{}{n}{k}\right)$

2 Knoten $2-k$ elementige Mengen, $A,B$ sind adjazent wenn $A\cap B=\varnothing$

1. Wie sieht dann $K(5,2)$ aus?
2. Zeige ${}_{\mathcal{X}}(K(n,k))\le n-2k+2=d+2$

Der Graph ist gleich dem Petersson-Graph! Bild

Wir wollen die Färbung folgend konstruieren:

Wir bilden Mengen $V_i$ die alle k-elementigen Mengen mit $i$ als dem kleinsten Element enthalten. Dabei bekommt dann $V_i$ die Farbe $i$ zugeteilt!

Wir haben jetzt noch übrige Elemente, die wir in einer Menge zusammenfassen wollen. Die Elemente wären demnach: $\{d+2,d+3,\dots ,2k+d\}$. Die Menge enthält dadurch dann noch $2k-1$ Elemente.

Die restliche Mengen sind nicht disjunkt und somit sind sie auch nicht adajzent im Graphen selbst! –> wir geben ihnen also die Farbe $d=2$!

und somit haben wir den Graphen gefärbt

Termin am DayPlanner-20240716

Beweis von : $2m=\sum _v(deg(v))\ge (k-1)\cdot n$

Annahme: Minimalgrad $<k-1$: Sei $v$ ein Knoten mit $deg(v)<k-1$

dann ist die Färbung: $\chi (G\setminus v)=k-1$ da $G$ k-kritisch ist: Betrachte diese Färbung von $G\setminus v$. Da $v$ höchstens $k-2$ Nachbarn hat, ist eine Farbe für $v$ übrig und somit $G$ ist $k-1$ färbbar –> Was im Widerspruch steht!

Aufgabe 2: Block-Graph bilden: Was bissschen anders zur Definition ist und man somit da Probleme hätte bekommen können.

Aufgabe 4:

Kann man auf zwei Arten argumentieren / lösen:

Betrachte die optimale Färbung die teilt die Knoten in Menge $V_i$ mit Farbe $i$:

Alle Kanten in $V_i$ sind dabei unabhängig und ferner $max|V_i\mid \le \alpha (G)$ und somit folgt: $\ge \alpha (G)-\chi (G)\ge \chi (G)\cdot max|V_i|\ge n$ $\chi (G)\ge \frac{n}{\alpha (n)}$