Beweis Graphen |
28.05.2017, 18:48 | 9halbe | Auf diesen Beitrag antworten » | ||
Beweis Graphen 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? |
||||
29.05.2017, 12:26 | 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. |
||||
29.05.2017, 20:40 | 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... |
||||
29.05.2017, 20:45 | IfindU | Auf diesen Beitrag antworten » | ||
Richtig. Aber was wenn der Baum nur einen Knoten und keine Kante besitzt |
||||
29.05.2017, 20:47 | 9halbe | Auf diesen Beitrag antworten » | ||
ja dann habe ich gar keine Clique bzw. n-1=0 maximale Cliquen. Also auch nicht n maximale.. |
||||
29.05.2017, 21:02 | IfindU | Auf diesen Beitrag antworten » | ||
Warum sollte der Knoten denn keine Clique sein? |
||||
Anzeige | ||||
|
||||
29.05.2017, 21:04 | 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? |
||||
29.05.2017, 21:10 | 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. |
||||
29.05.2017, 21:14 | 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? |
||||
29.05.2017, 21:18 | 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. |
||||
29.05.2017, 21:22 | 9halbe | Auf diesen Beitrag antworten » | ||
Wie kommst du auf n(n-1)? |
||||
30.05.2017, 05:05 | IfindU | Auf diesen Beitrag antworten » | ||
Das kommt davon wenn man versucht müde zu zählen. Natürlich nur 2n - 1. |
||||
30.05.2017, 08:37 | 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? |
||||
30.05.2017, 09:32 | 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. |
||||
30.05.2017, 12:45 | 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? |
||||
30.05.2017, 12:51 | 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. |
||||
30.05.2017, 13:40 | 9halbe | Auf diesen Beitrag antworten » | ||
RE: Beweis Graphen ...
Den letzten Teil habe ich aber noch nicht gezeigt oder? |
||||
30.05.2017, 13:44 | IfindU | Auf diesen Beitrag antworten » | ||
Ich fand das eine schöne Begründung. |
||||
30.05.2017, 13:46 | 9halbe | Auf diesen Beitrag antworten » | ||
Okay Und warum ist für diese Annahme mit den n maximalen Cliquen die Chordalität wichtig? |
||||
30.05.2017, 13:49 | IfindU | Auf diesen Beitrag antworten » | ||
Du fragst warum wir Bäume betrachtet haben? |
||||
30.05.2017, 13:55 | 9halbe | Auf diesen Beitrag antworten » | ||
nein, ich frage warum die Chordalität wichtig ist. |
||||
30.05.2017, 14:02 | 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. |
||||
30.05.2017, 14:04 | 9halbe | Auf diesen Beitrag antworten » | ||
Okay sorry, ich meinte tatsächlich, warum diese Annahme mit den n maximalen Cliquen bei chordalen GRAPHEN gilt. |
||||
30.05.2017, 14:08 | 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? |
||||
30.05.2017, 14:14 | 9halbe | Auf diesen Beitrag antworten » | ||
Das verstehe ich jetzt nicht genau. Warum gilt die Aussage denn nicht für Graphen, die nicht chordal sind? |
||||
30.05.2017, 14:30 | 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 |
||||
30.05.2017, 14:41 | 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? |
||||
30.05.2017, 14:51 | 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 |
||||
30.05.2017, 14:53 | 9halbe | Auf diesen Beitrag antworten » | ||
Okay, dann danke für deine Hilfe. Ich habe jetzt schon deutlich mehr verstanden als vorher Wenn ich doch noch eine Frage habe melde ich mich nochmal |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|