Etykiety
- mol_ksiazkowy
- Użytkownik
- Posty: 11264
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3141 razy
- Pomógł: 747 razy
Etykiety
Wierzchołki grafu nieskończonego są etykietowane liczbami naturalnymi. Istnieje krawędź między \(\displaystyle{ m}\) i \(\displaystyle{ n}\) gdy \(\displaystyle{ |m-n|}\) jest liczbą pierwszą. Jaka jest liczba chromatyczna tego grafu ?
- kerajs
- Użytkownik
- Posty: 8570
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 306 razy
- Pomógł: 3347 razy
Re: Etykiety
Ta liczba to 4.
Kolorem A maluję wierzchołki których etykiety przy dzieleniu przez 4 dają resztę 0, kolorem B wierzchołki których etykiety przy dzieleniu przez 4 dają resztę 1, kolor C dla reszty 2, a pozostałe kolorem D.
Jeśli różnicą etykiet jest liczba 2 to krawędź łączy wierzchołki o etykietach w kolorze A i C lub B i D.
Krawędzie o nieparzystej i pierwszej różnicy etykiet nie mogą łączyć etykiet w tym samym kolorze, gdyż różnica tych etykiet jest wielokrotnością 4.
Liczba chromatyczna nie może być mniejsza niż 4, gdyż w grafie istnieją kliki \(\displaystyle{ K_4}\) o etykietach \(\displaystyle{ k, k+2, k+5, k+7}\) .
Kolorem A maluję wierzchołki których etykiety przy dzieleniu przez 4 dają resztę 0, kolorem B wierzchołki których etykiety przy dzieleniu przez 4 dają resztę 1, kolor C dla reszty 2, a pozostałe kolorem D.
Jeśli różnicą etykiet jest liczba 2 to krawędź łączy wierzchołki o etykietach w kolorze A i C lub B i D.
Krawędzie o nieparzystej i pierwszej różnicy etykiet nie mogą łączyć etykiet w tym samym kolorze, gdyż różnica tych etykiet jest wielokrotnością 4.
Liczba chromatyczna nie może być mniejsza niż 4, gdyż w grafie istnieją kliki \(\displaystyle{ K_4}\) o etykietach \(\displaystyle{ k, k+2, k+5, k+7}\) .