 Hamming-Abstand und Graph |
anonym__
unregistriert
 |
|
| 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.
|
|
08.04.2017 19:40 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
09.04.2017 08:13 |
|
|
skubidoo09
Grünschnabel
Dabei seit: 08.04.2017
Beiträge: 8
|
|
sehr cool. Die gesamte Aufgabe
|
|
|
09.04.2017 13:50 |
|
|
anonym__
unregistriert
|
|
Vielen Dank für die Antwort!
Die chromatische Zahl müsste dann doch 2 sein oder nicht?
|
|
|
10.04.2017 14:11 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
10.04.2017 14:18 |
|
|
anonym__
unregistriert
|
|
Wenn ich es richtig verstanden habe, dann müsste die Cliquenzahl doch 4 sein?
|
|
|
10.04.2017 14:23 |
|
|
|
