Anzahl Kombinationen/ Ecken/ Pfad durch Knoten

Wissenschaft Mathematik
#1

Liebe Mathe-Experten,

habe mehrere Status, die nacheinander durchschritten werden können, beispielsweise a, b, c, d. Es darf immer nur einmal eine Kombination aus zwei Status vorkommen, also ohne Beachtung der Reihenfolge: {a,b} = {b,a}. Wieviele Statuswechsel gibt es?

Ich dachte, es sind (n über k), bei k = 2 (i.e. ein Paar), vereinfacht also n * (n-1) / 2. Beim Überprüfen ist es richtig für ungerade n, nicht jedoch für gerade n, beispielsweise bei vier Status:
a - b - c - d - a - c (5 Statuswechsel; Formel ergibt 6 Paare).

In diesem Beispiel gibt es auch noch den Pfad:
a - b - c - d - b (4 Statuswechsel); {d,b} fehlt im Pfad oben; insgesamt gibt es also sechs unique Paare {a,b}, {b,c}, {c,d}, {d,a}, {a,c} und {d,b}. Die Differenz der Anzahl wird bei größeren geraden n größer.

  • Wie berechne ich die maximale Anzahl Statuswechsel (oben: 5) und die minimale (oben: 4)?

  • Wieso stimmt meine Formel scheinbar für ungerade n, nicht jedoch für gerade n?

  • Mit Beachtung der Reihenfolge verdoppelt sich die Anzahl der Paare (bei k = 2); gilt das auch für die Statuswechsel?

Vielen Dank im Voraus

#2

Hallo,

du hast also einen vollständigen Graphen Kn. Darauf willst du so viele Kanten wie möglich hintereinander ablaufen, also eine Eulersche Linie bilden.
Die Existenz solcher Linien hängt von den Graden der Knoten ab. Haben alle Knoten geraden Grad, gibt es so eine Linie ohne weitere Anpassung und die Anzahl deiner Übergänge ist die Anzahl der Kanten. Das entspricht dann deiner Formel für ungerades n.
Für gerades n ist das etwas anders: Die Existenz der Eulerschen Linie ist nur dann gegeben, wenn genau zwei Knoten ungeraden Grad haben. Du musst also einige Kanten entfernen. Also lässt du zwei Knoten so wie sie sind und entfernst von den anderen jeweils eine Kante. Dadurch, dass jede Kante zwei Knoten verbindet, musst du also (n-2)/2 Kanten entfernen. Wenn du damit noch deine erstellte Formel korrigierst, sollte dein Ergebnis stimmen. Im Beispiel mit n = 4:
Anzahl Kanten = 4 * 3 / 2 = 6
Abzüglich (4 - 2) / 2 = 1
Macht 5 Übergänge.

Nico

#3

Hallo Nico,

vielen Dank - die Formel stimmt nun mit deiner Korrektur :smile:

Ich verstehe sie allerdings nicht ganz: Gemäß Euler darf zwei oder kein Knoten von ungeradem Grad sein. In meinem Beispiel ist ein Knoten ein Status, und ich berechne die Anzahl unterschiedlicher Statuspaare. Ein Paar (e.g. a - b) hat eine Kante, also a hat nur einen Nachbarn, b ebenso. Das sind bereits zwei Knoten von ungeradem Grad, und damit darf es maximal ein Paar geben. Ich müsste also bei mehr als einem Statuspaar (i.e. zwei Status) immer jeweils eine Kante pro (Paar - 1) von der Anzahl der möglichen Paare abziehen.
n = 2: 1 Paar, siehe oben, nichts abziehen
n = 3: 3 Paare, zwei Kanten abziehen
n = 4: 6 Paare, fünf Kanten abziehen
n = 5: 10 Paare, neun Kanten abziehen

Das entspricht wahrscheinlich deinem Satz:
„Also lässt du zwei Knoten so wie sie sind und entfernst von den anderen jeweils eine Kante.“

  • Damit müsste unabhängig von geradem oder ungeradem n etwas abgezogen werden (außer n = 2)
  • Wie kommst du auf: „Dadurch, dass jede Kante zwei Knoten verbindet, musst du also (n-2)/2 Kanten entfernen.“? Was bedeuten 2 im Zähler, 2 im Nenner?

Da deine Formel zu stimmen scheint, habe ich wahrscheinlich einen Denkfehler im Beispiel oben.

Liebe Grüße
Marco

#4

Hallo,

Ich müsste also bei mehr als einem
Statuspaar (i.e. zwei Status) immer jeweils eine Kante pro
(Paar - 1) von der Anzahl der möglichen Paare abziehen.

ich weiß nicht, ob wir gerade aneinander vorbei reden. In dem Graphen sind die einzelnen Zustände die Knoten, wobei jeder Zustand potenziell mit jedem anderen verbunden ist. Die Anzahl der Kanten ist also die Anzahl der möglichen Paare, wie du sie bereits ausgerechnet hast.
Jetzt ist bei ungeradem n der Grad jedes Knotens gerade, da er zu allen restlichen n-1 Knoten eine Verbindung hat. Ist n ungerade, dann ist n-1 gerade und es existiert eine Eulersche Linie.
Bei geraden n betrachten wir folgendes Beispiel:

1-----2
|\ /|
| \ / |
| X |
| / \ |
|/ \|
3-----4

Jetzt sollen 1 und 2 die Knoten sein, die ungeraden Grad behalten. Es könnten auch beliebige andere Knoten sein. Diese behalten alle Kanten, also bleiben noch (n-2)=2 Knoten, bei denen wir eine Kante wegnehmen müssen, damit der Knotengrad gerade wird. Die einzige Kante, die dafür in Frage kommt, ist {3,4}. Diese entfernen wir. Da sie aber sowohl an Knoten 3 als auch an Knoten 4 angrenzt, senkt das den Grad von zwei Knoten. Daher kommt die Korrektur um (n-2)/2.
Ich hoffe, das war verständlicher.

Nico

#5

Hallo Nico,

ja, war es :smile:

Vielen Dank
Marco