Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » eulersche und hamiltonsche Digraphen
Druckversion
Druckversion
Autor
Universität/Hochschule J eulersche und hamiltonsche Digraphen
Kolibri1990
Junior Letzter Besuch: im letzten Monat
Dabei seit: 03.01.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-10-30


Hallo,

ich habe folgende Aufgabe zu lösen und habe einfach keine Idee.
Wir definieren den Digraphen fed-Code einblenden
fed-Code einblenden fed-Code einblenden fed-Code einblenden fed-Code einblenden fed-Code einblenden fed-Code einblenden fed-Code einblenden
fed-Code einblenden

A) Zeigen sie dass fed-Code einblenden
B) Zeigen sie dass fed-Code einblenden

Ich bin etwas verwirrt, wie ich das machen soll bzw in meinem Verständnis ist der Graph nicht eulersch oder hamiltonsch. Wenn ich zum Bsp. 4 Vektoren betrachte mit den fed-Code einblenden fed-Code einblenden fed-Code einblenden fed-Code einblenden
Dann habe ich 2 Bögen mit fed-Code einblenden
fed-Code einblenden fed-Code einblenden
fed-Code einblenden

, aber ich kann diese Knoten nicht noch untereinander verbinden, oder? Vielleicht übersehe ich etwas... Und vor allem wie würde man den Beweis dann machen? Eulersch über den eulerschen Knotengrad = 0?

Danke schonmal!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6410
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-10-30


Hallo Kolibri1990,

ich nehme an, du betrachtest bei deinem Beispiel \(D_{(3,3)}\). Dieser Graph besitzt ja außer u1, u2, u3 und u4 noch 23 weitere Knoten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kolibri1990
Junior Letzter Besuch: im letzten Monat
Dabei seit: 03.01.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-11-02 18:52


mhm ok danke schonmal für die Info. Das hatte ich wirklich falsch verstanden. Danke. Ich versuche es nochmal und frage nochmal nach wenn ich nicht weiter komme :)

Gruß, Kolibri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kolibri1990
Junior Letzter Besuch: im letzten Monat
Dabei seit: 03.01.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-11-03 19:14


Hallo

ich nochmal. Soweit habe ich den ersten Teil der Aufgabe gelöst und bewiesen, dass der gegebene Digraph eulersch ist, da jeder Knoten den Eulergrad 0 hat.

Nun muss ich noch zeigen, dass der Digraph hamiltonsch ist.
Hier bin ich etwas überfragt.

Ich weiß D ist hamiltonsch wenn er stark zusammenhängend ist. (wenn in D je zwei Knoten verbindbar sind)
Kann ich dann begründen, dass dadurch, dass er eulersch ist ich also jede Kante abfahren kann, er auch hamiltonsch sein muss. Da ich um jeden Bogen abzufahren auch jeden Knoten abfahren muss?

Danke schonmal im Voraus!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6410
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-11-03 19:41


Hallo,

2020-11-03 19:14 - Kolibri1990 in Beitrag No. 3 schreibt:
1) Ich weiß D ist hamiltonsch wenn er stark zusammenhängend ist. (wenn in D je zwei Knoten verbindbar sind)

2) Kann ich dann begründen, dass dadurch, dass er eulersch ist ich also jede Kante abfahren kann, er auch hamiltonsch sein muss. Da ich um jeden Bogen abzufahren auch jeden Knoten abfahren muss?

1) Das ist nicht richtig. Nur die Umkehrung gilt.

2) Auch das ist nicht richtig. Bei einem hamiltonschen Weg wird jeder Knoten einmal und nur einmal durchlaufen. Das ist bei einem eulerschen Kantenzug nicht der Fall.

Vielleicht suchst du in \(D_{(3,3)}\) mal nach einem hamiltonschen Weg. Möglicherweise liefert das ja Ideen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kolibri1990 hat die Antworten auf ihre/seine Frage gesehen.
Kolibri1990 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]