Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweis Graphen Baum
Gehe zu Seite 1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Beweis Graphen Baum
 
Autor Nachricht
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 28 Mai 2017 - 19:42:39    Titel: Beweis Graphen Baum

Beweis:
Jeder Baum T(V,E) mit |V|=n Knoten und |E|=m=n-1 Kanten nicht mehr als n maximale Cliquen enthält.


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?
Deniz
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.07.2004
Beiträge: 3140

BeitragVerfasst am: 29 Mai 2017 - 10:56:36    Titel:

Hi,

Deine Aussage ist ein wenig schwierig zu lesen, da Du wahrscheinlich anders beginnen wolltest.
Und das Wort "Beweis:" samt Doppelpunkt ist hier noch nicht angebracht.
Was danach kommt ist ja eine Aussage, kein Beweis.

Vielleicht sollte auch sowas stehen, wie

Beweise: blabla

Aber das ist alles irgendwie nicht so toll.

Deine Behauptung lautet also:

Jeder Baum T(V,E) mit |V|=n Knoten und |E|=m=n-1 Kanten enthält nicht mehr als n maximale Cliquen.

Guck Dir mal die Definition von "Clique" an. Für 3 Knoten entspricht das der Definition des Kreises. Alle anderen Cliquen sind keine Kreise. Siehst Du das?
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 29 Mai 2017 - 19:35:32    Titel:

Okay du hast Recht, am Besten nochmal.

Meine Aufgabe ist es Folgendes zu beweisen:

Jeder Baum T(V,E) mit |V|=n Knoten und |E|=m=n-1 Kanten enthält nicht mehr als n maximale Cliquen.

Achso, also meinst du damit, dass es in Bäumen nur 2-elementige Cliquen gibt?
Ich muss also begründen, warum es nur n benachbarte Knotenpaare gibt.

Ist das richtig?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 29 Mai 2017 - 19:43:45    Titel:

So ist es. Jedenfalls ungefähr, denn "nicht mehr als" heißt "höchstens" und nicht "nur".

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 29 Mai 2017 - 20:19:31    Titel:

Gut, dann habe ich die Aufgabe jetzt verstanden.

Zu beweisen ist also, dass es höchstens n benachbarte Knotenpaare gibt.

Bei einem Baum mit n=1 Knoten gibt es eine Clique die n-1=0 groß ist und damit automatisch maximal ist.

Bei n=2 Knoten gibt es 3 Cliquen. Eine ist maximal und n-1 groß.

Wann ist eine Clique denn mal n groß?
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 29 Mai 2017 - 20:25:09    Titel:

Ne moment, wenn es nur 2-ementige Cliquen gibt, dann existiert die Clique bei 1 Knoten gar nicht oder? Und bei 2 Knoten gibt es nur eine Clique, statt 3. Shocked
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 30 Mai 2017 - 08:38:38    Titel:

Drücke dich gerne klar aus, damit man's versteht.

Was ich verstanden habe, ist: Es gibt nur zweielementige Cliquen. Dem kann ich zustimmen.

Was ich nicht verstehe ist, wieso "die Clique" bei einem Knoten nicht existieren soll. Warum der bestimmte Artikel? Welche "die Clique"?

Und ebensowenig, die letzte Behauptung. Wo gibt es drei Cliquen? Und wieso und bei welchen zwei Knoten nur zwei?

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 30 Mai 2017 - 11:49:21    Titel:

Also ich meinte Folgendes:

Bei n=3 Knoten habe ich einen Baum mit einer Wurzel und 2 Blättern. Hier habe ich 2 maximale Cliquen, nämlich die von der Wurzel zu jeweils einem Blatt führen. Gibt es hier noch weitere Cliquen?

Bei n=1 Knoten. Gibt es da eine oder mehrere Cliquen? Wenn Cliquen immer 2-elementig sind, dann braucht man mind. 2 Knoten. Dementsprechend dürfte es hier keine Cliquen geben.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 30 Mai 2017 - 11:57:48    Titel:

Sauber formulieren bitte: Cliquen sind nicht immer zweielementig, sondern mindestens zweielementig. Aber wahrscheinlich meinst du, dass alle Cliquen in einem Baum zweielementig sind.

Ansonsten alles richtig.

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 31 Mai 2017 - 18:52:05    Titel:

Kann mir nochmal jemand einen Tipp geben? Confused
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Beweis Graphen Baum
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2, 3  Weiter
Seite 1 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum