---

Geschrieben von anonym__ am 08.04.2017 um 19:40:

  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.

---

Geschrieben von eulerscheZahl am 09.04.2017 um 08:13:

 

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.

---

Geschrieben von skubidoo09 am 09.04.2017 um 13:50:

 

sehr cool. Die gesamte Aufgabe

---

Geschrieben von anonym__ am 10.04.2017 um 14:11:

 

Vielen Dank für die Antwort!
Die chromatische Zahl müsste dann doch 2 sein oder nicht?

---

Geschrieben von eulerscheZahl am 10.04.2017 um 14:18:

 

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.

---

Geschrieben von anonym__ am 10.04.2017 um 14:23:

 

Wenn ich es richtig verstanden habe, dann müsste die Cliquenzahl doch 4 sein?