Maximale Anzahl Wege in einem Graphen

15.01.2011, 01:14

Legostein

Maximale Anzahl Wege in einem Graphen

Ich habe Fragen zur folgenden Überlegung, die im Buch "Mathematik für Informatiker Band 1 Diskrete Mathematik und lineare Algebra" von Gerald Teschl und Susanne Teschl geäußert wird.

"In einem Graphen mit n Knoten kann ein nicht-geschlossener Weg maximal die Länge n-1 haben. Es gibt also nur endlich viele Wege. Allerdings kann es im schlimmsten Fall $\begin{eqnarray*} \frac{n!}{(n-m)!2} \end{eqnarray*}$ Wege der Länge m-1 geben (die Anzahl der Möglichkeiten, die m Knoten des Weges aus allen n Knoten auszuwählen, geteilt durch 2, da die Durchlaufrichtung keine Rolle spielt).

Insgesammt gibt es also $\begin{eqnarray*} \sum_{m=1}^{n-1}= \frac{n!}{(n-m)!2}=\frac{n!}{2}\sum_{m=1}^{n-1}\frac{1}{m!} \end{eqnarray*}$ Wege."

1)"die Anzahl der Möglichkeiten, die m Knoten des Weges aus allen n Knoten auszuwählen" - Ist das nicht $\begin{eqnarray*} \binom {n}{m}=\frac{n!}{(n-m)!*m!} \end{eqnarray*}$ ?

2) Wieso steht über dem Summenzeichen n-1 und nicht n?

3) $\begin{eqnarray*} \sum_{m=1}^{n-1}= \frac{n!}{(n-m)!2}=\frac{n!}{2}\sum_{m=1}^{n-1}\frac{1}{m!} \end{eqnarray*}$ Diese Umformung kann ich nicht ganz nachvollziehen.

Klar ist mir: die $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ kann ich vor das Summenzeichen ziehen weils ein Faktor ist, aber warum auch das $\begin{eqnarray*} n! \end{eqnarray*}$ , bzw. wieso bleibt dann noch $\begin{eqnarray*} \frac{1}{m!} \end{eqnarray*}$ übrig?

16.01.2011, 00:13

Legostein

Auf diesen Beitrag antworten »

Bzgl. 2): Ich vermute, dass es nur um die Anzahl der nicht-geschlossenen Wege geht, und deswegen die maximale Knotenanzahl - 1 betrachtet wird.

Kann mir jemand zu 1) und 3) helfen?

16.01.2011, 09:10

Huggy

Auf diesen Beitrag antworten »

RE: Maximale Anzahl Wege in einem Graphen

Zitat:

Original von Legostein
1)"die Anzahl der Möglichkeiten, die m Knoten des Weges aus allen n Knoten auszuwählen" - Ist das nicht $\begin{eqnarray*} \binom {n}{m}=\frac{n!}{(n-m)!*m!} \end{eqnarray*}$ ?

Bei den Wegen kommt es doch auch auf die Reihenfolge an, in der die Knoten gewählt werden.

Zitat:

2) Wieso steht über dem Summenzeichen n-1 und nicht n?

Hast du diesen Satz von weiter oben überlesen oder nicht verstanden:

Zitat:

In einem Graphen mit n Knoten kann ein nicht-geschlossener Weg maximal die Länge n-1 haben.

Zitat:

3) $\begin{eqnarray*} \sum_{m=1}^{n-1}= \frac{n!}{(n-m)!2}=\frac{n!}{2}\sum_{m=1}^{n-1}\frac{1}{m!} \end{eqnarray*}$ Diese Umformung kann ich nicht ganz nachvollziehen.

Klar ist mir: die $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ kann ich vor das Summenzeichen ziehen weils ein Faktor ist, aber warum auch das $\begin{eqnarray*} n! \end{eqnarray*}$ , bzw. wieso bleibt dann noch $\begin{eqnarray*} \frac{1}{m!} \end{eqnarray*}$ übrig?

Na, n! hängt doch auch nicht von dem Summationsindex m ab.
In der verbleibenden Summe führst du i = n -m als neuen Summationsindex ein, überlegst dir, über welchen Bereich i läuft und da die Bezeichnungen von Summationsindizes Schall und Rauch sind, benennst du i zum Schluss wieder in m um.

16.01.2011, 11:22

Legostein

Auf diesen Beitrag antworten »

RE: Maximale Anzahl Wege in einem Graphen

Zitat:

In der verbleibenden Summe führst du i = n -m als neuen Summationsindex ein, überlegst dir, über welchen Bereich i läuft und da die Bezeichnungen von Summationsindizes Schall und Rauch sind, benennst du i zum Schluss wieder in m um.

$\begin{eqnarray*} \sum_{m=1}^{n-1} \frac{n!}{(n-m)!2}=\frac{n!}{2}\sum_{i=n-m}^{?}\frac{1}{n-(n-m)}=\frac{n!}{2}\sum_{i=n-m}^{?}\frac{1}{m!} \end{eqnarray*}$ Ist so die Umformung korrekt?

Ich bin mir nicht sicherm ob bzw. bis wohin ich jetzt die Summationsgrenze verändern muss. Bei i=n-m fehlen doch jetzt mitunter die Möglichkeiten Wege mit einem, zwei Knoten usw... ?

Zitat:

Original von Huggy

Zitat:

Bei den Wegen kommt es doch auch auf die Reihenfolge an, in der die Knoten gewählt werden.

"Ist das einfach so" (im Sinne von, dass umfassende Vorüberlegungen notwendig wären, um zu verstehen, wie man auf die Forme kommt), dass ich deswegen dann nicht mehr doch "m!" teilen muss, oder kann ich mir, wie man auf die entstehende Formel kommt, irgendwie anhand ein paar Beispielen klarmachen?

16.01.2011, 11:49

Huggy

Auf diesen Beitrag antworten »

RE: Maximale Anzahl Wege in einem Graphen

Zitat:

Original von Legostein
Ich bin mir nicht sicherm ob bzw. bis wohin ich jetzt die Summationsgrenze verändern muss. Bei i=n-m fehlen doch jetzt mitunter die Möglichkeiten Wege mit einem, zwei Knoten usw... ?

Mir scheint, du verstehst das Prinzip nicht. Zu jedem Wert des alten Summationsindexes gehört genau ein Wert des neuen Summationsindexes. Da geht nichts verloren. Du musst dir nur die neuen Grenzen überlegen. Du hast

$\begin{eqnarray*} \sum_{m=m_u}^{m_o}... \end{eqnarray*}$

Jetzt betrachtest du den Summationsindex i = n - m. Die Summe laute dann

$\begin{eqnarray*} \sum_{i=i_u}^{i_o}... \end{eqnarray*}$

Die Grenzen für i bekommst du aus:

$\begin{eqnarray*} i_o=n-m_u \quad i_u=n-m_0 \end{eqnarray*}$

Zitat:

Original von Huggy

Zitat:

Bei den Wegen kommt es doch auch auf die Reihenfolge an, in der die Knoten gewählt werden.

Zitat:

Die Auswahl von k Objekten aus n unter Beachtung der Reihenfolge ist ein Standardproblem der elementaren Kombinatorik. Die Lösung ist einfach. Für das erste Objekt hast du n Möglichkeiten, für das 2. Objekt n - 1 Möglichkeiten und schließlich für das k. Objekt noch n - k +1 Möglichkeiten. Also:

$\begin{eqnarray*} n(n-1)...(n-k+1) \end{eqnarray*}$

Und das kann man schreiben als

$\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$

16.01.2011, 12:37

Legostein

Auf diesen Beitrag antworten »

RE: Maximale Anzahl Wege in einem Graphen

Zitat:

Original von Huggy
Mir scheint, du verstehst das Prinzip nicht. Zu jedem Wert des alten Summationsindexes gehört genau ein Wert des neuen Summationsindexes. Da geht nichts verloren. Du musst dir nur die neuen Grenzen überlegen. Du hast

$\begin{eqnarray*} \sum_{m=m_u}^{m_o}... \end{eqnarray*}$

Jetzt betrachtest du den Summationsindex i = n - m. Die Summe laute dann

$\begin{eqnarray*} \sum_{i=i_u}^{i_o}... \end{eqnarray*}$

Die Grenzen für i bekommst du aus:

$\begin{eqnarray*} i_o=n-m_u \quad i_u=n-m_0 \end{eqnarray*}$

Die Formel für die Änderung der Grenzen sodass der Intervall-Abstand gleichbleibt meine ich nun verstanden zu haben, aber das nichts verloren geht, bzw., dass sich die Summe nicht ändert, verstehe ich noch nicht... - ich meine z.B. bei $\begin{eqnarray*} \sum_{i=1}^{3} n^2 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=2}^{4} n^2 \end{eqnarray*}$ kommt doch auch was anderes raus

16.01.2011, 13:02

Huggy

Auf diesen Beitrag antworten »

RE: Maximale Anzahl Wege in einem Graphen
Das ist nun gleich doppelter Unfug. Da n^2 ga nicht von dem Index i abhängt, ist

$\begin{eqnarray*} \sum_{i=1}^3 n^2 =n^2\sum_{i=1}^3 1=n^2 +n^2 +n^2=3n^2 \end{eqnarray*}$

und

$\begin{eqnarray*} \sum_{i=2}^4 n^2 =n^2\sum_{i=2}^4 1=n^2 +n^2 +n^2=3n^2 \end{eqnarray*}$

Du meinst wohl

$\begin{eqnarray*} \sum_{i=1}^3 i^2 \neq \sum_{i=2}^4 i^2 \end{eqnarray*}$

Und das ist tatsächlich nicht gleich. Du hast dabei allerdings keine Indexänderung vorgenommen, sondern nur die Grenzen geändert. Korrekt wäre mit j = i +1, also i = j - 1

$\begin{eqnarray*} \sum_{i=1}^3 i^2=\sum_{j=2}^4 (j-1)^2=\sum_{i=2}^4 (i-1)^2 \end{eqnarray*}$

16.01.2011, 13:16

Legostein

Auf diesen Beitrag antworten »

Ah, jetzt blicke ich klarer durch - vielen Dank für deine Mühe und Geduld.

Neue Frage »

Antworten »

Maximale Anzahl Wege in einem Graphen

Verwandte Themen