0 Daumen
345 Aufrufe

Aufgabe:

Graphentheorie. Wie berechne ich die minimale Anzahl an Kanten bei vorgegebener Knoten Zahl.

Wenn ich 1000 Knoten habe und jeden mit mindestens 20 anderen Knoten verbinden will. Wie viele Kanten benötige ich mindestens?


Problem/Ansatz:

Hat jemand eine Idee wie man eine allgemeine Formel dazu herleitet.

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Hallo :-)

Der vollständige einfache Graph mit \(n\in \mathbb{N}_{\geq 2}\) Knoten hat genau

\(K(n):=\begin{pmatrix}n\\2\end{pmatrix}=\frac{n(n-1)}{2}\) Kanten.

Jeder Knoten hat zunächst \(n-1\) Kanten.

Nun sucht man die Mindestanzahl an benötigten Kanten, sodass jeder der \(n\) Knoten mit mindestens \(k\in \{0,1,2,...,n-2,n-1\}\) in Verbindung steht. Damit hast du folgende Anzahl

\(A(n,k):=\lceil{K(n)\cdot \frac{k}{n-1}\rceil}=\lceil{\frac{n(n-1)}{2}\cdot \frac{k}{n-1}\rceil}=\lceil{\frac{n\cdot k}{2}\rceil}\).

Hier mal ein paar kleinere Beispiele:

Bildschirmfoto von 2021-09-01 03-00-01.png

Bildschirmfoto von 2021-09-01 03-00-14.png

Avatar von 14 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community