[Graphentheorie] Dreiecke im Komplementgraphen

26.05.2019, 18:11

MaPalui

[Graphentheorie] Dreiecke im Komplementgraphen

Schönen Sonntag an alle smile

ich beschäftige mich einer Aufgabe aus der Graphentheorie. Hier kommt sie:
[attach]49287[/attach]

Leider komme ich schon bei (a) nicht wirklich weiter.
Vollständige Induktion wird hier wohl nicht funktionieren, da mit einem hinzukommenden Punkt die Kanten des Ausgangsgraphen nicht bestehen bleiben.
Ich weiß aber nicht, wie ich sonst an die Aufgabe rangehen kann. Klar, $\begin{eqnarray*} \begin{pmatrix}n\\3\end{pmatrix} \end{eqnarray*}$ ist die Anzahl der Möglichkeiten, drei Knoten zu wählen.
Nun müssen aber ja diese nicht zwingend ein Dreieck bilden, wenn keine Kanten zwischen ihnen bestehen.

Weiter weiß ich leider nicht verwirrt

26.05.2019, 18:29

HAL 9000

Auf diesen Beitrag antworten »

Für mich stellt sich als erstes die Frage, wie die Werte $\begin{eqnarray*} n,k \end{eqnarray*}$ mit $\begin{eqnarray*} V,E \end{eqnarray*}$ zusammenhängen: Womöglich $\begin{eqnarray*} n=|V|,k=|E| \end{eqnarray*}$ ? verwirrt

Mag für dich vielleicht eine selbstverständliche Vereinbarung sein - für mich ist es das nicht, und im Text fehlt es auch komplett.

P.S.: Und was ist mit $\begin{eqnarray*} r \end{eqnarray*}$ ?

26.05.2019, 19:26

MaPalui

Auf diesen Beitrag antworten »

Hallo HAL 9000, danke für deine Zeit.

Zitat:

Original von HAL 9000
Für mich stellt sich als erstes die Frage, wie die Werte $\begin{eqnarray*} n,k \end{eqnarray*}$ mit $\begin{eqnarray*} V,E \end{eqnarray*}$ zusammenhängen: Womöglich $\begin{eqnarray*} n=|V|,k=|E| \end{eqnarray*}$ ? verwirrt

Mag für dich vielleicht eine selbstverständliche Vereinbarung sein - für mich ist es das nicht, und im Text fehlt es auch komplett.

Mein Fehler das nicht anzugeben. Ja, zumindest in der Vorlesung ist das unsere übliche Konvention.

Zitat:

Original von HAL 9000
P.S.: Und was ist mit $\begin{eqnarray*} r \end{eqnarray*}$ ?

Darüber habe ich leider auch keine weitere Auskunft. Aber ich finde gerade im Skript:

Zitat:

Für einen r-regulären Graph G gilt r|V | = 2|E|.

Das hatte ich vorher nicht bedacht.

Neue Frage »

Antworten »

[Graphentheorie] Dreiecke im Komplementgraphen

Verwandte Themen