0 Daumen
1,1k Aufrufe

Aufgabe: Größe und Durchmesser

a) Sei n ≥ 6 eine natürliche Zahl, M eine n elementige Menge und G = (V, E) ein Graph mit V = (M über 2) = wobei zwei Knoten A, B Element von V genau dann adjazent sind, wenn (A ∩ B ≠∅) gilt. Bestimmen Sie die Größe ]E] von G. Natürlich muss die Antwort auch kurz begründet werden.

b) Beantworten Sie die gleiche Frage noch einmal für den Graphen G’ = (V', E’ mit V’ = (M über 3) und der gleichen Regel für die Adjazenz.

c) Beantworten Sie die gleiche Frage noch einmal für den Graphen G'' = (V”,E”) mit V'” = (M über 3) und der Regel, dass zwei Knoten A, B element von V'' genau dann adjazent sind, wenn [A ∩ Bl = 2 ist.


Nachtrag: (M über 2) ist der Binomialkoeffizient \( \left( \begin{array} { c } { M } \\ { 2 } \end{array} \right) \)

Dass M nicht angegeben ist, glaube ich, spielt keine Rolle.Jedenfalls im Blatt ist es nicht angegeben.

Avatar von

1 Antwort

0 Daumen

a) Der Graph G = (V, E) hat V = (M über 2) = die Menge aller Teilmengen von M mit genau 2 Elementen. Da jeder Knoten in V aus genau 2 Elementen von M besteht, und jeder Knoten A, B in V adjazent ist, wenn (A ∩ B ≠∅) gilt, bedeutet dies, dass jeder Knoten in V mit jedem anderen Knoten in V verbunden ist, der mindestens ein gemeinsames Element enthält. Daher hat jeder Knoten in V mindestens n-1 Kanten (da jeder Knoten mit jedem anderen Knoten verbunden ist, außer sich selbst). Da die Größe von V |V| = n über 2 = (n*(n-1))/2 ist, hat die Größe von E |E| = (n*(n-1))/2 * (n-1) = (n^2-n)/2 Kanten.

b) Der Graph G' = (V', E') hat V' = (M über 3) = die Menge aller Teilmengen von M mit genau 3 Elementen. Da jeder Knoten in V' aus genau 3 Elementen von M besteht und jeder Knoten A, B in V' adjazent ist, wenn (A ∩ B ≠∅) gilt, bedeutet dies, dass jeder Knoten in V' mit jedem anderen Knoten in V' verbunden ist, der mindestens ein gemeinsames Element enthält. Daher hat jeder Knoten in V' mindestens n-2 Kanten (da jeder Knoten mit jedem anderen Knoten verbunden ist, außer sich selbst und einem anderen Knoten). Da die Größe von V' |V'| = n über 3 = (n*(n-1)(n-2))/6 ist, hat die Größe von E' |E'| = (n(n-1)*(n-2))/6 * (n-2) = (n^3-3n^2+3n)/6 Kanten.

c) Der Graph G'' = (V", E") hat V" = (M über 3) = die Menge aller Teilmengen von M mit genau 3 Elementen. Da jeder Knoten in V" aus genau 3 Elementen von M besteht und jeder Knoten A, B in V" adjazent ist, wenn [A ∩ B] = 2 ist, bedeutet dies, dass jeder Knoten in V" mit jedem anderen Knoten in V" verbunden ist, der genau 2 gemeinsame Elemente enthält. Da jeder Knoten in V" 3 Elemente enthält, bedeutet dies, dass jeder Knoten in V" mit genau 3 anderen Knoten in V" verbunden ist, die genau 2 gemeinsame Elemente haben. Da die Größe von V" |V"| = n über 3 = (n*(n-1)(n-2))/6 ist, hat die Größe von E" |E"| = (n(n-1)*(n-2))/6 * 3 = (n^3-n^2)/2 Kanten.

Es ist zu beachten, dass die Größe von V und V' gleich sind, da die Menge M die gleiche Anzahl an Elementen hat. Allerdings, die Größe von E und E' unterscheidet sich, da die Anzahl der Kanten zwischen den Knoten basierend auf der Regel der Adjazenz variiert.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community