Sei n ≥ 6 eine natürliche Zahl, M eine n elementige Menge ... Bestimmen Sie die Größe ]E] von G.

Question

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.

Answer 1

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.