Wie viele Dreiecke hat ein Graph mit gegebener Linkanzahl mindestens (höchstens)?

Neue Frage »

net Auf diesen Beitrag antworten »
Wie viele Dreiecke hat ein Graph mit gegebener Linkanzahl mindestens (höchstens)?
Meine Frage:
Hallo, ich beschäftige mich gerade mit folgendem Problem:

Gegeben sei ein Netzwerk mit N Knoten und E ungerichteten Kanten.

Ich möchte nun zu gegebener Netzwerkgröße N und einer gegebenen Linkanzahl E, die minimale (maximale) Dreiecksanzahl () des Netzwerks bestimmen. Ein Dreieck ijk sei dadurch definiert, dass .

In dem Graphen gibt es entsprechend Knotenpaare und Tripel.

Meine Ideen:
Für ist natürlich auch . Ebenso folgt aus , dass .

Ausgehend von kann man zunächst sukzessive Links hinzufügen, ohne Dreiecke zu erzeugen. Auf jeden Fall ist natürlich .

Für N=3 ist dann und wir sind fertig.

Für N>3 ist .

Für N=4 haben wir dann .

Für N>4 ist, usw...

Ich weiss nicht, ob sich mein Problem überhaupt vollständig analytisch lösen lässt. Ein erster Schritt wäre es aber schonmal, zu gegebener Knotenzahl N die Linkzahl E zu finden, für die ungleich Null wird.

Ich bin für alle Vorschläge sehr dankbar!
net Auf diesen Beitrag antworten »

Okay, also ich denke für hab ich inzwischen eine Abschätzung gefunden. Das geht meiner Einschätzung nach leichter, als für . Am meisten Dreiecke lassen sich bei gegebenem erzeugen, wenn man die Links ausschließlich auf Cluster von Knoten verteilt. D.h. man versucht einen Teil der Knoten vollständig miteinander zu verbinden, während andere komplett ohne Link bleiben. So werden die Kanten in maximal vielen verschiedenen Dreiecken gleichzeitig verwendet.

Nehmen wir an, von den Knoten seien durch die gegebenen Links vollstaendig miteinander verbunden. Dann gilt:
.

Hat jemand eine Idee, wie man fuer vorgehen koennte?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von net
Nehmen wir an, von den Knoten seien durch die gegebenen Links vollstaendig miteinander verbunden. Dann gilt:
.

Wenn du schon soweit bist, solltest du aber etwas genauer vorgehen:

Es ist , und nach der vollständigen Verbindung dieser Knoten untereinander bleiben genau Kanten "übrig". Konstruktionsbedingt ist , und mit diesen Kanten verbinden wir der bisherigen Knoten mit einem neuen, -ten Knoten, was weitere Dreiecke erbringt.

Die exakte Zahl ist also .
net Auf diesen Beitrag antworten »

Super, vielen Dank fuer den Hinweis!

Die untere Grenze ist uebrigens bis einschliesslich gleich Null. Letztere gehoert zu einem bipartiten Graphen, in dem noch kein Dreieck existiert.
Zum uebrigen Bereich von habe ich folgendes Paper gefunden: http://www.google.com/url?sa=t&rct=j&q=o...2OhXWmg&cad=rja
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »