Etykiety

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
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

Post autor: mol_ksiazkowy »

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 ?
Awatar użytkownika
kerajs
Użytkownik
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

Post autor: kerajs »

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}\) .
ODPOWIEDZ