Graphentheorie

Neue Frage »

oinki Auf diesen Beitrag antworten »
Graphentheorie
hi,

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 unglücklich . Bitte um eure Hilfe

mfg oinki
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.
Neue Frage »
Antworten »



Verwandte Themen

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