Definition 2.2 (Vollst¨andiger Graph)  Ist |E| = n und K = E 2 , so spre- chen wir von einem vollst¨andigen Graphen K_n. Definition 2.3 (Bipartiter Graph)  Falls E aus zwei disjunkten Mengen S und T  besteht, und jede Kante eine Ecke aus S und eine andere in T  hat, so nennen wir den Graphen G(S +T, K) bipartit. Weiterhin sprechen wir von einem  vollst¨andigen bipartiten Graphen  K_S,T , falls alle Kanten zwischen  S und T  vorhanden sind. S T Abbildung 2: Ein bipartiter Graph Definition 2.4 (Weg)  Ein Weg P_n in einem Graphen besteht aus einer Fol- ge von verschiedenen Ecken  u₁, u₂, . . . , u_n  mit  u_iu_i+1    E. Die L¨ange des Weges ergibt sich aus der Anzahl der Kanten, also n - 1. Definition 2.5 (Kreis)  Ein Kreis C_n ist eine Folge von verschiedenen Ecken u₁, u₂, . . . , u_n, u₁, also ein geschlossener Weg. 3   Wege und Kreise Definition 3.1 (Untergraph)  Sei G(E, K) ein Graph. Dann nennen wir den Graphen  H(E⁰, K⁰)  Untergraph von G, wenn  E⁰    E und K⁰    K. Enth¨alt H alle Kanten zwischen den Ecken von E⁰, die auch in G vorhanden sind, dann heißt H  induzierter Untergraph. Definition 3.2 (Zusammenhangskomponenten)  Ein Knoten v   E ist erreichbar  von  u     E, wenn es einen Weg  P  in  G  von  u  nach  v  gibt. Die Erreichbarkeit bildet eine^¨ Aquivalenzrelation auf E dar, die induzierten Un- tergraphen bilden die^¨ Aquivalenzklassen, wir nennen sie  Zusammenhangs- komponenten. 2