Fakultät

09.04.2011, 19:56

MatheKind

Fakultät

Hallo,
hier eine Aufgabe, die seit drei Wochen kein Erstsemester im Informatikstudiengang gelöst hat.
Ich habe mich mal rangewagt (ich hatte es zuvor erst gar nicht probiert. Big Laugh

):

Es sei $\begin{eqnarray*} M := \left\{1, 2, ..., n \right\} \end{eqnarray*}$ . Sie können ohne Beweis den folgenden Sachverhalt als bekannt voraussetzen:

Die Anzahl der k-elementigen Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ beträgt $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ . (*)

Auf der Menge $\begin{eqnarray*} $\mathcal{P}(M, k) \end{eqnarray*}$ der k-elementigen Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ werde eine Relation $\begin{eqnarray*} R \end{eqnarray*}$ erklärt vermöge

$\begin{eqnarray*} A R B :\Leftrightarrow A \cap B = \left\{ \right\} \end{eqnarray*}$ für alle $\begin{eqnarray*} A, B \in \mathcal{P}(M, k) \end{eqnarray*}$ .

Der Graph $\begin{eqnarray*} G(n, k) \end{eqnarray*}$ ist derjenige Graph, der die Relation $\begin{eqnarray*} R \end{eqnarray*}$ darstellt: Seine Knoten sind die k-elementigen Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ ; der Einfacheit halber bezeichnen wir die Knoten mit $\begin{eqnarray*} A, B, ... \end{eqnarray*}$ Der Knoten $\begin{eqnarray*} A \end{eqnarray*}$ ist genau dann mit einem Knoten $\begin{eqnarray*} B \end{eqnarray*}$ durch ein Pfeil verbunden, wenn $\begin{eqnarray*} ARB \end{eqnarray*}$ gilt. Da $\begin{eqnarray*} R \end{eqnarray*}$ offensichtlich symmetrisch ist, genügt es zwei derartige Knoten durch eine Kante zu verbinden.

a) Zeichnen Sie die Graphen $\begin{eqnarray*} G(5, 1) \end{eqnarray*}$ und $\begin{eqnarray*} G(5,2) \end{eqnarray*}$ .

Im Folgenden sind $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ beliebig gewählt.

b) Mit wie vielen Knoten ist ein Knoten des Graphen $\begin{eqnarray*} G(n, k) \end{eqnarray*}$ durch eine Kante verbunden?
Machen Sie zweckmäßigerweise Gebrauch von (*).

c) Folgern Sie hieraus, wie viele Kanten der Graph $\begin{eqnarray*} G(n, k) \end{eqnarray*}$ besitzt.
Überprüfen Sie ihr Resultat anhand der Graphen $\begin{eqnarray*} G(5, 2) \end{eqnarray*}$ .

Zu meiner Lösung:

Die Teilaufgabe a werde ich hier nicht zeigen können, deswegen folgt b und c:

b)
Ich habe hier nicht von der Fakultätsformel Gebrauch gemacht, deswegen frage ich mich, ob das stimmt...
Mein Ansatz: Die Teilmengen $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ sind disjunkt. Dies kann man z. B. mit zwei Mengen mit jeweils geraden und ungeraden Zahlen beschreiben.
Ein Knoten ist genau dann mit einem anderen Knoten verbunden, wenn $\begin{eqnarray*} ARB \end{eqnarray*}$ gilt. Die ungerade Zahl $\begin{eqnarray*} 1 \end{eqnarray*}$ ist z. B. mit allen geraden Zahlen verbunden. - Es gibt $\begin{eqnarray*} \frac{n}{2} \end{eqnarray*}$ ganzahlige Elemente, also ist die Zahl $\begin{eqnarray*} 1 \end{eqnarray*}$ mit $\begin{eqnarray*} n - \frac{n}{2} \end{eqnarray*}$ Elemente durch einer Kante verbunden.
Allgemein kann man dies mit $\begin{eqnarray*} n - \frac{n}{k} \end{eqnarray*}$ ausdrücken.

c)
Auf b) aufbauend kann man sagen, dass es $\begin{eqnarray*} \frac{n}{k} * (n - \frac{n}{k}) \end{eqnarray*}$ Kanten gibt.

Jetzt habe ich keinerlei Gebrauch der Fakultätsformel gemacht. Habe ich die Aufgabe überhaupt korrekt verstanden?! verwirrt

Liebe Grüße
MatheKind

09.04.2011, 20:20

Mystic

Auf diesen Beitrag antworten »

RE: Fakultät

Zitat:

Original von MatheKind
Habe ich die Aufgabe überhaupt korrekt verstanden?! verwirrt

Die Kurzform der Antwort lautet: Nein, überhaupt nicht... unglücklich

Ich würde an deiner Stelle doch einmal mit a) anfangen, um ein Gefühl für die Aufgaben b) und c) zu bekommen und einfach durch Abzählen mal die Knotengrade in G(5,1) und G(5,2) bestimmen... Wie groß sind diese und wie kann man sie in diesem Spezialfall berechnen?

Edit: Wie haushoch daneben deine Formeln sind, kannst du übrigens schon daraus ersehen, dass sie i.allg. nicht einmal ganzzahlig sind!... geschockt

Neue Frage »

Antworten »

Fakultät

Verwandte Themen