Zum Inhalt springen

Graph/Paarungen/Symmetrische Differenz/Fakt

Aus Wikiversity

Es sei  G=(V,E)  ein Graph und seien P und Q Paarungen in G. Es sei H derjenige Graph auf V, dessen Kantenmenge die symmetrische Differenz von P und Q ist.

Dann sind die Zusammenhangskomponenten von H von einer der folgenden Gestalt.

  1. Ein isolierter Punkt.
  2. Ein linearer Graph, wobei die Kanten abwechselnd zu P bzw. zu Q gehören.
  3. Ein Kreis mit gerader Länge, wobei die Kanten abwechselnd zu P bzw. zu Q gehören.