Pfad Anzahl Knoten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:58 Fr 17.06.2011 | | Autor: | user0009 |
Hallo!
Ich hätte noch eine Aussage, bei der ich mir nicht sicher bin:
Ein nichtnotwendigerweise einfacher Pfad mit Länge k besteht aus zumindest k-1 verschiedenen Knoten.
Die Aussage müsste stimmen, da ein Pfad die gleiche Länge wie Knoten haben kann und der kürzeste Pfad aus 2 Knoten und der Länge 1 besteht.
lg user0009
|
|
| |
|
Spontan würde ich sagen die Aussage stimmt, aber ich hab mal ein wenig gegooglet:
Laut Wiki ist ein Pfad eine Menge [mm] $(v_1,...,v_n)$ [/mm] von n VERSCHIEDENEN Knoten, wobei [mm] $v_i$ [/mm] und [mm] $v_{i+1}$ [/mm] jeweils miteinander verbunden sind.
Dann wäre die Aussage natürlich wahr.
Problem dabei ist allerdings, dass es dann keinen ersichtlichen Unterschied zwischen einem Pfad und einem einfachen Pfad gibt.
Andere Definitionen legen keinen Wert darauf, dass die Knoten verschieden sind; dann währe die Aussage falsch.
Fazit:
Ich bin stark der Meinung, dass in einem Pfad die einzelnen Knoten verschieden sein müssen - ich frage mich dann nur was der Unterschied zwischen einem Pfad und einem einfachen Pfad sein soll...
Du solltest aber sicherheitshalber nochmal in deinem Skript/Buch nachgucken, damit du die Definition benutzt die als "richtig" vorausgesetzt wird.
Ich lasse die Frage nochmal offen, falls jemand aufklären kann wie genau ein Pfad definiert ist und was genau der Unterschied zwischen einem einfachen Pfad und einem Pfad ist (vor allem die Frage, wieso man beide Definitionen - Knoten mehrfach erlaubt und nicht - bei google findet würde mich interessieren...)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:17 Sa 18.06.2011 | | Autor: | user0009 |
Also laut meinem Skript ist die Definition für einen Pfad folgende:
Ein Pfad von v nach w,v,w [mm] \in [/mm] V ist eine Folge von Knoten [mm] v=v_0, v_1 ,v_2,...v_k= [/mm] w, [mm] v_i \in [/mm] V; i=0...k, wobei [mm] (v_i,v_{i_+k}) \in [/mm] E, i=0...k-1 gilt. Ein Pfad ist einfach, wenn [mm] v_i \not= v_j, [/mm] 0 [mm] \le [/mm] i, j [mm] \le [/mm] k gilt.
Allerdings bin ich mir eben nicht sicher wie ich die Definiton auf die Aussage anwenden soll.
lg user0009
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:10 Sa 18.06.2011 | | Autor: | user0009 |
Habe jetzt gerade noch eine Definiton in meinem Skript gefunden und die sagt mir, dass die Aussage definit falsch ist:
Die Länge eines Pfades ist die Anzahl seiner Kanten (k) bzw. die Summe der Kantengewichte bei gewichteten Graphen. Da das Gewicht unterschiedlich sein kann, stimmt zumindest k-1 verschiedenen Knoten nicht mehr. Es kann ja auch negative Kantengewichte geben.
lg user0009
|
|
|
|
