Farbe (Graphentheorie)
aus Wikipedia, der freien Enzyklopädie
Als Farbe bezeichnet man in der Graphentheorie eine natürliche Zahl, die einem Knoten (Farbe eines Knotens) oder einer Kante (Farbe einer Kante) eines Graphen zugeordnet wird.
Es kommt dabei in der Regel nicht auf den Wert der Zahl, sondern nur die Unterscheidbarkeit der Zahlen zueinander an. Man teilt die Menge der Knoten bzw. Kanten über ihre Farbe also in verschiedene Klassen ein.
Während der Begriff Farbe ganz allgemein nur eine solche Zuordnung darstellt, ist eine Färbung eine Zuordnung speziellerer Natur. Es ist daher streng darauf zu achten, ob von Farben ganz allgemein oder von Färbungen im Speziellen gesprochen wird.
[Bearbeiten] Farbe einer Kante
Als Farbe einer Kante bezeichnet man in der Graphentheorie eine der entsprechenden Kante zugeordnete natürliche Zahl.
Es kommt dabei in der Regel nicht auf den Wert der Zahl, sondern nur die Unterscheidbarkeit der Zahlen zueinander an. Man teilt die Menge der Kanten über ihre Farbe also in verschiedene Klassen ein.
[Bearbeiten] Farbe eines Knotens
Als Farbe eines Knotens bezeichnet man in der Graphentheorie eine dem entsprechenden Knoten zugeordnete natürliche Zahl.
Es kommt dabei in der Regel nicht auf den Wert der Zahl, sondern nur die Unterscheidbarkeit der Zahlen zueinander an. Man teilt die Menge der Knoten über ihre Farbe also in verschiedene Klassen ein.
