Sry, habe die Betragsstriche vergessen:
Wenn (V1⊆V2 ∧ E1⊆E2), dann |V1|≤|V2| und |E1|≤|E2|.
Weil auch |V2|≤|V3| und |E2|≤|E3| muss auch |V1|≤|V3| und |E1|≤|E3| sein, weil |V1|≤|V2|≤|V3| => |V1|≤|V3| und |E1|≤|E2|≤|E3| =>|E1|≤|E3| gilt.
Es sei die Relation \( R(G,\sim)\) zweier Graphen (unger., mark.) mit
\(G_1 \sim G_2 \Leftrightarrow \) \(G_1\) ist Teilgraph von \(G_2\)
gegeben.
Beweisen Sie, dass \( R(G,\sim)\) eine partielle Ordnung (Poset) ist.
Reflexiv:
Legende: \(G=(V,E)\) Graph \(G\) mit \(V=\) Knoten, \(E=\) Kanten
(G1,G1) Wahr, weil jeder Graph auch Teilgraph von sich selber ist. (G1∼G1) weil V1⊆V2∧E1⊆E2 .
Antisymmetrisch:
(G1∼G2)∧(G2∼G1)=>G1=G2 <=> (V1⊆V2 ∧ E1⊆E2) ∧ (V2⊆V1 ∧ E2⊆E1) => (V1=V2 ∧ E1=E2) und demnach identisch, also G1=G2.
Transitiv:
(G1∼G2) ∧ (G2∼G3) => (G1∼G3)
(V1⊆V2 ∧ E1⊆E2) ∧ (V2⊆V3 ∧ E2⊆E3) => (V1⊆V3 ∧ E1⊆E3)
Wenn (V1⊆V2 ∧ E1⊆E2), dann V1≤V2 und E1≤E2.
Weil auch V2≤V3 und E2≤E3 muss auch V1≤V3 und E1≤E3 sein, weil V1≤V2≤V3 => V1≤V3 und E1≤E2≤E3 =>E1≤E3 gilt.
Refl., trans. und antisymm. erfüllt, also ist R eine partielle Ordnung (Poset).
Reicht das als Beweis?
MfG
Doesbaddel
EDIT: Sry, habe die Betragsstriche vergessen:
Wenn (V1⊆V2 ∧ E1⊆E2), dann |V1|≤|V2| und |E1|≤|E2|.
Weil auch |V2|≤|V3| und |E2|≤|E3| muss auch |V1|≤|V3| und |E1|≤|E3| sein, weil |V1|≤|V2|≤|V3| => |V1|≤|V3| und |E1|≤|E2|≤|E3| =>|E1|≤|E3| gilt.
