Einfärben eines Konfliktgraphen (Chromatische Zahl) |
| 03.06.2012, 08:52 | ChrisL1988 | Auf diesen Beitrag antworten » | ||
| Einfärben eines Konfliktgraphen (Chromatische Zahl) ich soll folgende Konfliktgraphen (Funkstandorte) einfärben, um die Anzahl der benötigten Funkfrequenzen (chromatische Zahl des Graphen) zu bestimmen. Ich bin mir sicher, dass die chromatische Zahl 3 ist, da 4 viel zu einfach wäre. Ich habe nun schon ein paar Mal an verschiedenen Stellen angefangen, jedoch bleibe ich bei 3 Farben immer "stecken". Gibt es hierfür Algorithmen, oder kann mir wer andere nützliche Hinweise geben? Besten Dank im Voraus und lg Christoph |
||||
| 03.06.2012, 09:03 | Huggy | Auf diesen Beitrag antworten » | ||
| RE: Einfärben eines Konfliktgraphen (Chromatische Zahl) 3 reicht defintiv nicht aus. Betrachte das Viereck GFML Da ist jeder Knoten mit jedem anderen der 4 verbunden. Also braucht man für diese 4 Knoten schon 4 Farben. |
||||
| 03.06.2012, 09:54 | ChrisL1988 | Auf diesen Beitrag antworten » | ||
RE: Einfärben eines Konfliktgraphen (Chromatische Zahl)
Du hast Recht! Ich war so darauf fixiert, dass es mit 4 Farben zu "leicht" wäre, dass ich zwanghaft nach einer Möglichkeit mit 3 Farben gesucht habe 
Für mich nehme ich mit, dass es eine gute Herangehensweise ist, zuerst "Teilstrukturen" des Graphen zu analysieren und anschließend dann versucht diese Teilstrukturen miteinander zu verbinden. Danke! Lg Christoph |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
