Graphentheorie - Pfade und Kantenzüge

18.03.2014, 14:15	GarNixwisser	Auf diesen Beitrag antworten »
Graphentheorie - Pfade und Kantenzüge Meine Frage: Guten Tag, ich lerne gerade für meine Graphentheorieprüfung und komme an einer Stelle nicht so richtig weiter. Was ist der Unterschied zwischen einem Pfad und einem Kantenzug? Meine Ideen: Als Pfad haben wir definiert: ist eine Liste von aufeinanderfolgenden adjazenten Knoten. Als Kantenzug haben wir definiert: ist eine Liste von Kanten und Knoten. Ist der Unterschied also nur, dass in der Liste von Pfaden nur die (adjazenten) Knoten aufgeführt werden und im Kantenzug sowohl die Knoten, als auch die Kanten? Oder gibt es noch weitere Unterschiede? Vielen Dank schon mal im Voraus für eure Antworten!!!
18.03.2014, 14:49	weisbrot	Auf diesen Beitrag antworten »
RE: Graphentheorie - Pfade und Kantenzüge ich verstehe nicht sehr viel von graphentheorie, deshalb gehe ich mal einfach nach deinen definitionen. ein kantenzug ist dann sozus. wie ein pfad, aber mit mehr information, nämlich den, die adjazenten knoten verbindenden, kanten. also: wenn du aus einem kantenzug die kanten rausnimmst, bekommst du einen (eindeutigen) pfad, andersrum gibt es aber unter umständen (wenn es zwischen 2 knoten mehr als eine kante gibt) mehrere kantenzüge, die auf diese weise den gleichen pfad induzieren. beide sachen sind damit im prinzip das gleiche in einem graph in dem es zwischen je 2 knoten maximal eine kante gibt. lg
20.03.2014, 11:00	Lomlup	Auf diesen Beitrag antworten »
RE: Graphentheorie - Pfade und Kantenzüge Hey, ich lerne auch derzeit für meine Prüfung, daher kann ich dir eventuell dabei helfen ^^. Kantenzüge sind wirklich nur aufeinanderfolgende Kanten Bsp.: Kantenzug alpha=(alpha1,alpha2,alph3,...alpha2,...,alpha r) Ein Pfad (bei uns auch Weg genannt) hingegen ist ein Kantenzug mit einer Besonderheit, er durchläuft die niemals dieselben Kanten und Ecken erneut (v1-v2, v2-v3 ...vn-1 - vn). Außerdem ist der Weg-graph Pn schlicht. (falls v1 und vn identisch sind, ist es ein Kreis) Also sind alle Pfade Kantenzüge, aber nicht alle Kantenzüge sind Wege/Pfade. Um auf deine Frage zurückzukommen, bei den Pfaden stehen die Knoten/Ecken im Vordergrund. Ich hoffe ich konnte dir weiterhelfen.
23.03.2014, 11:15	LuZi88	Auf diesen Beitrag antworten »
RE: Graphentheorie - Pfade und Kantenzüge Ein Pfad* (bei uns auch Weg genannt) ....* Wir unterscheiden zwischen Pfad, Weg und Wanderung. Wobei Pfad: Jede Ecke u. jede Kante wird nur einmal benützt. Weg: Jede Kante wird nur einmal benützt. Wanderung: Ecken und Pfade dürfen beliebig oft benützt werden. => Alle Pfade sind Wege, Alle Wege sind Wanderungen => Alle Pfade sind Wanderungen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »