Hamming-Abstand und Graph |
| 08.04.2017, 19:40 | Auf diesen Beitrag antworten » |
| 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. |
|
|
|
| 09.04.2017, 08:13 | Auf diesen Beitrag antworten » |
| 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. |
| 09.04.2017, 13:50 | Auf diesen Beitrag antworten » |
| skubidoo09 | sehr cool. Die gesamte Aufgabe |
| 10.04.2017, 14:11 | Auf diesen Beitrag antworten » |
| anonym__ | Vielen Dank für die Antwort! Die chromatische Zahl müsste dann doch 2 sein oder nicht? |
| Anzeige | |
|
|
|
| 10.04.2017, 14:18 | Auf diesen Beitrag antworten » |
| 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. |
| 10.04.2017, 14:23 | Auf diesen Beitrag antworten » |
| anonym__ | Wenn ich es richtig verstanden habe, dann müsste die Cliquenzahl doch 4 sein? |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
