Konstruktion auflösbarer Fast-Blockpläne mit Hilfe eines Computers Ute Vogel

Im Jahre 1968 wurde im Bulletin de l’Association des Professeurs de Mathématiques Nr. 260, 1968, S. 32 das folgende Problem gestellt:

24 Teilnehmer einer Tagung möchten 8 Tage lang zusammen an Tischen für je 4 Personen zu Mittag essen.

Kann man einen Sitzplan so aufstellen, daß jede Person mit jeder anderen wenigstens einmal zusammen am Mittagstisch sitzt?

Dieses Sitzplan-Problem führt auf den Begriff des Fast-Blockplanes, einer Inzidenzstruktur, die von G. Pickert und K. E. Wolff in den Arbeiten [Pic,70] bzw. [Wol,73] definiert und untersucht worden ist.

Im folgenden wird eine Eigenschaft der Parallelismen von Fast-Blockplänen hergeleitet, die bei der Konstruktion auflösbarer Fast-Blockpläne mit Hilfe eines Backtracking-Algo-rithmus die Laufzeit erheblich herabsenkt.

Sei I = (P, B, I) ein Inzidenzstruktur (P ∩ B = ∅). Die betrachteten Inzidenzstrukturen I seien stets endlich, d.h. es gelte v ⇋ |P| ∈ IN und b ⇋ |B| ∈ IN, wobei IN die Menge der positiven ganzen Zahlen bezeichnet. Für P ⊆ P sei

(P) ⇋ {C ∈ B | ∀p ∈ P : pIC}

und [P] ⇋ |(P)| die Verbindungszahl von P. Analog sei für B ⊆ B

(B) ⇋ {p ∈ P | ∀C ∈ B : pIC}

und [B] ⇋ |(B)| die Schnittzahl von B.

Für die Menge {p_{1}, .., p_{n}} ⊆ P schreibt man statt ({p_{1}, .., p_{n}}) auch einfach (p_{1}, .., p_{n}) und entsprechend für die Verbindungszahl [p_{1}, .., p_{n}], analog für {C_{1}, .., C_{m}} ⊆ B.

Sei I = (P, B, I) eine Inzidenzstruktur. Ein Parallelismus von (P, B, I) ist eine Äquivalenzrelation ∥⊆ B × B, die dem ,,Parallelenaxiom“

∀p ∈ P ∀B ∈ B ∃_{1}C ∈ B : pIC ∧ C ∥ B

genügt. Die Äquivalenzklassen heißen Parallelenscharen. Inzidenzstrukturen, die einen Parallelismus besitzen, werden auflösbar genannt.

Eine taktische Konfiguration ist eine Inzidenzstuktur (P, B, I) für die gilt:

∃k, r ∈ IN ∀pP : [p] = r ∧ ∀B ∈ B : [B] = k.

Im Falle r = k nennt man die taktische Konfiguration symmetrisch (kurz: STK).

Eine taktische Konfiguration I = (P, B, I) heißt zerlegbar, wenn eine Äquivalenzrelation ∼⊆ P × P existiert, die eine Zerlegung der Punktmenge in m > 1 Klassen von je n > 1 Elementen derart induziert, daß

∃λ_{1}, λ_{2} ∈ IN_{0} ∀p, q ∈ P : ( p ∼ q ∧ p ≠ q ⇒ [p, q] = λ_{1})
∧ ( p ≁ q ⇒ [p, q] = λ_{2})

gilt.

Nach [Pic,70] und [Wol,73] wird eine taktische Konfiguration, die den Bedingungen

(FB1) ∀p, q ∈ P : [p, q] ≥ 1

und (FB2) r · (k − 1) = v

genügt, als Fast-Blockplan bezeichnet. Für Fast-Blockpläne gelten die folgenden Parameterbedingungen (vgl. [Wol,73] 1.3):

(1) ∀p ∈ P ∃_{1}p^{∼} ∈ P\{p} : [p, p^{∼}] = 2,

(2) ∀p, p^{∼}, q ∈ P : p ≠ q ≠ p^{∼} ∧ [p, p^{∼}] = 2 ⇒ [p, q] = 1,

(3) ∀B, C ∈ B : B ≠ C ⇒ [B, C] ≤ 2.

(1) und (2) zufolge sind Fast-Blockpläne mit v > 2 zerlegbare taktische Konfigurationen mit λ_{1} = 2, λ_{2} = 1, m = \frac{v}{2} und n = 2. Da zwei Punkte eines Blockplanes stets dieselbe Verbindungszahl besitzen, stellen Fast-Blockpläne i.a. keine Blockpläne dar.

Ist der Fast-Blockplan (P, B, I) auflösbar und bezeichnet s die Anzahl der Blöcke einer Parallelenschar, so gilt offenbar v = s · k.

Sei F = (P, B, I) ein auflösbarer Fast-Blockplan mit v > 2. Dann existieren mindestens zwei Parallelenscharen S_{1}, S_{2} ⊆ B derart, daß für je zwei Blöcke B, C dieser Parallelenscharen [B, C] ≤ 1 gilt (vgl. [Vog,89] (2.19)).

Für einen Fast-Blockplan F = (P, B, I), dessen Blockmenge B zwei disjunkte Teilmengen S_{1}, S_{2} mit den Eigenschaften

⋃_{B∈S_{i}}(B) = P, |S_{i}| = s für i ∈ {1, 2} und ∀B_{1} ∈ S_{1}, B_{2} ∈ S_{2} : [B_{1}, B_{2}] ≤ 1

enthält, wird die Inzidenzstruktur (P, S_{1} ∪S_{2}, I|_{P×S_{1}∪S_{2}}) als Startkonfiguration I_{F} von F bezeichnet.

Eine Startkonfiguration eines Fast-Blockplanes stellt eine taktische Konfiguration mit r = 2 dar. Ist der Fast-Blockplan F auflösbar und gilt v > 2, so können stets zwei Parallelscharen als S_{1} und S_{2} gewählt werden.

Der realisierte Algorithmus erweitert eine gegebene Startkonfiguration durch sukzessive Konstruktion weiterer Parallelenscharen zu einem auflösbaren Fast-Blockplan. Um zu den vorgegebenen Parametern alle auflösbaren Fast-Blockpläne zu konstruieren, muß das Verfahren auf alle möglichen Startkonfigurationen dieses Fast-Blockplanes angesetzt werden. Zur Bestimmung der Startkonfigurationen betrachtet man symmetrische taktische Konfigurationen, denn jede Startkonfiguration I_{F} = (P, S_{1} ∪ S_{2}, I_{F}|_{S_{1}∪S_{2}}) eines Fast-Blockplanes F = (P, B, I_{F}) definiert durch I ⇋ (S_{1}, S_{2}, I) mit

B_{1}IB_{2} ⇋ (B_{1}) ∩ (B_{2}) ≠ ∅ für B_{1} ∈ S_{1} und B_{1} ∈ S_{2}

eine symmetrische taktische Konfiguration mit v′ = b′ = |S_{1}| und r′ = k′ = k. Umgekehrt erhält man aus jeder symmetrischen taktischen Konfiguration I = (P, B, I) mit den Parametern |P| = s und [p] = k für p ∈ P durch

P′ ⇋ I, B′ ⇋ P ∪ B sowie I′ ⇋ {((x, y), z)|x = z ∨ y = z} ⊆ P′ × B′ eine auflösbare taktische Konfiguration (P′, B′, I′) mit v′ = s · k, k′ = k, r′ = 2 und den beiden Parallelenscharen S_{1} ⇋ P, S_{2} = B. Außerdem liefert eine STK I = (P, B, I) mittels pI^{c}B ⇋ ¬(pIB) wieder eine STK I_{c} = (P, B, I^{c}) mit den Parametern v_{c} = v und k_{c} = v − k. Beispiel: Transformation einer Startkonfiguration in die STK I und I^{c}

A_{4} d_{3} d_{2} d_{1}  b_{1} b_{2}  b_{3} a_{1} a_{2} a_{3} c_{1} c_{2} c_{3} A_{1}  A_{2} A_{3} B_{1}  B_{2} B_{3}  B_{4}  A_{1}  A_{2} A_{3} A_{4}  B_{1} B_{2} B_{3} B_{4}  A_{3} A_{4} A_{1}  A_{2} B_{2} B_{1} B_{4}  B_{3}

Startkonfiguration I_{F} = (P_{F} , B_{F} , ∈)  STK I = (P, B, I)  STK I^{c} = (P_{c}, B_{c}, I_{c})
eines Fast-Blockplanes F  v = b = s = 4,  v_{c} = b_{c} = 4,
mit k_{F} = 3, r_{F} = 6 und s_{F} = 4.  k = r = k_{F} = 3  k_{c} = r_{c} = 1,
P_{F} = {a_{i}, b_{i}, c_{i}, d_{i}|i ∈ {1, 2, 3, 4}}  P = S_{1}  P_{c} = P
S_{1} = {{a_{1}, a_{2}, a_{3}}, {b_{1}, b_{2}, b_{3}}, {c_{1}, c_{2}, c_{3}}, {d_{1}, d_{2}, d_{3}}} B = S_{2}  B_{c} = B
= {A_{1}, A_{2}, A_{3}, A_{4}}  A_{i}IB_{j} ⇋ (A_{i}) ∩ (B_{j}) ≠ ∅ A_{i}I_{c}B_{j} ⇋ ¬(A_{i}IB_{j})

S_{2} = {{a_{1}, b_{1}, c_{1}}, {a_{2}, b_{2}, d_{1}}{a_{3}, c_{2}, d_{2}}, {b_{3}, c_{3}, d_{3}}} = {B_{1}, B_{2}, B_{3}, B_{4}} B_{F} = S_{1} ∪ S_{2}.

Im folgenden werden taktische Konfigurationen (P, B, I), in denen eine Punktmenge P′ ⊂ P existiert so, daß (P′, B′, I‘) mit B′ ⇋ ⋃_{p∈P′}(p) sowie I′ ⇋ I|_{P′×B′} eine taktische Konfiguration darstellt, reduzibel genannt, anderenfalls irreduzibel. Die in einer reduziblen taktischen Konfiguration enthaltenen irreduziblen taktischen Konfigurationen nennt man Teilkonfigurationen.

Beispiel:

1 2 3 4 5

Die symmetrische taktische Konfiguration

I = ({1, 2, 3, 4, 5},

{({1, 2}, 1), ({1, 2}, 2), ({3, 4}, 1), ({3, 5}, 1), ({4, 5}, 1})}, I) mit pI(B, n) ⇋ p ∈ B ist reduzibel und zerfällt in die zwei Teilkonfigurationen mit P_{1} = {1, 2} und P_{2} = {3, 4, 5}.

Kennt man die Anzahl ζ(v, k) der irreduziblen STK mit den Parametern v und k, die nicht zueinander isomorph sind, so kann nach Satz 2.10 aus [Vog,89] die Anzahl σ(v, k) aller untereinander nichtisomorphen STK berechnet werden.

Für k = 1 ist lediglich die STK mit v = b = 1 irreduzibel, und es gilt ζ(v, 1) = 0 für v > 1, woraus man σ(v, 1) = 1 für v ≥ 1, d.h. es existiert stets – bis auf Isomorphie – nur eine STK mit k = 1 und v ≥ 1.

Im Fall k = 2 ist jede irreduziblen STK mit v ≥ 2 Punkten isomorph zu der STK R(v) = (P, B, I) mit

P ⇋ {p_{1}, .., p_{v}}, B ⇋ {{{p_{i}, p_{i+1}}|i = 1, .., v − 1}} ∪ {{p_{1}, p_{v}}} und I ⇋∈.

v − 1  v  1  2  3 4 5 v − 2 R(v)

Insbesondere ist also ζ(v, 2) = 1 für v ≥ 2.

Beispiele:

1) Mögliche Startkonfigurationen eines Fast-Blockplanes F mit k = 3 und r = 6

F besitzt (FB2) zufolge v = 6 · (3 − 1) = 12 Punkte. Jede Parallelenschar besteht daher aus s = \frac{v}{k} = 4 Blöcken.

Eine Startkonfiguration von F definiert somit eine STK I mit 4 Punkten und k = 3. Aus dieser gewinnt man wie oben angegeben die STK I^{c} mit v = 4 und k = 1. Wegen σ(v, 1) = 1 für v ≥ 1 ist I^{c} eindeutige bestimmt, also auch die Startkonfiguration I. Diese Startkonfiguration kann durch Konstruktion weiterer Parallelenscharen nicht zu einem Fast-Blockplan erweitert werden. Somit kann kein auflösbarer Fast-Blockplan mit k = 3 und r = 4 existieren.

2) Startkonfigurationen eines Fast-Blockplanes F mit k = 4 und r = 8

Ein Fast-Blockplan mit diesen Parametern beschreibt das eingangs erwähnte Sitzplan-Problem. Wegen v = 24 besteht jede Parallelenschar aus s = 6 Blöcken. Aus einer Startkonfiguration von F erhält man daher eine STK I mit 6 Punkten und k = 4. Der Übergang zur STK I^{c} liefert die Parameter v_{c} = 6 und k_{c} = 2. Damit kann die Anzahl der nichtisomorphen dieser STK mit Hilfe von σ(6, 2) = 4 berechnet werden.

5  ^{6}^{3}  ^{4}^{1}  ^{2} I_{1}^{c}  ^{5}  ^{6}^{1}  ^{2}  ^{3}^{4} I_{2}^{c}  ^{4}^{5}^{6}  ^{3}^{2}^{1} I_{3}^{c}  ^{5}^{6}  ^{1}  ^{2}^{3}^{4} I_{4}^{c}

Somit existieren für den Fast-Blockplan F lediglich vier Startkonfigurationen. Ob eine dieser Startkonfigurationen zum Fast-Blockplan F erweitert werden kann, konnte aufgrund der hohen Zeitbedarfs des verwendeten Backtracking-Algorithmus noch nicht festgestellt werden.

Literatur:

[Pic,70] G. Pickert, Remarques ur une classe de structures géometriques finies, Séminaire d’algebre non

commutative, Conférence n^{o} 14 du 3 mars 1970.

[Wol,73] K. E. Wolff, Fast Blockpläne, Mitt. math. Sem. Giessen 102 (1973). [Vog,89] U. Vogel, Algorithmen zur Konstruktion auflösbarer Fast-Blockpläne mit Hilfe eines Computers,

Diplomarbeit, TU Clausthal, 1989.