notwendig und hinreichend < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:04 Mi 06.12.2017 | | Autor: | asg |
| Aufgabe | | Bei einem ungerichteten Graphen $G = (V, E)$ mit $V = [mm] \{1,2,3,4,5,6,7\}$ [/mm] und $E = [mm] \{\{1,2\}, \{1,6\}, \{2,3\}, \{2,4\}, \{3, 5\}, \{3,7\}, \{4,6\}, \{5,7\}, \{6,7\}\}$ [/mm] soll angegeben werden, welche chromatische Zahl [mm] $\chi(G)$ [/mm] (Knotenfärbungszahl) ist notwendig und welche hinreichend. |
Hallo zusammen,
bei dieser Aufgabe bin ich mir nicht ganz sicher, was genau verlangt ist.
Ich weiß, dass der Graph mit mindesten 3 Farben konfliktfrei gefärbt werden kann, nämlich z.B.:
Die Knoten 1, 3, 4 (rot)
Die Knoten 2, 5, 6 (grün)
Der Knoten 7 (blau)
Also [mm] $\chi(G) [/mm] = 3 $ ist die notwendige Zahl oder [mm] $\chi(G) \le [/mm] 3 $ (??)
Eine andere Färbung wäre, jedem Knoten eine eigene Farbe zu zuweisen. Dann wäre [mm] $\chi(G) [/mm] = 7 $ und diese ist die hinreichende Zahl oder [mm] $\chi(G) \le [/mm] 7 $ ??
Dankschön vorab
Viele Grüße
Asg
Graph G und eine konfliktfreie Färbung
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Ja, 3 Farben sind notwendig, 7 hinreichend. Das heißt, 3 sind nötig, 7 reichen aus.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:56 Mi 06.12.2017 | | Autor: | asg |
Hallo,
danke für die schnelle Antwort.
Ist es nicht so:
da $3$ notwendig ist, sind somit auch $1$ und $2$ notwendig und damit die notwendige Zahl wäre [mm] $\chi(G) \le [/mm] 3$ und nicht [mm] $\chi(G) [/mm] = 3$?
Gleiches gilt für die hinreichende Zahl:
es müssten doch alle Zahlen $3 [mm] \gt \chi(G) \le [/mm] 7$ hinreichende Zahlen sein, oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:23 Do 07.12.2017 | | Autor: | a3bas |
So ist es.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Do 07.12.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
