Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | Gegeben ist ein Paar $G = [mm] \left(V, E\right)$ [/mm] mit [m]V := \left\{ v_1,\ldots,v_n \right\}[/m], [mm] $\left| V \right| [/mm] < [mm] \infty$. [/mm] G nennen wir 'Graph'.
1.) G heißt ungerichtet, wenn [m]E := \left\{ \left\{ a,b \right\}\; | \; a,b \in V \right\}[/m]. Wieviele ungerichtete Graphen gibt es für [m]\left| V \right| = n[/m]?
2.) G heißt gerichtet, wenn [m]E := V \times V[/m] und [m]\forall 1 \le i < j \le \left| V \right| \, \forall v_i, v_j \in V: \left( v_i, v_j \right) \in E \Rightarrow \left( v_j, v_i \right) \notin E[/m]. Wieviele gerichtete Graphen gibt es für [m]\left| V \right| = n[/m]? |
Idee:
Beim zweiten Fall gibt es [mm] $2^n$ [/mm] Möglichkeiten, daß [mm] $n\!$ [/mm] Knoten eine Schleife besitzen oder nicht (entweder hat ein Knoten eine Schleife oder nicht). Für jede dieser [mm] $2^n$ [/mm] Möglichkeiten können zwischen den anderen paarweise verschiedenen Knoten des gerichteten Graphen drei Fälle auftreten:
Seien $a, b [mm] \in [/mm] V$ mit $a [mm] \ne [/mm] b$:
1.) [mm] $\left( a, b \right) \in [/mm] E [mm] \wedge \left( b, a \right) \notin [/mm] E$
2.) [mm] $\left( b, a \right) \in [/mm] E [mm] \wedge \left( a, b \right) \notin [/mm] E$
3.) [mm] $\left( a, b \right) \notin [/mm] E [mm] \wedge \left( b, a \right) \notin [/mm] E$
Also gibt es für die restlichen Knoten jedesmal [m]3^{\left| E \right| - n}[/m] Möglichkeiten, oder? Insgesamt gäbe es dann [mm] $2^n [/mm] * [mm] 3^{\left| E \right| - n}$ [/mm] mögliche gerichtete Graphen, richtig?
Für den zweiten Fall habe ich noch keinen wirklichen Ansatz. Vermutlich gilt dort auch [mm] $2^n [/mm] * [mm] \red{?}$.
[/mm]
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
Hallo Karl.
Zu den (ungerichteten) Graphen:
Hat der Graph n Ecken, so kann dieser höchstens m = [mm] \vektor{n \\ 2} [/mm] (n über 2) Kanten haben. (Wie oft kann man 2 VERSCHIEDENE Punkte auswählen und durch eine Kante verbinden?)
Für 0 [mm] \le [/mm] k [mm] \le [/mm] m gibt es wiederum [mm] \vektor{m \\ k} [/mm] verschiedene Graphen mit genau k Kanten. (Wie oft kann ich aus m möglichen Kanten k Stück auswählen?).
Die Gesamtzahl der (ungerichteten) Graphen mit n Ecken beträgt also
[mm] \summe_{k=0}^m \vektor{m \\ k} [/mm] = [mm] 2^m.
[/mm]
Nun zu den gerichteten Graphen (Digraphen)
Wieder hat der Graph höchstens m = [mm] \vektor{n \\ 2} [/mm] gerichtete Kanten. Da jede Kante aber zusätzlich eine Richtung hat ist die Anzahl der Digraphen mit genau k Kanten jetzt
[mm] 2^k* \vektor{m \\ k}
[/mm]
Damit beträgt die Anzahl der Digraphen mit n Ecken
[mm] \summe_{k=0}^n 2^k* \vektor{m \\ k} [/mm] = [mm] 3^m
[/mm]
|
|
|
| |
|
Hallo holy diver,
Danke für deine Antwort! Leider verstehe ich nicht, wieso man hier gerade die Kombinationsformel nehmen muß. Könntest Du mir vielleicht noch sagen, wie diese Aufgabe mit einem Urnenmodell modelliert werden kann?
Viele Grüße
Karl
|
|
|
| |
|
Zur Urne.
Wieso hat so ein Graph höchstes n über 2 Kanten?
Wir legen die n Ecken in eine Urne, und ziehen ohne zurücklegen 2 Ecken heraus. Diese verbinden wir dann durch eine Kante. Wie oft lassen sich nun aus n Elemente ohne zurücklegen 2 Stück herausnehmen? Naja, gerade n über 2 Mal.
Die Frage, wie viele Graphen mit genau k Kanten existieren lässt sich so fassen.
Wir haben eine Urne, in der sich die n über 2 Kanten befinden, die der Graph haben kann, daraus ziehen wir nun k Kanten ohne zurücklegen. Das ergibt m über k Kanten.
Was ist wenn wir einen Digraphen haben. Wir kennen bereits die maximale Kantenanzahl, und haben einen ungerichteten Graphen mit k Kanten bestimmt. Jetzt geben wir jeder Kante noch eine Richtung. Lege dazu die "Orientierungen" "vorwärts" und "rückwärts" in eine Urne, und ziehe mit Zurücklegen für jede Kante eine Orientierung heraus. Das macht dann [mm] 2^k [/mm] mögliche Orientierungen, um aus dem ungerichteten Graphen einen gerichteten zu machen. Das macht dann insgesamt
[mm] 2^k [/mm] * (m über k)
gerichtete Graphen mit genau k Kanten.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:21 Mi 01.06.2005 | | Autor: | Karl_Pech |
Hallo Holy Diver,
Danke für deine Hilfe!
Viele Grüße
Karl
|
|
|
|
