date-created: 2024-07-15 10:25:51 date-modified: 2024-07-15 10:58:08

Zusammenfassung | Wiederholung

[!Tip]

Beweisideen sind wichtig zu wissen, weil man hier die ungefähre Idee umsetzen oder betrachten zu können!

Daher diese Beweisideen nochmal anschauen!

Ober | Untergraphen

Eulerkreise:

-> Eulerkreis kann man algorithmisch finden: in $\mathcal{O}(n)$, da man einfach den Graph einmal algorithmisch durchläuft

Hamiltonsche Abschluss:

Einen Abschluss kann erzeugen, wenn man für jeden Knoten, wo die Eigenschaft von Ore-Dirac gilt dann noch so viele Knoten einfügt

von einem Graph mit n Knoten ist der kleinste Obergraph von $G$ für den $d_H(u)+d_H(v)<|V\mid$ für alle in $H$ nicht adjazenten Knoten $u,v$ gilt (dabei ist $d_H(x)$ der Grad des Knotens $x$ in H.)

Ore-Dirac:

Graphen-Darstellung

planare graphen kann man einbetten –> also eine ebene Zeichnung darstellen.

• Skelette sind planar

Eulers Formel

Allgemeine Formel: man hat mehrere Zusammenhangskomponenten

Ist wichtig, weil man damit bei gewisser algorithmischen Theorien eine gewisse Beschränkung des Aufwandes darstellen kann.

Kantenzusammenhang

[!Important] Relevant in der Forschung

Und man hat hier noch nicht soo viel erforscht –> daher lohnt es sich da hinein zu investieren!

Kantenfärbung

Kantenfärbung gibts nur zwei Möglichkeiten: Entweder die Färbung ist $\Delta (g)$ (maximalgrad) oder es ist $\Delta (G)+1$
–> Es gibt nur die zwei Möglichkeiten!