Die letzten 6 Beiträge |
anonym__ |
Wenn ich es richtig verstanden habe, dann müsste die Cliquenzahl doch 4 sein? |
eulerscheZahl |
Ja genau.
Alle Wege zwischen den Knoten u und v in V haben entweder die gleiche Länge oder unterscheiden sich um ein Vielfaches von 2. Der Graph ist also bipartit bzw. zweifärbbar. |
anonym__ |
Vielen Dank für die Antwort!
Die chromatische Zahl müsste dann doch 2 sein oder nicht? |
skubidoo09 |
sehr cool. Die gesamte Aufgabe |
eulerscheZahl |
Du hast du Knoten 0000, 0001, ..., 1111.
Hammingabstand 1 bedeutet, dass genau eine Ziffer anders ist.
Hier ein Bild für V = {0,1}^3.
die c) mache ich dir: jeder Knoten hat 4 Nachbarn, also eine gerade Anzahl. Da der Graph zusammenhängend ist und alle Knoten geraden Grad haben, gibt es auch einen Eulerkreis. |
anonym__ |
Hamming-Abstand und Graph
Hallo zusammen,
Ich habe ein Problem mit dieser Aufgabe. Ich weiß überhaupt nicht wie ein Hamming-Abstand einen Graphen angeben kann. Also mein Problem liegt darin, dass ich nicht weiß wie ich mit den Hamming-Abstand arbeiten kann damit ein Graph entsteht.
Der Graph G = (V,E) sei definiert durch V={0,1}^4 und E={(v,w)| d(v,w)=1}, dabei ist d der Hamming-Abstand.
a) Geben Sie die chromatische Zahl von G an.
b) Geben Sie die Cliquenzahl von G an.
c) Hat G einen Eulerkreis?
Begründen Sie ihre Antworten jeweils. |
|
|