Powyższy problem wiąże się z rozdziałem 10. Combinatorial Designs (Introductory Combinatorics, Richard A. Brualdi)Dla jakich \(\displaystyle{ n}\) może istnieć rozkład grafu \(\displaystyle{ K_n}\) na trójkąty? Sprawdź czy rozkład ten jest możliwy dla grafów \(\displaystyle{ K_6}\) oraz \(\displaystyle{ K_7}\). Jeśli tak, podaj parametry otrzymanych konfiguracji oraz skonstruuj ich macierze.
Uwaga: mówimy, że graf jest rozkładalny na trójkąty, jeżeli w grafie tym istnieje zbiór krawędziowo rozłącznych trójkątów pokrywających wszystkie jego krawędzie.
Korzystając z wiadomości z teorii grafów:
Graf pełny posiada \(\displaystyle{ \binom{n}{2}}\) krawędzi.
Dla wygody, bez straty ogólności, niech graf pełny będzie n-kątem foremnym ze wszystkimi przekątnymi.
Rozkładu grafu dokonamy w taki sposób, że jedną krawędzią (bokiem trójkąta) będzie bok \(\displaystyle{ n}\)-kąta, natomiast pozostałe 2 krawędzie będą tworzyć dwie przekątne wychodzące z dwóch różnych wierzchołków wybranego już boku i mające punkt wspólny w przeciwległym wierzchołku.
W ten sposób otrzymujemy następujące ograniczenie:
\(\displaystyle{ \binom{n}{2} = 3n \\
n(n-1)=6n \\
n^2-7n=0 \\
n=0 \vee n=7}\)
Tak więc, możemy dokonać rozkładu grafu \(\displaystyle{ K_7}\) na 7 krawędziowo rozłącznych trójkątów pokrywających wszystkie jego krawędzie.
Graficznie rozkład wygląda następująco:
Jeśliby ponumerować wierzchołki, trójkąty możemy rozpisać w następujących blokach:
\(\displaystyle{ B_1=\{1,2,6\}, B_2=\{2,3,7\}, B_3=\{3,4,1\}, B_4=\{4,5,2\}, B_5=\{5,6,3\}, \\ B_6=\{6,7,4\}, B_7=\{7,1,5\}}\)
Macierz incydencji:
\(\displaystyle{ \begin{tabular}{l|lllllll}
& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
B_1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\
B_2 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
B_3 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\
B_4 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
B_5 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
B_6 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
B_7 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\
\end{tabular}}\)
Parametry otrzymanej konfiguracji to: \(\displaystyle{ (7, 7, 3, 3, 1)}\)\(\displaystyle{ \text{BIBD}(n,b,r,k,\lambda)}\) - konfiguracja \(\displaystyle{ (n,b,r,k,\lambda)}\), gdzie \(\displaystyle{ n}\) - liczba wierzchołków, \(\displaystyle{ b}\) - liczba bloków, \(\displaystyle{ r}\) - liczba bloków, w których znajduje się ustalony wierzchołek, \(\displaystyle{ k}\) - liczba elementów w bloku, \(\displaystyle{ \lambda}\) - liczba bloków w których znajduje się ustalona para wierzchołków.
Powinno być dobrze, ale będę wdzięczny za sprawdzenie.
Z góry dzięki.