Beweis Graphen

Neue Frage »

9halbe Auf diesen Beitrag antworten »
Beweis Graphen
Meine Frage:
Beweis:
Jeder Baum T(V,E) mit |V|=n Knoten und |E|=m=n-1 Kanten nicht mehr als n maximale Cliquen enthält.

Meine Ideen:
Ich verstehe gar nicht, wie man Cliquen in Bäumen haben kann. Das sind noch Kreise?! In Bäumen gibt es doch keine Kreise, oder?
IfindU Auf diesen Beitrag antworten »
RE: Beweis Graphen
Absolut nicht mein Fachgebiet: Aber deine Argumentation sagt sofort aus, dass maximale Cliquen auch höchstens 2 Knoten bestehen. Wenn der Baum zusammenhängend ist (nach Definition laut Wikipedia), dann ist jede maximale Clique 2-elementig -- mit Ausnahme des Baumes mit nur einem Knoten. Man muss also begründen warum es nur benachbarte Knotenpaar gibt.

Edit: Etwas schaerfer und einleuchtender waere die Anzahl Cliquen.
9halbe Auf diesen Beitrag antworten »

Hallo und danke für deine Antwort!

Gut, also auf die Idee bin ich gar nicht gekommen, dass Bäumen dann 2-elementige Cliquen haben.
Aber du hast Recht, in welchem Fall hat man den n Cliquen? Es ist doch immer genau n-1 oder? Ich muss ja für die 2-elementigen Cliquen die Kanten zählen. Und wenn jeder Knoten maximal einen Nachfolgeknoten hat, dann sind es n-1 Kanten...
IfindU Auf diesen Beitrag antworten »

Richtig. Aber was wenn der Baum nur einen Knoten und keine Kante besitzt Augenzwinkern
9halbe Auf diesen Beitrag antworten »

ja dann habe ich gar keine Clique bzw. n-1=0 maximale Cliquen.
Also auch nicht n maximale..
IfindU Auf diesen Beitrag antworten »

Warum sollte der Knoten denn keine Clique sein?
 
 
9halbe Auf diesen Beitrag antworten »

Mmh achso, also hat der Baum mit 1 Knoten und der Baum mit 2 Knoten beide jeweils 1 maximale Clique?
IfindU Auf diesen Beitrag antworten »

Genau. Der Baum mit 2 Knoten hat insgesamt 3 Cliquen, aber nur eine maximale. Der Baum mit einem knoten hat nur eine Clique, aber diese ist damit sofort maximal.
9halbe Auf diesen Beitrag antworten »

Okay, mal angenommen n>1:
Jeder Baum mit n Knoten hat immer n Cliquen, es gibt aber immer nur eine maximale, die ist n-1 groß.

Aber wie beweise ich das jetzt mathematisch korrekt?
IfindU Auf diesen Beitrag antworten »

Nein. Es gibt extrem viele Cliquen, etwa n(n-1). Aber es gibt höchstens n maximale Cliquen, welche jeweils aus 2 Knoten bestehen. Und du hast doch schon begründet warum es dann m viele gibt.
9halbe Auf diesen Beitrag antworten »

Wie kommst du auf n(n-1)? Lehrer
IfindU Auf diesen Beitrag antworten »

Das kommt davon wenn man versucht müde zu zählen. Natürlich nur 2n - 1. Freude
9halbe Auf diesen Beitrag antworten »

Okay, mal an einem Beispiel von n=3 Knoten.
Es müsste ja laut deiner Aussage 2n-1 Cliquen geben, also 5.
Es gibt 3 maximale Cliquen, nämlich die, die das "Dreieck" bilden. Wo sind die anderen beiden Cliquen?
IfindU Auf diesen Beitrag antworten »

Es gibt nur 2 maximale Cliquen, jeweils bestehend aus dem "mittleren" Knoten und einem anderen. Die 3 anderen sind nicht maximal und bestehen aus nur einem Knoten.
9halbe Auf diesen Beitrag antworten »

Ach stimmt, hatte vergessen, dass es sich ja um Bäume handelt..

Mmh aber das kann ich doch so nicht einfach aufschreiben oder? Das muss doch auch irgendwie "mathematisch" gehen?
IfindU Auf diesen Beitrag antworten »

Wenn du mit "mathematisch" Formeln meinst, geht das natürlich. Aber dafür musst du erst einmal Formalisieren was ein Baum ist, was eine Clique ist, usw. Dann bist du Seitenweise mit Formeln beschäftigt, und kannst jede Folgerung mit einem Axiom begründen.

Ansonsten ist das meines ersten Posts in meinen Augen bereits mathematisch.
9halbe Auf diesen Beitrag antworten »
RE: Beweis Graphen
...
Zitat:
Original von IfindU
dass maximale Cliquen auch höchstens 2 Knoten bestehen. Wenn der Baum zusammenhängend ist (nach Definition laut Wikipedia), dann ist jede maximale Clique 2-elementig -- mit Ausnahme des Baumes mit nur einem Knoten. Man muss also begründen warum es nur benachbarte Knotenpaar gibt.


Den letzten Teil habe ich aber noch nicht gezeigt oder?
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
Es ist doch immer genau n-1 oder? Ich muss ja für die 2-elementigen Cliquen die Kanten zählen. Und wenn jeder Knoten maximal einen Nachfolgeknoten hat, dann sind es n-1 Kanten...


Ich fand das eine schöne Begründung.
9halbe Auf diesen Beitrag antworten »

Okay Freude

Und warum ist für diese Annahme mit den n maximalen Cliquen die Chordalität wichtig?
IfindU Auf diesen Beitrag antworten »

Du fragst warum wir Bäume betrachtet haben?
9halbe Auf diesen Beitrag antworten »

nein, ich frage warum die Chordalität wichtig ist.
IfindU Auf diesen Beitrag antworten »

Hier haben wir nur Bäume betrachtet. Wenn Google mich nicht belügt, sind chordale Graphen, diejenigen ohne "sehnfreie" Kreise. Da wir keine Kreise besitzen, insbesondere keine sehnfreien, sind Bäume chordal. D.h. wir haben die deutlich stärkere Eigenschaft von Kreisfreiheit benutzt um zu argumentieren, warum maximale Cliquen immer aus höchstens 2 Knoten bestehen.

Ich verstehe nicht ganz warum du jetzt nach der allgemeineren Bedingung fragst, wenn wir nicht in dem allgemeinen Setting gearbeitet haben.
9halbe Auf diesen Beitrag antworten »

Okay sorry, ich meinte tatsächlich, warum diese Annahme mit den n maximalen Cliquen bei chordalen GRAPHEN gilt.
IfindU Auf diesen Beitrag antworten »

Direkt unter der Definition die ich gefunden hab, stand der Satz: Jeder chordale Graph ist die Verklebung von vollständigen Graphen. Wenn das bekannt ist, kann man benutzen, dass jede maximale Clique mindestens einen der vollständigen Graphen komplett beinhalten muss.

Edit: Das ist Stuss...Dafür muss ich etwas länger nachdenken.

Edit 2: Kann es sein, dass man einen Baum erhält, wenn man alle vollständigen Graphen davon zu einem Knoten kontrahiert?
9halbe Auf diesen Beitrag antworten »

Das verstehe ich jetzt nicht genau. Warum gilt die Aussage denn nicht für Graphen, die nicht chordal sind?
IfindU Auf diesen Beitrag antworten »

Wikipedia sagt folgendes:
Worst case hat ein Graph mit Knoten bis zu maximale Cliquen.

Interessant sind also vermutlich Graphen mit mindestens 6 Knoten -- kannst ja mal basteln Big Laugh
9halbe Auf diesen Beitrag antworten »

Kannst du mir dazu den Link mal schicken?

Okay, aber wieso ist das denn so? Also was hat die Chordalität denn, dass die Anzahl der maximalen Cliquen so viel weniger wird?
IfindU Auf diesen Beitrag antworten »

Der Link ist oben unter "Wikipedia" versteckt.

Und Chordalitaet sind, soweit ich das sehe, Verklebungen von vollständigen Graphen. Fasst man diese als eine Einheit, also ein Knoten, auf, erhält man einen Baum.

Chordale Graphen sind also Mischungen aus Bäumen und vollständigen Graphen. Vollständige Graphen haben nur eine maximale Clique, und Bäume haben nur maximale Cliquen. Beides zusammen genommen sorgt dafür, dass die Mischung nur wenig maximale Cliquen haben kann.

Für tiefere Antworten müsstest du jemand finden der besseres Verständnis hat. Ich google mich von einer Antwort zur nächsten Big Laugh
9halbe Auf diesen Beitrag antworten »

Okay, dann danke für deine Hilfe. Ich habe jetzt schon deutlich mehr verstanden als vorher Tanzen Wenn ich doch noch eine Frage habe melde ich mich nochmal Wink
Neue Frage »
Antworten »



Verwandte Themen

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