gerichteter Graph definieren |
25.03.2012, 03:30 | stefanerb | Auf diesen Beitrag antworten » |
gerichteter Graph definieren Der Graph G=(V,E) sei definiert durch V={0,1}x{0,1} {0,1,2,3}x{3,4} und E={{(a,b) c,d)}|b=d+1} {(0,4),(1,1)} Meine Ideen: Wie bekomme ich denn da die Knotenanzahl heraus? Iwie komme ich mit der Formulieren nicht zurecht!sind das jetzt einfach die Knoten von 0-4?? |
||
25.03.2012, 04:11 | Airblader | Auf diesen Beitrag antworten » |
Die Knoten sind Elemente aus V, also die Elemente aus und . Beispielsweise also (0,0), (0, 1), (1, 4), (3, 3), ... Bist du sicher, dass das Schulmathematik ist? air |
||
25.03.2012, 22:13 | stefanerb | Auf diesen Beitrag antworten » |
Tut mir leid, ist natürlich Hochschulmathe, hab mich vor lauter Verzweiflung gestern wahrscheinlich im Unterforum geirrt. Aber wie du es jetzt schreibst (0,0),(0,1),(1,4) sind es doch Relationen (Kanten) und keine Knoten, oder sollen die Knoten so heißen "00" "01" "10" "11" ? Steh bestimmt schon wieder auf dem Schlauch. Vielen Dank im voraus! |
||
25.03.2012, 23:01 | Airblader | Auf diesen Beitrag antworten » |
Stell dir die Knoten als Punkte im vor, also als Punkte im euklidischen Gitter. Da (0,0) ein Knoten ist, ist der Ursprung also ein Knoten usw. Eine Kante, in diesem Fall, ist nicht von der Form (a,b), sondern von der Form ((a,b), (c,d)). Das siehst du auch, wenn du dir die Menge E mal anschaust. air |
||
25.03.2012, 23:17 | Airblader | Auf diesen Beitrag antworten » |
Als Beispiel hänge ich dir mal die Knotenmenge an, in der ich die eine Kante ((0,4),(1,1)) bereits gezeichnet habe. [attach]23694[/attach] air |
||
25.03.2012, 23:51 | stefanerb89 | Auf diesen Beitrag antworten » |
Oh du gibst dir aber Mühe, jetzt hab ich das sogar verstanden, das der graph im euklidischen Gitter dargestellt wird hab ich net gemerkt, aber jetzt isses klar, danke. Das b=d+1 bedeutet doch dann eigentlich, dass alle Knoten verbunden werden bei denen b um eins größer ist als d.....zum Beispiel ((0,0),(0,1)) ((1,0),(1,1)) oder ((2,3),(2,4)) usw...ist das so gemeint? |
||
Anzeige | ||
|
||
26.03.2012, 00:06 | Airblader | Auf diesen Beitrag antworten » |
Genau andersrum: ((0,1),(0,0)), ((1,1),(1,0)) und ((2,4),(2,3)) wären Kanten. Bei einem gerichteten Graphen ist das durchaus wichtig. In meiner Grafik haben habe ich die Richtung der Kante nicht illustriert. air |
||
26.03.2012, 00:34 | stefanerb | Auf diesen Beitrag antworten » |
Achso, ok. Also es steht ja da {(0,4),(1,1)} das sagt mir dass die Richtung von 0,4 zu 1,1 geht, hätte jetzt im ersten moment gedacht ungerichtet, aber gut dass du es nochmal betont hast dass er gerichtet ist. [attach]23697[/attach] Ich hoffe ich kann noch ein paar weitere Fragen stellen? Wir hatten bisher nur vollständige Graphen oder K3,3 oder K6,6, da ist es ja leicht festzustellen ob sie bipartit oder planar sind, nur wie mache ich es jetzt wenn ich feste Knotenpunkte habe, darf ich den Graph dann überhaupt falten, die Kante (0,4)(1,1) macht mir da Schwierigkeiten, sonst könnte man es vlt sogar optisch schon erkennen ob bipartit oder planar. Ich kenn nur die Formel: |E| <= 3 * |V| - 6 15<=30 stimmt, also planar?? Außerdem: |E|<=2*|V|-4 15<=18 also auch bipartit? |
||
26.03.2012, 01:35 | Airblader | Auf diesen Beitrag antworten » |
Du hast noch ein paar Kanten vergessen! Im Übrigen gehen die Kanten meiner Meinung nach alle in die falsche Richtung ... die Kanten gehen doch von (a,d+1) nach (c,d), also von oben nach unten. Im Übrigen glaube ich, dass lediglich gilt "Wenn G planar, dann |E| <= 3*|V| - 6", nicht jedoch andersrum. Du könntest diese Eigenschaft also lediglich nutzen, um Plättbarkeit zu widerlegen – das geht hier so jedoch nicht. Wie man die Frage noch beantworten kann, weiß ich leider nicht, so tief stecke ich in der Grapthentheorie nicht drin. air |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |