Liczba chromatyczna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
darex99
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 15 kwie 2018, o 20:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Liczba chromatyczna

Post autor: darex99 »

Proszę o pomoc w poniższych zadaniach.
1. \(\displaystyle{ G}\) jest grafem regularnym stopnia \(\displaystyle{ r}\), rzędu \(\displaystyle{ n}\). Wykaż że \(\displaystyle{ \chi(G) \ge \frac{n}{n-r}}\)
2. Udowodnij, że w dowolnym grafie \(\displaystyle{ G}\) jest co najmniej \(\displaystyle{ \frac{\chi(G)(\chi(G)-1)}{2}}\) krawędzi.
Ostatnio zmieniony 15 kwie 2018, o 22:00 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: Liczba chromatyczna

Post autor: Mruczek »

1:    
2:    
ODPOWIEDZ