Liczba chromatyczna a ilość krawędzi w grafie.
-
- Użytkownik
- Posty: 29
- Rejestracja: 19 lis 2017, o 17:30
- Płeć: Mężczyzna
- Lokalizacja: A kto to wie
- Podziękował: 11 razy
Liczba chromatyczna a ilość krawędzi w grafie.
Wykaż, że jeśli w algorytmie sekwencyjnym zostało użytych \(\displaystyle{ k}\) kolorów do pomalowania grafu, to ten graf ma przynajmniej \(\displaystyle{ \frac{ k(k-1) }{2}}\) krawędzi.
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Re: Liczba chromatyczna a ilość krawędzi w grafie.
Zauważ, że dla każdej pary użytych kolorów \(\displaystyle{ c_i}\), \(\displaystyle{ c_j}\) istnieje krawędź łącząca wierzchołki o tych kolorach. W związku z tym krawędzi jest przynajmniej \(\displaystyle{ \binom{k}{2} = \frac{ k(k-1) }{2}}\).