Begründen Sie, dass es 2^{\begin{pmatrix} n\\2\\ \end{pmatrix}} Möglichkeiten gibt, die Kantenmenge zu wählen.

Question

Kann jemand bitte mir helfen, ich konnte die Aufgabe nicht lösen... :/

Aufgabe:

Gegeben sei ein Graph G = (V,E) mit der Knotenmenge V = {1,...,n}.

(a) Begründen Sie, dass es \( 2^{\begin{pmatrix} n\\2\\ \end{pmatrix}} \)  Möglichkeiten gibt, die Kantenmenge zu wählen.
(b) Für n = 3: Wie viele dieser \( 2^{\begin{pmatrix} n\\2\\ \end{pmatrix}} \) Graphen sind bipartit? Wie viele der Graphen sind Bäume?

Ich bedanke mich sehr im Voraus.

lG

Answer 1

Für die a) kannst du für jedes ungeordnete Paar an Knoten entscheiden, ob eine Kante zwischen ihnen sein soll oder nicht (2 Möglichkeiten also). Es gibt insgesamt
\( \left(\begin{array}{l} n \\ 2 \end{array}\right) \)
solcher ungeordneter Paare, woraus die Formel folgt.

b) Kannst du eigentlich alleine hinbekommen, es gibt ja schliesslich nur 8 Graphen auf 3 Knoten, zeichne also all jene und schaue, wieviel Bäume und bipartite Graphen es unter ihnen gibt.