[Graphentheorie] Ubahn Netz |
12.10.2013, 15:58 | Adramelec | Auf diesen Beitrag antworten » | ||
[Graphentheorie] Ubahn Netz ich hab schon wieder eine Frage. Folgende Aufgabe habe ich: "Ein Ubahn Netz bestehend aus U1, U2 und U3. Die Haltestellen werden als Stationen bezeichnet. Der BAschnitt zwischen zwei Station ist eine Teilstrecke. a) Die U2 ist die längste Linie mit 9 Teilstrecken b) Fünf Stationen sind Umsteigerknoten wo jeweils zwei Linien aufeinander treffen. c) Kein Umsteigerknoten ist mit einem anderen Umsteigerknoten adjazent. d) Von der U1 und U3 kann man an jeweils zwei verschiedenen Umsteigerknoten zur U2 umsteigen. e) Kein Umsteigerknoten ist auch Endststation einer U-Bahn-Linie. f) Das gesamte U-Bahn-Netz hat 19 Stationen. g) Am Umsteigerknoten zwischen U1 und Ue3 ist der Abstand zu allen sechs Endstation jeweils drei Teilstrecken. h) In der Streckenmitte der Linie U2 gibt es zwei adjazente Knoten, die keine Umsteigerknoten sind. Konstruieren Sie den Graphen." Also mir ist natürlich klar, dass ich die U2 mit 10 Knoten und 9 Kanten zeichnen muss. Und dann wirds aber schon spannend. Mir ist auch bewusst, dass ich die Endstationen der U2 nicht angreifen kann und die zwei in der Mitte auch nicht, da Sie keine Umsteigerknoten sein dürfen. 10 Knoten habe ich noch zur Verfügung. Aber gibt es hier irgendeinen Weg "systematisch" vorzugehen? Mit der Adjazenzmatrix komm ich hier ja nicht wirklich weit oder? Danke! |
||||
12.10.2013, 18:38 | Math1986 | Auf diesen Beitrag antworten » | ||
RE: [Graphentheorie] Ubahn Netz Du kannst zunächst mal versuchen, die Aussagen in graphentheoretische Sprechweise zu übersetzen: a) Es gibt einen Weg der Länge 9 b) Es gibt 5 Knoten mit Knotengrad 4. c) ... Dann kannst du dir überlegen, wie viele Knoten vom Grad 1, 2 und 4 es gibt. |
||||
12.10.2013, 18:47 | Adramelec | Auf diesen Beitrag antworten » | ||
a) Einen Weg mit 10 Knoten und 9 Kanten b) Es gibt 5 Knoten mit Knotengrad 2 (oder wie kommst du auf Knotengrad 4?) c) Kein knoten mit Knotengrad 2 ist adjazent zu einander. d) Es gibt zwei zusätzliche Wege. Diese Kanten dürfen nicht adjazent sein. e) Kein Knoten mit dem Grad 2 darf der letzte Knoten in einem Weg sein. f) Der Graph hat 19 Knoten. g) Es gibt einen Knoten, die inzident mit einer Kante von U1 und U3 sind. Wobei von diesem Knoten alle Endknoten mit 3 Teilstrecken geschafft werden muss. h) Streckenmitte der U2 haben 2 Knoten den Knotengrad 1. Ist das so mal richtig? Also das hilft auf jeden Fall schon mal. Habe ich jetzt eine Chance das in eine Matrix zu transportieren? |
||||
12.10.2013, 19:01 | Math1986 | Auf diesen Beitrag antworten » | ||
Du scheinst da mit den Knoten einen generellen Denkfehler zu haben: b) Auf Knotengrad 4 komme ich, da sich dort zwei Linien kreuzen und diese nach e) eben keine Endstationen sind. Also kann man von der Station aus mit jeder der beiden Linien in zwei Richtungen fahren. Siehe c) c) Das heißt im Prinzip nur, dass keine zwei Bahnen den selben Streckenabschnitt befahren, brauchst du u.A. bei b) d) Würde ich erstmal offen lassen. e) Etwas präziser. Was heißt "der Letzte in einem Weg"? e) sagt ja gerade, dass es überhaupt Knoten mit Grad 1 gibt. f) Richtig g) Würde ich erstmal offen lassen. h) Würde ich erstmal offen lassen. Graphentheoretisch entsprechen also die "Endstationen" des U-Bahn-Netzes Knoten vom Grad 1, während "Umsteigerknoten" Knoten vom Grad 4" entsprechen. Der Rest der Knoten hat Grad 2. Und nochmal: Dann kannst du dir überlegen, wie viele Knoten es jeweils gibt. |
||||
12.10.2013, 19:39 | Adramelec | Auf diesen Beitrag antworten » | ||
Cool! Ich merk schön langsam wie man sowas in graphentheoretische Begriffe verwandeln kann.. Also das ist mein Ergebnis: U2 hat 10 Knoten ---- 2 Knoten den Grad 1 ---- 4 Knoten den Grad 4 ---- 4 Knoten den Grad 2 U1 hat: ---- 2 Knoten mit Grad 1 ---- 2 Knoten mit Grad 4 U3 hat: ---- 2 Knoten mit Grad 1 ---- 2 Knoten mit Grad 4 Es muss einen Knoten mit Grad 2 geben (betrifft den Weg von U3 und U1) richtig so? Und wenn ja, wie mach ich weiter? Sollte ich auf grund dessen das schon zeichnen können? (Ich steh ja ganz auf Matrizen, seit du mir gesagt hast das die Methode von gestern immer funktioniert..(für die Anwendungen in den anderen Thread) :-D) |
||||
12.10.2013, 19:47 | Math1986 | Auf diesen Beitrag antworten » | ||
Überlege dir erstmal, wie viele Knoten vom Grad 1, 2 und 4 es insgesamt gibt. Wenn du zeichnen willst dann fang damit an, die Linie U2 zu zeichnen, und überlege dir dann, wo genau sich die Umsteigestationen zu U1 und U3 befinden. |
||||
Anzeige | ||||
|
||||
12.10.2013, 19:52 | Adramelec | Auf diesen Beitrag antworten » | ||
Okay, sry, ich probiers nochmal: 6 Knoten mit Grad 1 5 Knoten mit Grad 4 8 Knoten mit Grad 2 right? |
||||
12.10.2013, 19:53 | Math1986 | Auf diesen Beitrag antworten » | ||
|
||||
12.10.2013, 20:23 | Adramelec | Auf diesen Beitrag antworten » | ||
Dann hab ich das: [attach]31776[/attach] Und ab jetzt wirds spannend ;-) Natürlich könnt ich jetzt vermutlich doch herumprobieren draufkommen.. - aber das ist ja nicht Sinn der Übung.. PS: Bin für heute raus, antworte morgen in der Früh! |
||||
12.10.2013, 20:28 | Math1986 | Auf diesen Beitrag antworten » | ||
Na, nun kommt Hinweis c) ins Spiel - und die Tatsache, dass du genau 4 Umsteigeknoten unterbringen musst. |
||||
13.10.2013, 12:21 | Adramelec | Auf diesen Beitrag antworten » | ||
Ich konnte das Beispiel lösen. Danke! :-) Das Umformen in graphentheoretische Begriffe ist wirklich ein guter Hinweis und macht das bearbeiten solcher Aufgaben wesentlich leichter. Ich glaub, ich hab jetzt alles. Danke für deine wirklich sehr gute Hilfe! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |