Ungleichung, chromatische Zahl < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:28 Do 05.02.2009 | | Autor: | MacMath |
| Aufgabe | | [mm] m(G)\ge \frac{1}{2}\chi(G)(\chi(G)-1) [/mm] |
Obige Ungleichung ist zu zeigen, leider weiß ich nicht wie.
[mm] \chi(G) [/mm] ist hier die chromatische Zahl eines Graphen G
|
|
| |
|
Hallo MacMath,
die Formel [mm] \bruch{n(n-1)}{2}=\vektor{n\\2} [/mm] gibt in der Stochastik ja z.B. die Zahl möglicher Paarungen aus n Elementen an.
Hier angewandt: der kleinste Graph, der die chromatische Zahl [mm] \chi(G) [/mm] hat, hat genau [mm] \chi(G) [/mm] Knoten, von denen jeder mit jedem anderen durch eine Kante verbunden ist. Die Zahl der Kanten ist dann ...
Grüße,
reverend
|
|
|
|
