Zusammenhangskomponenten im graphischen Matroid

23.02.2014, 14:43	Kathy93	Auf diesen Beitrag antworten »
Zusammenhangskomponenten im graphischen Matroid Meine Frage: Für einen Graphen G bezeichne c(G) die Anzahl der Zusammenhangskomponenten. Man beweise mittels Aussagen über die Rangfunktion im graphischen Matroid die folgende Ungleichung für die Graphen $\begin{eqnarray} G_1=(V,E_1), G_2=(V,E_2), G_1\cap G_2=(V,E_1\cap E_2), G_1\cup G_2=(V,E_1\cup E_2) \end{eqnarray}$ : $\begin{eqnarray} c(G_1) + c(G_2)\leq c(G_1\cup G_2)+c(G_1 \cap G_2) \end{eqnarray}$ Meine Ideen: Ich muss sicherlich irgendwie mit der Submodularität der Rangfunktion arbeiten, doch weiß ich leider nicht genau, wie das gehen soll. Kann mir da vielleicht einer helfen? Vielen Dank im Voraus!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »