| Autor |
Beitrag |
    
Simon
| | Veröffentlicht am Sonntag, den 10. September, 2000 - 20:09: | 
|
Hi!
Kann mir bitte dringend hierbei wer helfen?
Die Aufgabe lautet folgendermaßen:
Entferne aus dem vollständigen (ungerichteten) Graphen Kantenmenge {1,....,5} die Knoten (3,5),(4,5).
(a) Stelle den resultierenden Graphen G durch seine Adjazenz- und seine Inzidenzmatrix dar, wobei im Fall der Inzidenzmatrix die Kanten (i,j) gemäß der Relation
(i,j) vor(i',j') « (i<i' v (i=i' ^ j<j'))
anzuordnen sind.
(b) Enthält G eine geschlossene Eulersche Linie? (Eulersche Linie angeben, bzw. Begründung, falls keine existiert.)
(c) Gib eine geschlossene Hamiltonsche Linie in G an.
Vielen Dank schon jetzt!!!!
lg,
Simon |
Ralph
| | Veröffentlicht am Montag, den 11. September, 2000 - 21:05: |
|
Das ist kein Mathematik, oder?
Bin Mathematiker und habe sowas noch nie gehört ....
Machst Du das in der Schule?
Erklär mal genauer.
Ralph |
Fern
| | Veröffentlicht am Montag, den 11. September, 2000 - 21:44: |
|
Hi Ralph,
Dies ist "Grafentheorie".
Ich weiß zwar auch nicht, wie obige Aufgabe zu lösen ist, ich weiß aber, dass dies zur Mathematik gehört.
Eine Eulerlinie ist eine Linie, die alle Kanten des Grafen enthält und eine Hamiltonlinie ist eine Linie, die alle Ecken enthält.
Das berühmte Königsberger Brücken Problem, kann damit gelöst werden oder vielmehr bewiesen werden, dass es keine Lösung hat, weil keine Eulerlinie existiert. |
Zaph (Zaph)
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 19:20: |
|
Graphentheorie hat nichts mit Adeligen zu tun, also bitte mit ph ;-)
Der betrachtete Graph enthält die "Ecken" 1, 2, 3, 4, 5 und zwischen je zwei Ecken, außer zwischen 3 und 5 bzw. 4 und 5 verläuft eine "Kante".
Er hat also die 8 Kanten {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}.
Ein geschlossener eulerscher Pfad existiert nicht, da in den Ecken 3 und 4 ungerade viele Kanten ankommen. Wenn der Pfad nicht geschlossen zu sein braucht, dann gibt es den, da genau zwei Ecken mit ungerade vielen Kanten existieren.
Ein Hamiltonscher Rundweg existiert: 1,5,2,3,4,1.
Bei der Inzidenzmatrix werden Zeilen und Spalten jeweils den Ecken zugeordnet. In diesem Fall haben wir also eine 5x5-Matrix. Ein Eintrag ist 0, wenn zwischen den entsprechenden Ecken keine Kante verläuft. Ansonsten ist der Eintrag 1 oder -1, jenachdem, in welche Richtung die Kante läuft. Wenn die Kante keine Richtung hat, ist der Eintrag beides Mal 1.
Bei der Adjazenzmatrix werden die Zeilen den Ecken und die Spalten den Kanten zugeordnet. In jeder Spalte stehen genau zwei Einsen (nämlich dort, wo die Ecken der entsprechenden Kante liegen) und sonst nur Nullen. |
Simon
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 20:26: |
|
Hallo Zaph!
Herzlichen Dank für deine Lösung. Ich habs auch so ähnlich gemacht.
Ein paar kurze Fragen noch: Wie weisst du, welche Richtung die Kante hat? Gibt es da eine spezielle Regelung? Haben die Kanten bei meinem Beispiel überhaupt eine Richtung?
Meine Adjazenzmatrix würde wie folgt ausschauen:
| 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 1 | 1 | 1 | | 1 | 1 | 0 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | | 1 | 1 | 0 | 0 | 0 |
Kannst du mir bitte noch zeigen, wie die Indzidenzmatrix ausschauen muss?
Ciao,
Simon |
Fern
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 20:40: |
|
Hi Zaph,
Ich halte ebenfalls die Schreibweise "Graf" als ausgemachten Unsinn.
Die deutschen Kultusminister sind da aber anderer Meinung! (Siehe amtliche Regelung der deutschen Rechtschreibung § 32).
==================
Was mich an dieser Aufgabe irritiert hat, ist dass (daß?) gefordert wurde, die "Knoten" (3,5) und (4,5) zu entfernen.
Aber mit deiner (Deiner?) Erklärung ist es jetzt klar.
Gruß, Fern |
Zaph (Zaph)
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 21:19: |
|
Hi Simon und Fern!
Fern: Ich bin grad etwas rumgesurft, habe auch § 32 gefunden, aber das Wort "Graph" dort nicht entdecken können. Zwar "Grafik" neben "Graphik", aber eben nicht "Graph". Das wäre mir jetzt wirklich neu. Habe leider keinen Fremdwörterduden mit der neuen Rechtschreibung zur Hand.
Simon und Fern: Und jetzt sehe ich es auch: es steht da "Kantenmenge {1,2,3,4,5}" und "Knoten (= Ecken) (3,5), (4,5)". Dann ist aber wieder von Relation auf den "Kanten (i,j)" die Rede.
Simon: Ich würde sagen, die Matrix, die du aufgeschrieben hast, ist die Inzidenzmatrix des ungerichteten Graphen, wie ich ihn zuerst verstanden habe.
Die Adjazenzmatrix wäre dann (Begründung siehe oben)
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
wobei die Reihenfolge der Kanten
{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4} ist.
Kann es sein, das du die Aufgabe nicht ganz korrekt aufgeschrieben hast und es sich eventuell um den "Kantengraph" eines Graphen handelt? Dann wäre alles, was ich oben gechriebnen habe, Quatsch.
Bitte überprüf das noch einmal. |
Fern
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 21:29: |
|
Hallo Simon,
Meiner Ansicht nach muss die Inzidenzmatrix des gerichteten Graphen (Zaph zuliebe!) wie folgt aussehen:
1 2 3 4 5
(1,2) -1 1 0 0 0
(1,3) -1 0 1 0 0
(1,4) -1 0 0 1 0
(1,5) -1 0 0 0 1
(2,3) 0 -1 1 0 0
(2,4) 0 -1 0 1 0
(2,5) 0 -1 0 0 1
(3,4) 0 0 -1 1 0
In jeder Zeile steht einmal -1 und einmal 1 sonst Nullen.
Im Allgemeinen (allgemeinen?) kann man die Richtung der Kanten willkürlich festlegen. In unserem Beispiel sind sie aber so geordnet, wie ich sie blau an den Rand der Matrix geschrieben habe.
=============
Aufruf an Zaph: Überprüfe mal bitte meine Matrix.
An Simon: Verlass dich nicht zu sehr auf mein Resultat, denn ich bin kein Experte. |
Simon
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 21:48: |
|
Sorry, in der Angabe ist beim Satz "Entferne aus dem vollständigen (ungerichteten) Graphen Kantenmenge {1,....,5} die Knoten (3,5),(4,5)."
Kante- und Knoten durchgestrichen.
Ich glaub, du müsstest Recht haben mit deiner obigen Erklärung. Klingt jedenfalls ziemlich plausibel.
Nur deine Adjazenzmatrix verstehe ich nicht ganz. Wie kommst du auf die 8 Spalten?
Ciao,
Simon |
Fern
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 21:53: |
|
Hallo nochmals,
Ich habe meine Matrix abgeschickt bevor ich diejenige von Zaph gesehen habe.
Wir scheinen Inzidenz- und Adjazenzmatrix zu verwechseln.
Ich habe nur ein englischsprachiges Buch: dort ist nur von
Connectivity matrix
und
Incidence matrix die Rede.
Dort steht auch, dass Inzidenz Matrix nur für gerichtete Graphen aufgestellt werden kann.
Die von Simon aufgestellte Matrix entspricht genau der "Connectivity Matrix".
=====================
Graf steht tatsächlich nicht im Duden. Nur der Hinweis auf die allgemeine Regel, die jedoch etwas vage formuliert ist. Also bleiben wir doch bei Graph.
Im Duden steht übrigens auch nichts unter "Adjazent". |
Fern
| | Veröffentlicht am Donnerstag, den 14. September, 2000 - 07:59: |
|
Hallo Simon,
Hier ist auch noch eine Skizze unseres Graphen - so wie ich ihn interpretiere:
 |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 15. September, 2000 - 17:16: |
|
Hi,
der Fremdwörterduden definiert
Adjazent = Anwohner, Anrainer, Grenznachbar,
adjazieren = ("bei od. neben etwas liegen"): angrenzen
inzident = im Verlauf einer Angelegenheit nebenbei auffallend, zufällig
Inzidenz = Eintritt (eines Ereignisses), Vorfall
Wie auch immer. Simon hatte Recht mit der Adjazenzmatrix. Ich habe die beiden Begriffe verwechselt.
Jetzt verstehe ich auch, was es mit der Relation auf sich hat. Die Kanten sollen in eine Reihenfolge gebracht werden. Die Inzidenzmatrix hat für jede Ecke eine Zeile und für jede Kante eine Spalte. Deshalb hat die Inzidenmzmatrix acht Spalten. Die Zeile Nr. i entspricht der Ecke Nr. i. Um zu sagen, welche Kante der ersten, zweiten,..., achten Spalte entspricht, müssen die Kanten durchnummeriert werden. Die Nummerierung geschieht nach der angegebenen Relation. Das liefert die Reihenfolge
{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}
der Kanten. Zufälligerweise ist das genau die Reihenfolge, die ich und Fern oben angenommen haben. Die Matrix von oben mit den acht Spalten ist also die Inzidenzmatrix.
Ob die Inzidenzmatrix 8 Zeilen und 5 Spalten oder wie bei Fern 8 Spalten und 5 Zeilen hat, weiß ich nicht genau.
Fern, in deinem Bild müssen die Pfeile an den Kanten entfernt werden, da der Graph ungerichtet ist. In deiner Matrix sind die "-1" durch "1" zu ersetzen. Gleiche Begründung. |
Fern
| | Veröffentlicht am Freitag, den 15. September, 2000 - 17:53: |
|
Hi Zaph,
Du hast Recht: der Graph ist nicht gerichtet.
Ich habe zwar die angegebene Relation sofort durchschaut aber fälschlicherweise gemeint, mit geordneten Kanten sei der Graph gerichtet.
Also Pfeile weg (und -1 weg).
Ob in der Matrix die Ecken als Spalten oder Zeilen angeschrieben werden, ist vielleicht nur Konventionssache.
Obwohl das Wort "adjacent" im Englischen ein durchaus bekanntes Vokabel ist, wird die Adjazenzmatrix dort "connectivity matrix" genannt.
Gruß, Fern |
Fern
| | Veröffentlicht am Freitag, den 15. September, 2000 - 18:15: |
|
Hi Zaph und Simon,
Ich habe eine interessante Webseite gefunden (allerdings Englisch):
http://www.go.com/?win=_search&sv=M6&lk=noframes&nh=10&ud9=IE5&qt=%22graph+theory%22&oq=&url=http%3A//www.utc.edu/%7Ecpmawata/petersen/&ti=Graph+Theory+Lessons&top=
Dort wird übrigens die Matrix "Adjacency Matrix" genannt.
In Lesson 7 gibt es ein Applet, mit dem man einen Graph zeichnen kann und automatisch die zugehörige Adjazent Matrix angezeigt bekommt! |
|
