Maximale Teilgraphen isomorph zu einem Stern

Neue Frage »

hyperwürfel Auf diesen Beitrag antworten »
Maximale Teilgraphen isomorph zu einem Stern
Ihr seid meine letzte Hoffnung.... komm einfach nicht drauf....

Frage: Bestimmten sie die Anzahl der Teilgraphen des Kn, die isomorph zu einem Stern sind.
Abakus Auf diesen Beitrag antworten »
RE: Maximale Teilgraphen isomorph zu einem Stern
Willkommen im Forum, hyperwürfel Wink

Verrätst du uns, was ein Kn ist und was du unter Sternen verstehst ? Hast du schon was überlegt ?

Grüße Abakus smile
 
 
hyperwürfel Auf diesen Beitrag antworten »
RE: Maximale Teilgraphen isomorph zu einem Stern
Ein Kn ist ein vollständiger Graph mit n Knoten (d.h. jeder Knoten ist adjazent zu allen anderen Knoten.) Ein Stern ist ein Graph, in dem ein Knoten adjazent zu allen anderen Knoten ist. Diese sind jedoch untereinander nicht adjazent.

weiß nicht, wo ich da ansetzen soll
Abakus Auf diesen Beitrag antworten »
RE: Maximale Teilgraphen isomorph zu einem Stern
Du könntest es für n = 2, 3, 4, ... einmal durch Probieren austesten und dann zu einer Vermutung kommen.

Ein Stern hat in jedem Fall sowas wie einen Mittelpunkt. Und durch den Mittelpunkt ist ein Stern dann auch schon festgelegt ?

Grüße Abakus smile
HarryPotter Auf diesen Beitrag antworten »

Hallo, ich hole diese Frage mal aus der Versenkung weil, mich diese Frage jetzt auch beschäftigt und noch nicht gelöst wurde.

Ich greife einfach mal den Vorschlag von Abakus auf und suche für n=2,3,4,...
Teilgraphen des welche isomorph zu einem Stern sind.

Meine Vermutung ist, es gibt immer Teilgraphen welche isomorph zu einem Stern sind.

Begründung:

In einem hat man alle möglichen Kanten vorhanden. Das heißt ich kann einen Stern daraus machen indem ich bestimmte Kanten weglasse.
Man geht wie folgt vor: Man wählt einen beliebigen Knoten und behält alle inzidenten Kanten dieses Knotens. Das heißt alle Kanten welche diesen Knoten erreichen. Alle anderen Kanten kann man löschen. Damit hat man einen Stern.
Jetzt sind also alle anderen Knoten nur mit jeweils dem Knoten verbunden.
Durch entfernen eines Knotens (und seiner Kante zu ) erhält man wieder einen Stern.
Man kann solange Knoten entfernen bis nur noch und ein anderer Knoten übrig bleibt. Das ist der letzte Stern.
Damit hat man also mögliche Teilgraphen eines welche isomorph zu einem Stern sind.

Seht ihr das auch so?
Neue Frage »
Antworten »



Verwandte Themen

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