Kürzester Weg < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich würde gerne wissen , wie lang der kürzeste Weg zwischen zwei Knoten höchstens ist.
Ich habe schon diverse Skripts durchforstet (Wege und Kreise) , aber nichts brauchbares gefunden.
Ich habe mir auch den Dijkstra-Algorithmus angeguckt, aber der hat mir auch nicht weitergeholfen.
Ich habe 2 Knoten gezeichnet und diese durch eine Kante verbunden. Wenn ich mir das jetzt so angucke , is der kürzeste Weg doch genau diese eine Kante , oder nicht ?
Wär nett , wenn ihr mir bisschen auf die Sprünge helfen könntet.
Vielen Dank im Voraus.
|
|
| |
|
> Hallo,
>
> ich würde gerne wissen , wie lang der kürzeste Weg
> zwischen zwei Knoten höchstens ist.
>
> Ich habe schon diverse Skripts durchforstet (Wege und
> Kreise) , aber nichts brauchbares gefunden.
> Ich habe mir auch den Dijkstra-Algorithmus angeguckt, aber
> der hat mir auch nicht weitergeholfen.
>
> Ich habe 2 Knoten gezeichnet und diese durch eine Kante
> verbunden. Wenn ich mir das jetzt so angucke , is der
> kürzeste Weg doch genau diese eine Kante , oder nicht ?
> Wär nett , wenn ihr mir bisschen auf die Sprünge helfen
> könntet.
>
> Vielen Dank im Voraus.
Hallo pc_doctor,
Da fehlen ganz wichtige Voraussetzungen !
Vermutlich ist gemeint, dass ein zusammenhängender
Baum betrachtet werden soll, denn sonst gibt es ja
zwischen gewissen Paaren von Punkten überhaupt
keinen Weg, also auch keinen kürzesten.
Wenn über einen zusammenhängenden Graph gar
nichts spezielles bekannt ist als seine gesamte
Knotenzahl n, so muss man für das Maximum der
Länge des kürzesten Weges zwischen zwei beliebigen
Punkten des Graphen vom schlimmstmöglichen Fall
ausgehen. Das wäre ein linearer (unverzweigter)
Baum (= Weg) von einem ersten Punkt A zu einem
n-ten Punkt B. Dieser ist der längstmögliche kürzester
Weg zwischen 2 Knoten und hat die Länge n-1 .
LG , Al-Chw.
|
|
|
| |
|
Hallo Al,
danke für die schnelle Antwort.
Mehr als die Tatsache , dass wir bei ungerichteten Graphen sind , und doppelknotenfreie Wege haben, gibt es leider keine weiteren Voraussetzungen.
Ich habe ein weiteres Buch , in das ich reingeguckt habe und dort steht:
"Die Länge eines Weges W in einem gewichteten...".
Ich glaube damit hat sich das erledigt , weil wir bi
s jetzt gewichtete Graphen gar nicht behandelt haben.
Was da aber noch steht ist , dass ein kürzester Weg von einem Knoten s zu einem Knoten z ein Weg mit minimaler Länge ist.
Wenn wir jetzt mal die mathematische Formalität weglassen , ist es doch logisch , dass wenn man 2 Knoten hat , der kürzeste Weg diese eine Kante ist , die diese beiden Knoten verbindet. Anders kann ich mir das grade nicht vorstellen.
EDIT: Ich habe wohl die Aufgabe missverstanden und keinen Bezug zur Aufgabestellung hergestellt(da die Aufgabenstellung auf der vorherigen Seite war):
Die Wörter einer festen Länge n über dem Alphabet {A,C,G,T} bilden die Knotenmenge [mm] V_n [/mm] eines ungerichteten Graphen [mm] G_n [/mm] = [mm] (V_n [/mm] , [mm] E_n). [/mm] Zwei solche Wöter sind adjazent , wenn sie sich an genau einer Stelle unterscheiden, also Hamming-Abstand 1 haben"
Aufgabe:
Wie lang ist ein kürzester Weg zwischen zwei Knoten höchstens ?
Also haben wir immer noch die gleichen Voraussetzungen.
|
|
|
| |
|
> Hallo Al,
>
> danke für die schnelle Antwort.
>
> Mehr als die Tatsache , dass wir bei ungerichteten Graphen
> sind , und doppelknotenfreie Wege haben, gibt es leider
> keine weiteren Voraussetzungen.
>
> Ich habe ein weiteres Buch , in das ich reingeguckt habe
> und dort steht:
> "Die Länge eines Weges W in einem gewichteten...".
> Ich glaube damit hat sich das erledigt , weil wir bi
> s jetzt gewichtete Graphen gar nicht behandelt haben.
> Was da aber noch steht ist , dass ein kürzester Weg von
> einem Knoten s zu einem Knoten z ein Weg mit minimaler
> Länge ist.
>
> Wenn wir jetzt mal die mathematische Formalität weglassen
> , ist es doch logisch , dass wenn man 2 Knoten hat , der
> kürzeste Weg diese eine Kante ist , die diese beiden
> Knoten verbindet. Anders kann ich mir das grade nicht
> vorstellen.
Naja, das Ganze soll sich doch aber wohl doch auf
einen bestimmten vorgegebenen Graphen beziehen.
Wenn du dann zwei beliebige Knoten A und B heraus-
greifst, kannst du doch nicht davon ausgehen, dass
die Kante AB tatsächlich zum Graphen gehört (außer
du nimmst der Einfachheit halber an, dass du ohnehin
den vollständigen Graph hast, in dem 2 beliebige
Knoten stets direkt durch eine Kante verbunden sind).
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:36 Di 21.01.2014 | | Autor: | pc_doctor |
Hallo Al,
entschuldige das Missverständnis. Ich habe die Aufgabenstellung nicht gesehen ( da die Aufgabenstellung auf einer vorherigen Seite war ) und somit dachte ich , dass die Aufgabe allgemein gestellt war. Schau mal bitte meinen editierten Post "Konkrete Aufgabe" an.
|
|
|
| |
|
> Hallo Al,
> entschuldige das Missverständnis. Ich habe die
> Aufgabenstellung nicht gesehen ( da die Aufgabenstellung
> auf einer vorherigen Seite war ) und somit dachte ich ,
> dass die Aufgabe allgemein gestellt war. Schau mal bitte
> meinen editierten Post "Konkrete Aufgabe" an.
Aha. Das ist was anderes - und ziemlich simpel.
| Aufgabe | Die Wörter einer festen Länge n über dem Alphabet {A,C,G,T} bilden die Knotenmenge $ [mm] V_n [/mm] $ eines ungerichteten Graphen $ [mm] G_n [/mm] $ = $ [mm] (V_n [/mm] $ , $ [mm] E_n). [/mm] $ Zwei solche Wörter sind adjazent , wenn sie sich an genau einer Stelle unterscheiden, also Hamming-Abstand 1 haben"
Aufgabe:
Wie lang ist ein kürzester Weg zwischen zwei Knoten höchstens ? |
Betrachten wir 2 beliebige solche Wörter [mm] w_1 [/mm] , [mm] w_2
[/mm]
der Länge n . Dann erhalten wir doch sofort einen "Weg"
von [mm] w_1 [/mm] zu [mm] w_2 [/mm] , indem wir z.B. schön der Reihe nach
einen Buchstaben nach dem anderen abändern, sofern
er überhaupt geändert werden muss. Der kürzeste Weg
besteht also aus genau so vielen Kanten wie die Anzahl
der Stellen i mit $\ [mm] w_1(i)\not= w_2(i)$.
[/mm]
Im "schlimmsten" Fall ist diese Anzahl gleich n .
LG , Al-Chw.
|
|
|
| |
|
Hallo,
damit ich das richtig verstehe:
Was meinst du mit "einen Buchstaben ändern".
Wir haben zum Beispiel a und b.
Meinst du es so , dass man a mit b verbindet , danach die Buchstaben ändert und dann b mit a verbindet ? Sodass man 2 "Wege" hat ?
|
|
|
| |
|
> Hallo,
> damit ich das richtig verstehe:
>
> Was meinst du mit "einen Buchstaben ändern".
>
> Wir haben zum Beispiel a und b.
>
> Meinst du es so , dass man a mit b verbindet , danach die
> Buchstaben ändert und dann b mit a verbindet ? Sodass man
> 2 "Wege" hat ?
Betrachten wir z.B. den Fall mit n=6 . In diesem Raum gibt
es z.B. die Wörter
$\ [mm] w_1\ [/mm] =\ GGACTA$
$\ [mm] w_2\ [/mm] =\ CGTAGG$
[mm] w_1 [/mm] und [mm] w_2 [/mm] unterscheiden sich an 5 der 6 Stellen. Ein
kürzester Weg von [mm] w_1 [/mm] zu [mm] w_2 [/mm] geht also z.B. über diese
Stationen:
GGACTA = [mm] w_1
[/mm]
CGACTA
CGTCTA
CGTATA
CGTAGA
CGTAGG = [mm] w_2
[/mm]
Dieser Weg hat die Länge 5 - und kürzer geht es in
diesem Fall offenbar nicht.
LG
|
|
|
| |
|
Vielen Dank für die Antwort.
Gibt es da jetzt eine bestimmte "Taktik" um von [mm] w_1 [/mm] zu [mm] w_2 [/mm] kommen ? Gucke mir das die ganze Zeit an und kann kein "System" erkennen, gibt es also einen bestimmten Weg , wie man die einzelnen Buchstaben abändert?
|
|
|
| |
|
Die Reihenfolge, in der du die Buchstaben änderst, ist egal, solange du nur immer 1 Buchstaben pro Schritt änderst.
Wichtig ist nur, wie oft du 1 Buchstaben ändern musst, um von [mm] w_1 [/mm] nach [mm] w_2 [/mm] zu gelangen.
Das sind im Allgemeinen genau so viele Schritte, um wie viele Buchstaben sich die Wörter unterscheiden.
Z.B ACT
ATT
Diese beiden Wörter unterscheiden sich um 1 Buchstaben,
also musst du auch nur einen Schritt (= 1 Kante) gehen, um von ACT zu ATT zu gelangen.
Schöne Grüße
|
|
|
| |
|
Hallo und danke für die Antworten.
Bezogen auf de Aufgabe
"Die Wörter einer festen Länge n über dem Alphabet {A,C,G,T} bilden die Knotenmenge $ [mm] V_n [/mm] $ eines ungerichteten Graphen $ [mm] G_n [/mm] $ = $ [mm] (V_n [/mm] $ , $ [mm] E_n). [/mm] $ Zwei solche Wöter sind adjazent , wenn sie sich an genau einer Stelle unterscheiden, also Hamming-Abstand 1 haben"
Aufgabe:
Wie lang ist ein kürzester Weg zwischen zwei Knoten höchstens ?"
Das heißt also , ich habe die Knotenmenge {A,C,G,T}
Und die Frage ist jetzt wie lang der kürzeste Weg zwischen zwei Knoten ist.
Aber welche Knoten aus der Menge {A,C,G,T} muss ich jetzt nehmen ? Alle ?
ALso : AC ; AG ; AT ; CA; CG ; CT ; GC ; TC, TA
Und jetzt als Paar:
ALso (AC;AG) ( AC;AT) (AC;CA) (AC;CG) jeder mit jedem sozusagen. Und dann haben sie doch immer einen unterschiedlichen Buchstaben, oder ?
|
|
|
| |
|
> "Die Wörter einer festen Länge n über dem Alphabet
> {A,C,G,T} bilden die Knotenmenge [mm]V_n[/mm] eines ungerichteten
> Graphen [mm]G_n[/mm] = [mm](V_n[/mm] , [mm]E_n).[/mm] Zwei solche Wörter sind adjazent
> , wenn sie sich an genau einer Stelle unterscheiden, also
> Hamming-Abstand 1 haben"
> Aufgabe:
> Wie lang ist ein kürzester Weg zwischen zwei Knoten
> höchstens ?"
>
> Das heißt also , ich habe die Knotenmenge {A,C,G,T}
NEIN !
Jedes Wort der Länge n, das aus den 4 gegebenen
Buchstaben gebildet ist, ist ein Knoten des Graphen.
Insgesamt hat dieser Graph also [mm] 4^n [/mm] Knoten.
Bei Länge n=6 sind dies zum Beispiel [mm] 4^6=4096 [/mm] Knoten.
LG , Al-Chw.
|
|
|
| |
|
Hallo Al,
okay jetzt verstehe ich was mit n gemeint ist.
Wir haben also die Länge [mm] 4^{n} [/mm] ( 4 weil [mm] |V_n| [/mm] = 4 ist )
Und jetzt soll ich doch aber 2 Knoten mir angucken und den kürzesten Weg rausfinden.
Was ich halt nicht verstehe , welche 2 Knoten ? Ich nehme mal an , es sollen beliebige Knoten [mm] \in V_n [/mm] sein.
Ich kapiere das mit den 2 Knoten irgendwie nicht richtig..
|
|
|
| |
|
> Hallo Al,
>
> okay jetzt verstehe ich was mit n gemeint ist.
>
> Wir haben also die Länge [mm]4^{n}[/mm] ( 4 weil [mm]|V_n|[/mm] = 4 ist ) ![[haee]](/images/smileys/haee.gif "[haee]") ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Da scheint aber immer noch ein Durcheinander vorzu-
herrschen.
1.) Die Länge der betrachteten Wörter ist gleich n .
2.) An jeder der n Stellen eines Wortes kann jeweils
ein beliebiger Buchstabe aus [mm] $\{\,A\,,\,C\,,\,G\,,\,T\,\}$ [/mm] stehen.
3.) Die Menge [mm] V_n [/mm] hat [mm] 4^n [/mm] Elemente, also ist
[mm]|V_n|\ =\ 4^n[/mm] .
> Und jetzt soll ich doch aber 2 Knoten mir angucken und den
> kürzesten Weg rausfinden.
> Was ich halt nicht verstehe , welche 2 Knoten ? Ich nehme
> mal an , es sollen beliebige Knoten [mm]\in V_n[/mm] sein.
> Ich kapiere das mit den 2 Knoten irgendwie nicht richtig..
Ja, es sollen zwei beliebige Knoten sein. Die Länge des
kürzesten Weges (oder besser gesagt: der verschiedenen
möglichen kürzesten Wege) hängt davon ab, an wie vielen
der n Stellen sich die beiden Wörter unterscheiden.
Für jeden einzelnen solchen Unterschied muss man eine
Kante im Graph beschreiten. Da aber die Reihenfolge,
in welcher man diese Unterschiede behebt, frei wählbar ist,
gibt es in der Regel viele "kürzeste Wege" zwischen zwei
vorgegebenen Wörtern.
LG , Al-Chw.
|
|
|
| |
|
Hallo nochmal,
ein Beispiel würde mir das Verstehen sicherlich vereinfachen.
Nehmen wir eine andere Menge [mm] V_n={a,b,c}
[/mm]
Selbe Aufgabenstellung; kürzester Weg zwischen zwei Knoten
Jetzt muss ich doch verschiedene Kombinationen benutzen
Also: ab , ac , ba, bc, cb, ca.
Und jetzt muas ich ab mit ac vergleichen dann ab mit ba , dann ab mit bc usw , oder nicht ?
|
|
|
| |
|
> Hallo nochmal,
>
> ein Beispiel würde mir das Verstehen sicherlich
> vereinfachen.
> Nehmen wir eine andere Menge [mm]V_n={a,b,c}[/mm]
Sorry, aber so kann eine Analogie nicht gehen. Bei der
ursprünglichen Bedeutung von [mm] V_n [/mm] sollten wir schon
bleiben:
Die Wörter einer festen Länge n über dem Alphabet {A,C,G,T}
bilden die Knotenmenge $ [mm] V_n [/mm] $ eines ungerichteten Graphen
$ [mm] G_n [/mm] $ = $ [mm] (V_n [/mm] $ , $ [mm] E_n). [/mm] $
Wenn du jetzt anstatt des Alphabets {A,C,G,T} das
neue Alphabet {a,b,c} nehmen willst, bringt das natürlich
auch keine wirkliche Vereinfachung. Um der ursprünglichen
Aufgabe gerecht zu werden, musst du immer noch eine
Zahl n für die Wortlänge wählen. Wenn du magst, kann
das etwa n=2 sein (mit der leisen Gefahr, dass du dann
gewisse Dinge nicht mehr erkennst, weil sie fast zu
simpel, aber auch verwechselbar werden).
So. Damit wäre [mm] V_2 [/mm] (über dem neuen Alphabet) die Menge
der [mm] 3^n=3^2=9 [/mm] Wörter
aa, ab, ac, ba, bb, bc, ca, cb, cc
Der gesamte Graph hat also in diesem Fall nur 9 Knoten.
Zwei Knoten sind genau dann durch eine Kante verbunden,
wenn sie sich entweder in ihrem ersten oder in ihrem zweiten
(aber nicht in beiden) Buchstaben unterscheiden.
Man kann sich aber auch ohne dass man den
kompletten Graph untersucht, einsehen, dass es
zwischen zwei beliebiben Wörtern (Knoten) einen
kürzesten Weg aus höchstens 2 Kanten geben muss.
Unterscheiden sich die Wörter nur in einem ihrer
Zeichen, so besteht der kürzeste Weg sogar aus
einer einzigen Kante.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:03 Mi 22.01.2014 | | Autor: | pc_doctor |
Hallo,
alles klar , jetzt hab' ich's. Vielen vielen Dank und schönen Abend noch!!!
|
|
|
|
