0 Daumen
346 Aufrufe

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

Avatar von

Was ist \(B_{2n,2n}\)?

Und was genau meinst du mit Zerlegen?

Wenn ich für n = 1 einsetze, bekomme ich den bipartiten Graph B2,2 und kann diesen in 1 (12) Kreis zerlegen, also ich kann mit den Kanten und Knoten aus B2,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:

B2,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 nrichtig. Da ich aus dem Graphen nur einen Kreis bilden kann (1)2.

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 B2n,2n n2 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

1 Antwort

0 Daumen

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

Avatar von 13 k

Danke für eure Hilfe

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community