Anzahl aller möglichen Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Leute,
Es geht mir im folgenden um diese Diskussion.
Ich habe die dortigen Erklärungen damals sehr schön nachvollziehen können. Es gibt also [mm] $3^{\binom{n}{2}}$ [/mm] mögliche gerichtete Graphen bei $n$ Knoten, und [mm] $2^{\binom{n}{2}}$ [/mm] mögliche ungerichtete Graphen bei $n$ Knoten.
Im Moment suche ich jedoch noch andere kürzere Erklärungen für das obige Problem. Also Solche, die man irgendwie kompakt aufschreiben könnte.
Z.B. habe ich mir für [mm] $2^{\binom{n}{2}}$ [/mm] überlegt:
(1) Man betrachte die Potenzmenge aller $n$ Knoten.
(2) Es gibt insgesamt [mm] $\binom{n}{2}$ [/mm] Möglichkeiten aus Kanten durchs Verbinden (oder nicht Verbinden) von jeweils zwei Knoten durch eine Kante einen Graphen mit $n$ Knoten zu erstellen.
(3) Bedingung (2) gilt für alle Elemente von (1) (mit Ausnahme von [mm] $\emptyset$, [/mm] oder?). Also gibt es insgesamt [mm] $2^{\binom{n}{2}}$ [/mm] Möglichkeiten ungerichtete Graphen aus einer Menge von $n$ Knoten zu konstruieren.
Wäre eine solche Argumentation schlüssig? Und wenn ja, wie kann ich den bei gerichteten Graphen ähnlich argumentieren? Die 3er-Potenz erinnert einen ja nicht gerade an eine Potenzmenge, und der Alternativweg in der damaligen Diskussion ging über eine Summenbildung. Um auf [mm] $3^{\binom{n}{2}}$ [/mm] zu kommen, mußte man dieses Ergebnis zunächst raten (Ich habe damals eine Wertetabelle erstellt) und dann mit vollständiger Induktion beweisen.
Danke!
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:25 Sa 01.10.2005 | | Autor: | Frank05 |
> Ich habe die dortigen Erklärungen damals sehr schön
> nachvollziehen können. Es gibt also [mm]3^{\binom{n}{2}}[/mm]
> mögliche gerichtete Graphen bei [mm]n[/mm] Knoten, und
> [mm]2^{\binom{n}{2}}[/mm] mögliche ungerichtete Graphen bei [mm]n[/mm]
> Knoten.
> Im Moment suche ich jedoch noch andere kürzere Erklärungen
> für das obige Problem. Also Solche, die man irgendwie
> kompakt aufschreiben könnte.
War doch schon kompakt ueber die Summen.. ?
> Z.B. habe ich mir für [mm]2^{\binom{n}{2}}[/mm] überlegt:
>
>
> (1) Man betrachte die Potenzmenge aller [mm]n[/mm] Knoten.
Du willst doch die Anzahl der Graphen mit n Knoten. Nicht mit nur einer Teilmenge dieser Knoten. Sollen die Teilmengen irgendwie mit den Kanten in Zusammenhang stehen? Wenn ja, dann ist in keinster Weise klar wie.
> (2) Es gibt insgesamt [mm]\binom{n}{2}[/mm] Möglichkeiten aus Kanten
> durchs Verbinden (oder nicht Verbinden) von jeweils zwei
> Knoten durch eine Kante einen Graphen mit [mm]n[/mm] Knoten zu
> erstellen.
Der Satz ist ziemlich konfus. Und wie du ja schon weisst gibt es [mm]2^\binom{n}{2}[/mm] Graphen mit n Knoten. Wieso behauptest du jetzt etwas anderes?
> (3) Bedingung (2) gilt für alle Elemente von (1) (mit
> Ausnahme von [mm]\emptyset[/mm], oder?). Also gibt es insgesamt
> [mm]2^{\binom{n}{2}}[/mm] Möglichkeiten ungerichtete Graphen aus
> einer Menge von [mm]n[/mm] Knoten zu konstruieren.
Auch sehr konfus.. Also die Potenzmenge umfasst selbst schonmal [mm]2^n[/mm] Teilmengen. Wenn nun fuer jede dieser Teilmengen (2) gilt (wie auch immer (2) gemeint sein soll), dann heisst das [mm]2^n * \binom{n}{2}[/mm].
> Wäre eine solche Argumentation schlüssig?
Also ich kann in keinster Weise nachvollziehen was du da machst und wenn ich (2) richtig lese widersprichst du da deiner zu beweisenden Aussage.
Aber jetzt zu deiner eigentlichen Frage: Wie kann man das anders erlaeutern?
Einfaches Fakt ist, dass es [mm]\binom{n}{2}[/mm] moegliche Kanten gibt in einem Graphem mit n Knoten ohne Schleifen.
Wie sieht nun einer dieser Graphen mit n Knoten aus? Aus den [mm]\binom{n}{2}[/mm] Kanten sind k Kanten in diesem Graphen enthalten.
Ich habe die Erfahrung gemacht, dass es fuer Informatiker meist einfacher ist, sich das in Bits vorzustellen (wahrscheinlich, weil die meisten sich darueber schon mal mehr Gedanken gemacht haben). Also nehme man sich [mm]\binom{n}{2}[/mm] Bits. Wenn man jetzt diese Bits beliebig auf 0 oder 1 setzt, so entspricht das gerade einem Graphen und wir wollen somit wissen, wieviele Zahlen man mit Hilfe dieser Bits darstellen kann. 2 Moeglichkeiten fuer das erste Bit / fuer die erste Kante, fuer jede dieser Moeglichkeiten wieder 2 Moeglichkeiten fuer das zweite Bit, usw. Also [mm]2*2*2....*2 = 2^\binom{n}{2}[/mm].
Und nochmal was anderes: Im Originalthread ist bei der Antwort meiner Meinung nach ein Fehler gemacht worden. Nach der von dir angegebenen Definition sind in einem Graphen Schleifen explizit erlaubt. Die Antwort bezieht sich jedoch auf den Fall, dass es keine Schleifen gibt.
Betrachten wir also jetzt ungerichtete Graphen nach deiner Definition:
G heißt ungerichtet, wenn $ E := [mm] \left\{ \left\{ a,b \right\}\; | \; a,b \in V \right\} [/mm] $. (also evtl. auch $a=b$!)
Dann gibt es die bereits genannten [mm] $\binom{n}{2}$ [/mm] Kanten zwischen verschiedenen Knoten und dazu nochmal $n$ Schleifen, also insgesamt [mm] $\binom{n}{2}+n [/mm] = [mm] \frac{n*(n-1)+2*n}{2} [/mm] = [mm] \frac{n*(n+1)}{2} [/mm] = [mm] \binom{n+1}{2}$ [/mm] Kanten. Und somit ist die Anzahl der versch. Graphen mit n Knoten [mm] $2^\binom{n+1}{2}$.
[/mm]
Analog nochmal fuer den Fall von gerichteten Graphen:
G heißt gerichtet, wenn $ E := V [mm] \times [/mm] V $ und $ [mm] \forall [/mm] 1 [mm] \le [/mm] i < j [mm] \le \left| V \right| \, \forall v_i, v_j \in [/mm] V: [mm] \left( v_i, v_j \right) \in [/mm] E [mm] \Rightarrow \left( v_j, v_i \right) \notin [/mm] E $.
Man beachte, dass diese Definition etwas ungewoehnlich ist, da zwischen 2 Knoten somit nur eine Kante sein kann. Entweder in die eine Richtung oder in die andere. Insbesondere ist auch die Anzahl der Kanten fixiert auf $n*n$ Kanten, falls du nicht $E [mm] \subset [/mm] V [mm] \times [/mm] V$ gemeint hast! Da die nachstehende Bedingung aber sonst gar nicht erfuellt sein kann nehme ich hier einfach mal an, dass du eine Teilmenge gemeint hast.
Da Rueckkanten nicht erlaubt sind gibt es also maximal genausoviele Kanten wie beim ungerichteten Fall, nur dass diesesmal noch die Richtung eine Rolle spielt, d.h. fuer je zwei Knoten koennen wir uns jetzt eine von drei Moeglichkeiten aussuchen (von Kante oder nicht im ungerichteten Fall zu keine Kante oder Kante von a nach b oder Kante von b nach a). Analog zu der Auffassung mit den Bits oben ergibt sich somit fuer die Anzahl der Graphen mit dieser seltsamen Definition von gerichtet: [mm] $3^\binom{n+1}{2}$
[/mm]
Nachdem das aber nicht so sonderlich interessant ist betrachten wir das ganze einfach noch mit einer gaengigeren Definition von gerichteten Graphen:
$G = (V, E)$ mit $E [mm] \subset [/mm] V [mm] \times [/mm] V$ heisst gerichteter Graph.
Damit sind insbesondere jetzt 2 Kanten zwischen 2 Knoten moeglich: Hin- und Rueckkante.
Aber: Schleifen sind immer noch einfach zu zaehlen.
Somit ergibt sich fuer die neue Gesamtanzahl von moeglichen Kanten:
[mm] $\binom{n}{2}*2 [/mm] + n = [mm] \frac{2*n*(n-1)+2*n}{2} [/mm] = [mm] \frac{2*n^2}{2} [/mm] = [mm] n^2$
[/mm]
Und wir koennen nur noch waehlen, ob wir in einen Graphen eine solche Kante aufnehmen oder nicht (die Richtung ist schon durch den Faktor 2 bei der Kantenanzahl beruecksichtigt). Das Ergebnis lautet hier also: [mm] $2^{(n^2)}$
[/mm]
|
|
|
| |
|
Hallo Frank,
> Ich habe die Erfahrung gemacht, dass es fuer Informatiker
> meist einfacher ist, sich das in Bits vorzustellen
> (wahrscheinlich, weil die meisten sich darueber schon mal
> mehr Gedanken gemacht haben). Also nehme man sich
> [mm]\binom{n}{2}[/mm] Bits. Wenn man jetzt diese Bits beliebig auf 0
> oder 1 setzt, so entspricht das gerade einem Graphen und
> wir wollen somit wissen, wieviele Zahlen man mit Hilfe
> dieser Bits darstellen kann. 2 Moeglichkeiten fuer das
> erste Bit / fuer die erste Kante, fuer jede dieser
> Moeglichkeiten wieder 2 Moeglichkeiten fuer das zweite Bit,
> usw. Also [mm]2*2*2....*2 = 2^\binom{n}{2}[/mm].
Vielen Dank für die Anschauung mit den Bits! Jetzt ist es mir klar geworden. Wir betrachten eine Adjazenzmatrix $A [mm] \in \{0,1\}^{\left|V\right|\times\left|V\right|}$:
[/mm]
[mm]A := \begin{pmatrix}
{\color{red}a_{11}} & \hdotsfor{2} & a_{1n} \\
a_{21} & {\color{red}a_{22}} & \dots & a_{1n} \\
a_{n1} & \hdotsfor{2} & {\color{red}a_{nn}}
\end{pmatrix}[/mm]
Wie viele Elemente sind auf der Diagonale? Genau [mm] $n\!$ [/mm] Elemente. Da wir hier Graphen ohne Schleifen betrachten, zählen wir diese Elemente nicht. Übrigbleiben zwei symmetrische Teile von [mm] $A\!$. [/mm] Zusammen sind dies [mm] $n^2 [/mm] - n$ Elemente. Da wir ungerichtete Graphen betrachten, brauchen wir also nur eine Hälfte von [mm] $A\!$ [/mm] zu betrachten. Das sind genau [mm] $\tfrac{n^2-n}{2}$ [/mm] Elemente. Und jetzt zählen wir, wie Du schon gesagt hast, alle möglichen Bitpositionen indem wir hochzählen. Das sind dann genau [mm] $2^{\frac{n^2-n}{2}}$ [/mm] Möglichkeiten. Zählen wir die Schleifen mit, wären das zusammen mit der Diagonale [mm] $2^{\frac{n^2-n}{2}+n}$ [/mm] Möglichkeiten. Und so kann man auch die restlichen gerichteten Fälle durchspielen. Ich frage mich nur gerade, ob es auch möglich wäre den Fall [mm] $3^{\binom{n+1}{2}}$ [/mm] durch eine Adjazenzmatrix zu erklären.
Danke für deine Mühe!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:22 Sa 01.10.2005 | | Autor: | Frank05 |
> Ich frag'
> mich nur gerade, ob es auch möglich wäre den Fall
> [mm]3^{\binom{n+1}{2}}[/mm] durch eine Adjazenzmatrix zu erklären.
Ganz analog. Die Diagonale ist fuer Schleifen zustaendig. Damit bleiben [mm] $n^2-n$ [/mm] Eintraege. Die symmetrischen Eintraege ergeben sich von selbst, da bei deiner Definition ja nur eine Kante zwischen den beiden Knoten sein kann. Somit hast du fuer die Eintraege der Matrix wieder 3 Moeglichkeiten: 0 = keine Kante, [mm] $a_{ij}=1$ [/mm] heisst Kante von [mm] $v_i$ [/mm] nach [mm] $v_j$ [/mm] und der symmetrische Fall [mm] $a_{ji}=1 \Leftrightarrow a_{ij}=-1$ [/mm] fuer eine Kante von [mm] $v_j$ [/mm] nach [mm] $v_i$. [/mm] Die Rechnung fuer die Anzahl der Graphen bleibt die Gleiche jetzt eben mit 3 als Basis.
Unter der gaengigen Definition von gerichteten Graphen hast du sonst eben alle [mm] $n^2-n$ [/mm] Elemente der Matrix zur Verfuegung und die $n$ Diagonaleintraege. Auch hier gilt wieder je 2 Moeglichkeiten, also [mm] $2^{(n^2)-n+n}=2^{(n^2)}$
[/mm]
> Ist jetzt aber auch nicht so wichtig. Ich glaube, ich habe
> mich damals einfach mit der Definition vertan.
Definition ist Definition.. manchmal kann es ja auch gewuenscht sein, auf eine etwas andere Definition zurueckzugreifen. (Bei einer Uebungsaufgabe koennte man somit z.B. verhindern, dass jemand einfach eine Loesung fuer die uebliche Definition aus dem Netz abschreibt ohne etwas verstanden zu haben - schliesslich geht es bei so einer Aufgabe um die Herangehensweise und weniger um das konkrete Ergebnis)
|
|
|
|
