Graphentheorie |
05.05.2008, 13:59 | oinki | Auf diesen Beitrag antworten » |
Graphentheorie ich weiß nicht ob das thema hier hin gehört. Ich hoffe ihr könnt mir weiterhelfen. Gegeben ist: G(V,E) mit V={1,2,...500} und {i,j} element E genau dann, wenn max (i,j)/min (i,j) --- "/" soll geteilt durch bedeuten ganzzahlig und eine Potenz von 2 ist. Nun soll ich sagen ob der Graph bipartit ist. Ich weiß, dass ein Graph nicht bipartit ist, wenn ihn ihm Kreise mit ungerader Anzahl an Kanten gibt. Und bipartit wenn der Graph in Menge A und B zerlegt werden kann. Aber das Problem ist, dass ich nicht weiß wie der Graph aussieht . Bitte um eure Hilfe mfg oinki |
||
05.05.2008, 19:22 | Tobias | Auf diesen Beitrag antworten » |
Du weißt bereits, dass ein Graph nicht bipartit sein kann, wenn es einen Kreis ungerader Länge gibt (Lemma von König). Versuch doch einfach mal einen Kreis ungerader Länge zu konstruieren. Fange z.B. mit einem Dreikreis mit den Knoten i, j und k an. Dabei kann man o.B.d.A. von i < j < k ausgehen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|