Zusammenhangskomponente

Neue Frage »

madi83 Auf diesen Beitrag antworten »
Zusammenhangskomponente
Hi,
ich soll eine aufgabe mit ja oder nein beantworten, und zwar ist die frage ob es einen ungerichteten Graphen (ohne Doppelkanten) mit 12 Knoten, 66 Kanten und 3 Zusammenhangskomponenten gibt.

Was ist denn eine Zusammenhangskomponente?
Wenn ich 4 Graphen habe und die miteinander verbunden sind, gibt es dann min. 3 solcher Komponenten? sind das also nur kanten??
Divergenz Auf diesen Beitrag antworten »
RE: Zusammenhangskomponente
Hallo,

also eine Zusamenhangskomponente in einem Graph ist eben ein zusammenhängender Teil des Graphen, das heißt alle Knoten, die direkt oder indirekt miteinander verbunden sind einschließlich aller Kanten, die in diesen Knoten starten oder enden.

In deinem Fall kann man sich überlegen, dass es diesen Graphen nicht geben kann. Nimmt man nämlich 12 Knoten und will daraus einen ungerichten Graphen ohne Mehrfachkanten mit 66 Kanten bauen, so gibt es nur den vollständigen Graphen (jeder Knoten ist mit jedem anderen durch eine Kante verbunden). Dieser Graph besteht dann aber nur aus einer Zusammenhangskomponente, da man ja von jedem Knoten aus (sogar direkt) zu jedem anderen gelangt.
Madi83 Auf diesen Beitrag antworten »

hmmm, also gibts immer nur graphen mit einer zusammenhangskomponente? nee kann ja nich sein..ich versteh den zusammenhang irgendwie nich so ganz..gibts nich irgendwo ein beispiel wo das veranschaulicht ist?
Abakus Auf diesen Beitrag antworten »

Divergenz hat es schon erklärt, überlege einfach mal wieviele Kanten ein zusammenhängender Graph mit 12 Knoten ohne parallele Kanten höchstens haben kann.

Dann kannst du überlegen, ob noch Platz für isolierte Knoten ist.

Grüße Abakus smile

**** verschoben nach Sonstiges (Graphentheorie) ****
madi83 Auf diesen Beitrag antworten »

na bei 12 knoten gibts 11 kanten. Was du allerdings mit isolierte knoten meinst weiss ich wieder nich.
Divergenz Auf diesen Beitrag antworten »

11 Kanten pro Knoten! Also insgesamt Kanten, da ja beim Addieren jede Kante doppelt gezählt wird (jeweils über beide angrenzenden Knoten). Das macht dann insgesamt 66.
 
 
madi83 Auf diesen Beitrag antworten »

achso, und das sind schon die 66 Kanten, das heisst es kann keine weiteren zusammenhangskomponenten geben, da sonst mehr kanten entstehen würden?
Divergenz Auf diesen Beitrag antworten »

naja fast, es kann keine weitere Zusammenhangskomponente geben, da man dafür weiter Knoten bräuchte! Diese könnten dann z.B. isoliert sein, das heißt keine Nachbarn haben.
Neue Frage »
Antworten »



Verwandte Themen

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