DISKRETE MATHEMATIK
Dr. E. Prisner, Dr. J. Sustal,
Dr. W. Preuß, S. Fröhlich,
Sommersemester 2000

6.1 Wir betrachten die Menge M aller endlichen 1-2 Folgen, d.h. aller Tupel (a₁,a₂,...,a_k) mit k N₀ und a_i {1,2} für alle i {1,2,...,k}. Wir betrachten die durch (a₁,a₂,...,a_k)* (b₁,b₂,...,b_m) = (a₁, a₂, ... ,a_k, b₁, b₂, ..., b_m) definierte binäre Verknüpfung "*" auf M. Außerdem sei eine binäre Relation "§" auf M durch (a₁,a₂,...,a_k)§ (b₁,b₂,...,b_m) falls a₁ + a₂ + ... + a_k = b₁ + b₂ + ... + b_m definiert.

• a) Zeigen Sie, daß § eine Kongruenzrelation bzgl. "*" ist.
• b) Finden Sie eine binäre Verknüpfung auf M, bzgl. der obiges § keine Kongruenzrelation ist.
• c) Geben Sie eine Äquivalenz(!)relation auf M an, die bzgl. "*" keine Kongruenzrelation ist.

6.2 Die Eckenmenge des Graphen G sei {1,2,...,17} und die Kantenmenge sei {{1,3}, {1,5}, {2,8}, {2,10}, {2,15}, {3,13}, {3,17}, {4,6}, {4,12}, {5,17}, {6,7}, {7,14}, {8,9}, {8,13}, {9,10}, {10,11}, {11,16}, {12,14}, {15,17}}. Ist G zusammenhängend? Ist G bipartit? Erlaubt G eine offene oder geschlossene Eulersche Linie?

6.3 Ein Graph ist 3-regulär, wenn die Grade aller Ecken 3 sind.

• a) Gibt es einen 3-regulären Graphen mit 11 Ecken?
• b) Gibt es einen 3-regulären Graphen mit 12 Ecken, bei dem der Abstand von je zwei Ecken höchstens 3 ist?
• c) (optional) Gibt es einen 3-regulären Graphen mit 12 Ecken, bei dem der Abstand von je zwei Ecken sogar höchstens 2 beträgt?

6.4 Für natürliche Zahlen p und q habe der Graph G(p,q) die Menge N der natürlichen Zahlen als Eckenmenge. Zwei natürliche Zahlen i und j sind in G benachbart, falls | i - j |= p oder | i - j |=q gilt.

• a) Ist G(3,5) zusammenhängend? Ist G(3,5) bipartit?
• b)(optional) Allgemeiner: Für welche natürlichen Zahlen p und q ist G(p,q) zusammenhängend, und für welche p und q ist G(p,q) bipartit?