Dritter Beweis: Gewichtsverteilung¶

In diesem Beweis betrachten wir eine Gewichtsverteilung auf den Knoten des Graphen. Diese notieren wir als \(w = (w_1,...,w_n)\) und es gilt \(w_i \ge 0\), sowie \(\sum^n_{i=1}w_i = 1\). Des weiteren definieren wir eine Funktion \(f(w) = \sum_{ \{v_i, v_j\} \in E} w_i w_j\), welche wir zu maximieren versuchen. Wieso wir dies für exakt diese Funktion tun wird sich im späteren Verlauf des Beweises klären.

Setzen wir nun \(v_i\) und \(v_j\) als zwei nicht benachbarte Knoten mit positiven Gewicht \(w_i, w_j\) und fassen das Gewicht ihrer adjazenten Knoten zusammen als \(s_i, s_j\) und nehmen \(s_i \ge s_j\) an.

Bewegen wir nun das Gewicht von \(v_j\) nach \(v_i\), setzen also \(w'_i := w_i + w_j\) und \(w'_j := 0\), dann ergibt sich für die neue Gewichtung \(w'\):

1. Dies gilt aufgrund des verschobenen Gewichts. Dieses wird in der Multiplikation auf seitens \(s_j\) nicht mehr betrachtet, bei \(s_i\) schon. Da \(w_j\) für \(s_j\) wegfällt wird das Gewicht hier also abgezogen und bei \(s_i\) umgekehrt draufgerechnet in der Multiplikation.
2. Dies gilt, da \(w_j\) als Ecke mit positiven Gewicht ausgewählt wurde.

Wir können diese Verschiebung nun wiederholen bis es keine nicht-adjazenten Knoten mit positiver Gewichtung mehr gibt und erhalten danach eine optimierte Verteilung, da für jede Umformung \(f(w') \ge f(w)\) gilt. Da wir das Gewicht nach bestimmten Anzahl an Verschiebungen innerhalb einer k - Clique verschieben betrachten wir nun wie wir das Gewicht für eine solche Clique optimieren können. Dies muss nicht zwangsweise die größte Clique sein, f wäre dann größer als mit einer kleineren Clique.

Bewegen wir die Gewichte innerhalb einer solchen k - Clique in der Form, dass wir uns zwei Knoten mit positiven Gewicht wählen für die \(w_i > w_j > 0\) gilt und ein \(\varepsilon\) setzen für das \(0 < \varepsilon < w_i - w_j\) gilt. Addieren wir \(\varepsilon\) auf \(w_j\) und subtrahieren es von \(w_i\). Es ergibt sich also:

1. Da in einer Clique alle Knoten miteinander verbunden sind, gleichen sich die Unterschiede für die Funktionswerte für alle Kanten aus, außer der zwischen \(v_i\) und \(v_j\). Dementsprechend muss das alte Gewicht abgezogen und das neue addiert werden.
2. Da \(0 < \varepsilon < w_1 - w_2\) gilt.

Daher optimiert diese Gewichtsverlagerung die k-Clique bis es keine ungleichen Gewichtungen mehr in ihr gibt. Dass dies irgendwann eintritt ist leicht einzusehen, denn wenn man \(\varepsilon\) setzt als

wodurch \(w_i' = w_i - \varepsilon = w_i - w_i + \frac{1}{k} = \frac{1}{k}\) gilt, also ein Knoten nach dem anderen die optimale, da gleichmäßige Verteilung einnimmt. Hierzu muss \(0 < w_i - \frac{1}{k} < w_i - w_j\), also \(w_j < \frac{1}{k} < w_i\) gelten. Wenn man \(w_i\) als maximal gewichteten Knoten wählt und \(w_j\) als minimal gewichteten, dann muss \(\frac{1}{k}\) zwischen beiden liegen muss. Obrige Ungleichung hat gezeigt, dass je näher die Werte der einzelnen Knoten aneinanderliegen desto optimierter ist die Funktion f, wodurch bei einer gleichmäßigen Verteilung das Optimum liegt. Dies liegt an der Eigenschaft der Multiplikation maximal für die Summe der Faktoren zu sein, wenn beide Faktoren gleich groß sind.

In einer k-Clique können maximal \(\frac{k (k-1)}{2}\) Kanten sein, also \(\frac{\text{Jeder Punkt} (\text{Jeder Punkt mit dem er sich verbinden kann})}{\text{Enden einer Kante}}\). Für die Gewichtung ergibt sich also:

1. Definition von f.
2. Setzung von \(w_i := \frac{1}{k}\).
3. Dies gilt, da wie oben erwähnt in einer k-Clique maximal \(\frac{k (k-1)}{2}\) Kanten sein.

Da diese Funktion maximal ist wenn k maximal ist und der höchstmögliche Wert für k genau p - 1 ist gilt weiter:

Insbesondere gilt dies dann auch für die uniforme Verteilung