Graphen und Menge von Untergraphen

Question

Es sei G ein ungerichteter Graph.

Sei U(G) die Menge aller Untergraphen von G

≤_G eine Binärrelation auf U(G), definiert durch H ≤_G F gdw H ein Untergraph von F ist, mit H, F ∈ U(G).

1. Zeigen Sie: G ist eine Halbordnung auf U(G).

2. Geben Sie ein Beispiel für einen Graphen G an, sodass G auf U(G) eine ltotale Ordnung ist und ein Beispiel G auf U(G) keine totale Ordnung ist.

Answer 1

zu 1.

≤_G ist reflexiv, weil jeder Graph Untergraph von sich selbst ist.

≤_G ist transitiv, weil mit F Untergraph von G und G Untergraph von H auch F Untergraph von H ist.

≤_G ist antisymmetrisch, weil wenn mit F Untergraph von G der Graph G alle Kanten und Knoten von F hat und mit G Untergraph von F der GRaph F alle Kanten und Knoten von G hat, also F=G sein muss.

zu 2.

Der Graph mit einem einzigen Knoten und keinen Kanten und der vollständige Graph mit 2 Knoten.