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

Übungsblatt 6

Abgabe in der 7. Semesterwoche

6.1 Wir betrachten die Menge M aller endlichen 1-2 Folgen, d.h. aller Tupel (a1,a2,...,ak) mit k N0 und ai {1,2} für alle i {1,2,...,k}. Wir betrachten die durch (a1,a2,...,ak)* (b1,b2,...,bm) = (a1, a2, ... ,ak, b1, b2, ..., bm) definierte binäre Verknüpfung "*" auf M. Außerdem sei eine binäre Relation "§" auf M durch (a1,a2,...,ak)§ (b1,b2,...,bm) falls a1 + a2 + ... + ak = b1 + b2 + ... + bm definiert.

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.

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.


April 2000