Lösungansatz bipartiter Graph Kreis

Question

ich möchte mit der vollst. Induktion beweisen, dass ich den bipartiten Graph B_2n,2n in n² Kreise zerlegen kann. Kann mir jemand einen Lösungansatz geben?

Comments

Was ist $B_{2n,2n}$?

Und was genau meinst du mit Zerlegen?

---

Wenn ich für n = 1 einsetze, bekomme ich den bipartiten Graph B_2,2 und kann diesen in 1 (1²) Kreis zerlegen, also ich kann mit den Kanten und Knoten aus B_2,2 einen Kreis bilden. Wenn ich für n andere n∈Ν einsetzte, bekomme ich bipartite Graphen die sich in mehr Kreise zerlegen lassen.

---

Hast du absichtlich nicht auf meine Fragen geantwortet oder war das nur ein Versehen?

---

Verstehe ich dich richtig, wenn ich annehme,
dass du nach der Anzahl Hamiltonscher Kreise
im vollstänigen bipartiten Graphen $K_{2n,2n}$
fragst?

---

Hallo,

nein ich habe es nicht absichtlich gemacht, vielleicht habe ich falsch verstanden was du möchtest @oswald.

Hamilton-Kreise haben wir noch nicht gemacht.

Wenn ich den IA mit n=1 mache habe ja:

B_2,2 z.B. der Graph mit den Knoten ABCD. AC und BD bilden die disjunkte Menge. Es lässt sich dann folgender Kreis bilden K = {AC,CB,BD,DA}.

Damit wäre n² richtig. Da ich aus dem Graphen nur einen Kreis bilden kann (1)².

Für n=2 wäre der Graph ABCDEFGH und aus dem Graphen kann ich 4 Kreise bilden. Mit zerlegen ist gemeint, dass ich alle Kanten benutze und schaue wieviel Teilgraphen ich machen kann, wobei hier der Teilgraph ein Kreis sein soll.

Die IV ist dann, so denke ich, dass sich aus dem bipariten Graphen B_2n,2n n² Kreise bilden lassen.

Hier weiß ich nicht weiter ...

---

Hamiltonkreis: siehe hier
https://de.wikipedia.org/wiki/Hamiltonkreisproblem

Ah. OK.

Du meinst Eulersche Touren, Eulerkreise:

https://de.wikipedia.org/wiki/Eulerkreisproblem

---

Danke für eure Hilfe

Answer 1

Hallo,

ich verstehe das so:

Wir haben den vollständigen bipartiten Graphen $G=(X \cup Y,E)$, wobei X und Y jeweils 2n Elemente enthalten. Wir such $n^2$ Teilgraphen $K_i=(X_i \cup Y_i,E_i)$, die Kreise sind - und zwar so, dass jede Kante aus E in genau einer der Kantenmengen $E_i$ enthalten ist.

Für n=1 ist der Graph ein Kreis - fertig.

Es sei also jetzt $G=(X \cup Y,E)$ der vollständige bipartite Graph mit jeweils (2n+2) Elementen, sagen wir mit $x_1, \ldots,x_{2n},x_{2n+1},x_{2n+2}$, y analog. Dann sei G' der Teilgraph von G mit den Knoten $x_1, \ldots x_{2n}$, y analog. Dafür gibt es n^2 Kreise nach Induktionsvoraussetzung.

Wir ergänzne diese Kreise durch

$$(\{x_{2i-1},x_{2i},y_{2n+1},y_{2n}\}, E_{1,i}) \text{ mit den benötigten Kanten aus E}, i=1, \dots n$$

$$(\{x_{2n+1},x_{2n},y_{2i-1},y_{2i}\}, E_{2,i}) \text{ mit den benötigten Kanten aus E}, i=1, \dots n$$

$$(\{x_{2n+1},x_{2n},y_{2n+1},y_{22}\}, E_0) \text{ mit den benötigten Kanten aus E}$$

Das sind 2n+1 Stück.

Gruß Mathhilf

Comments

Danke für eure Hilfe