Regel des zweifachen Abzählens

21.04.2010, 15:25	Hellboy256	Auf diesen Beitrag antworten »
Regel des zweifachen Abzählens An einer Universität muss jeder Student einer bestimmten Studien- richtung genau 3 der 7 angebotenen Lehrveranstaltungen besuchen. Die Lektoren geben die jeweiligen Höhrerzahlen als 51, 30, 30, 20, 23, 12 und 17 an. Welcher Schluss kann daraus gezogen werden ? Diese Aufgabe sollte man mithilfe der "Regel des zweifachen Abzählens" lösen. Die Regel lautet folgendermaßen: Ein ungerichteter Graph heißt bipartit, wenn es eine Partition der Eckenmenge in zwei Blöcke E1 und E2 gibk, sodass jede Kante eine Endecke in E1 und eine Endecke in E2 hat. Hätte vlt jemand ne Idee wie das gehen soll?
21.04.2010, 15:29	kiste	Auf diesen Beitrag antworten »
Das ist sicherlich nicht die Regel, das ist nur die Definition von bipartit. Aber du kannst das Problem ja einmal in eine Graphentheoretische Fassung bringen: Du hast also einen bipartiten Graphen, wobei der eine Block die Studenten und der andere die Veranstaltungen sind. Eine Kante ziehen wir wenn ein Student die Veranstaltung besucht. Was kannst du jetzt über die Grade der Knoten der jeweiligen Blöcke aussagen?
21.04.2010, 15:47	Hellboy256	Auf diesen Beitrag antworten »
Gut dann hätte ich also auf der einen Seite (E1) die Studenten also nur ein Knoten und auf der anderen die 7 Lehrveranstaltungen (7 Knoten) aber was kann man jetzt darüber aussagen?
21.04.2010, 15:51	kiste	Auf diesen Beitrag antworten »
Na nicht so knauserig sein mit den Knoten, jeder Student soll seinen eigenen Knoten bekommen. Und dann untersuche wie gesagt einmal die Grade der Knoten
21.04.2010, 15:57	Hellboy256	Auf diesen Beitrag antworten »
Ok dann wären auf der linken Seite (E1) 61 Knoten und davon würden dann 51 zum ersten Knoten auf der rechten Seite, 30 zum zweiten auf der rechten Seite, 30 zum dritten auf der rechten Seite, ...
21.04.2010, 16:06	kiste	Auf diesen Beitrag antworten »
Jetzt hast du wieder zu viel Knoten spendiert! Die Anzahl der Studenten(die hier in der Aufgabe ja zu bestimmen ist) ist niedriger. Sage einfach einmal du hast n Studenten. Was ist die Summe der Grade auf der rechte und auf der linken Seite?
Anzeige

21.04.2010, 16:12	Hellboy256	Auf diesen Beitrag antworten »
Die Summe der rechten Seite wäre doch die gesammte Anzahl aller Lehrveranstaltungen, also 51+30+30+20+23+12+17 = 183 Und die Summe der linken Seite ist ja, da jeder Student drei Lehrveranstaltungen Besuchen muss 183/3 = 61 ?
21.04.2010, 16:15	kiste	Auf diesen Beitrag antworten »
Naja das ist nicht die Summe auf der linken Seite, die ist 3n. Aber n ergibt sich dann zu 61...
21.04.2010, 16:21	Hellboy256	Auf diesen Beitrag antworten »
Wenn n die Anzahl der Studenten ist, wäre dann nicht auf der rechten Seite die Summe der Grade 3n und auf der Linken (Summe der Grade)/3 ?
21.04.2010, 16:24	kiste	Auf diesen Beitrag antworten »
Auf der rechten Seite kenne wir doch die Grade... Das sind gerade die Zuhörerzahlen der Veranstaltungen. Auf der linken Seite sind die Studenten, wir wissen dass hier jeder Knoten Grad 3 hat, da jeder Student 3 Veranstaltungen hört! Summation der Grade auf der rechten Seite: 183 .... auf der linken Seite: 3n Also 3n = 183

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »