Graphentheorie
-
Hi,
ich habe 2 Aufgaben ich habe das Skript gelesen, aber dazu steht nichts drin.
a) Beweisen Sie: Ein Knoten v, der nicht in einem Zyklus enthalten ist und
dessen Eingangsgrad nicht 0 ist, kann nicht Element der Knotenbasis sein.b) Beweisen Sie: Ein azyklischer Graph hat eine eindeutig bestimmte Knotenbasis.
Speziell zu a) kann ich Garnichts sagen.
Vielleicht hat da jemand einen Ansatz, aber bitte nicht zu mathematisch
Danke
-
a) ist eigentlich ziemlich einfach. Ich trau mich gar nicht, irgendwas zu verraten. Was genau ist denn dein Problem? Die Aufgabenstellung schreit ja schon nach einem Widerspruchsbeweis.
-
mhh weiß nicht, wenn ich einen Zyklus
hätte von mir aus <2,3,2> und 4 nicht im Zyklus liegt, dann gehört der halt
nicht zu den Basisknoten.
-
Was ist denn eine Knotenbasis?
-
Wenn ich es richtig verstanden habe, muss ein Pfad existieren zu den Knoten.
also wenn ich 1 -><- 2 -> 4, dann wäre 1,2,1 mein Zyklus aber von 4 führt
kein Pfad zur 1 oder 2.
-
adonis schrieb:
Wenn ich es richtig verstanden habe, muss ein Pfad existieren zu den Knoten.
Ja. Es wäre aber besser, wenn du das in ganzen Sätzen formulierst. So ungefähr wie "Eine Knotenbasis ist eine Teilmenge B von V mit der Eigenschaft, dass 1) für jeden Knoten v ein Element b von B existiert, so dass es einen Pfad von b nach v gibt und 2) ..."
Ja, eine -- auch für die Aufgabe wesentliche -- Eigenschaft fehlt noch. (Falls du Basen von Vektorräumen kennst, hast du gerade quasi nur die Eigenschaft als Erzeugendensystem gefordert, aber noch keine lineare Unabhängigkeit.)
also wenn ich 1 -><- 2 -> 4, dann wäre 1,2,1 mein Zyklus aber von 4 führt
kein Pfad zur 1 oder 2.Und was sagt das aus?
BTW du verbeißt dich zu sehr in den Zyklus. Die Aufgabe dreht sich um den Knoten v, der sich u.a. *nicht* in einem Zyklus befindet. Es kann also auch sein, dass es überhaupt keine Zyklen gibt.
-
Hier steht noch B ist minimal, d.h. keine echte Teilmenge von B hat diese Eigenschaft. <- Was soll das bedeuten?
Also ein Knoten wäre auch kein Basisknoten.
und der letzte Knoten wenn es keinen Zyklus gibt, wäre auch keiner?
-
adonis schrieb:
Hier steht noch B ist minimal, d.h. keine echte Teilmenge von B hat diese Eigenschaft. <- Was soll das bedeuten?
Das bedeutet, dass B keine Basis mehr ist, wenn du einen Knoten herausnimmst. Das heißt im Umkehrschluss, solange man noch Knoten herausnehmen kann, ohne dass die Erzeugungseigenschaft (also dass der gesamte Graph von B aus erreichbar ist) verloren geht, es keine Basis sein kann.
Also ein Knoten wäre auch kein Basisknoten.
und der letzte Knoten wenn es keinen Zyklus gibt, wäre auch keiner?Versteh ich nicht.