Bipartiter Graph

Beschreibung

Ein bipartiter oder paarer Graph ist ein Graph für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.

Definition

Ein Einfacher Graph $G=(V,E)$ heißt bipartit falls sich dessen Knoten in zwei Teilmengen zerlegen lassen und die Knoten innerhalb der Teilmengen nicht durch Kanten verbunden sind.

Eigenschaften

Automorphismengruppe

Gilt $n\ne m$, dann ist die Automorphismengruppe isomorph zum direkten Produkt zweier Symmetrische Gruppe: $Aut(G_{n,m})=S_n\times S_m$

Gilt $n=m$ so kann man zusätzlich beide Mengen vertauschen, man erhält also $Aut(G_{n,n})=S_n\times S_n\times C_2$

lit_clayOfficeHoursGeometric2017