Aufgabe:
Es sei die Relation ≤G für einen beliebigen Graphen auf der Menge Seiner Teilgraphen wie folgt diefiniert
Seien H1,H2 ∈ G. dann gilt.
H1 ≤G H2 <==> H1 Teilgraph von H2.
a) zeigen dass ≤G Partielle Ordnung ist
b) Geben Hasse-Diagramm von ≤G für den gegebenen graph an
a---b---c
c) Welche Höhe hat die Partielle Ordnung für einen beliebigen Graphen ? begründen sie Ihre Antwort
Problem/Ansatz:
zu a ist offensichtlich klar
da jeder Graph ist ein Teilgraph von sich selbst (reflexivität gilt).
wenn ein graph x1 ist teilgraph von x2 und x2 teilgraph von x1 dann muss x1=x2 (antisymmetrie gilt)
wenn x1 teilgraph von x2 und x2 teilgraph von x3 dann ist auch x1 teilgraph von x3 (T gilt)
b ) abc
ab bc
/ \ / \
a b c
c) die Antwort ist n wobei n = anzahl die Knoten . weil ein graph kann max. n-1 Teilgraphen haben.
hab ich das richtig verstanden?
Würde mich freuen auf eure Hilfe.
