Liczba i indeks chromatyczny grafu
- Szemek
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
Liczba i indeks chromatyczny grafu
Zadanie pochodzi z mojego (zaliczonego ) egzaminu z dyskretnej.
Dla rozruszania szarych komórek
Określ liczbę chromatyczną grafu \(\displaystyle{ G}\) rzędu \(\displaystyle{ n}\), \(\displaystyle{ n\ge 3}\) otrzymanego z grafu pełnego \(\displaystyle{ K_n}\) poprzez usunięcie jednej krawędzi. Ile wynosi indeks chromatyczny grafu \(\displaystyle{ G}\).
Dla rozruszania szarych komórek
Określ liczbę chromatyczną grafu \(\displaystyle{ G}\) rzędu \(\displaystyle{ n}\), \(\displaystyle{ n\ge 3}\) otrzymanego z grafu pełnego \(\displaystyle{ K_n}\) poprzez usunięcie jednej krawędzi. Ile wynosi indeks chromatyczny grafu \(\displaystyle{ G}\).
Liczba i indeks chromatyczny grafu
W grafie pełnym \(\displaystyle{ K_{n}}\)liczba chromatyczna wynosi \(\displaystyle{ n-1}\). Usuwając dowolną krawędź dostajemy dwa wierzchołki, które nie sąsiadują ze sobą (inne wierzchołki dalej mają tych samych sąsiadów itd ) . Te dwa wierzchołki kolorujemy na ten sam kolor. Zatem liczba chromatyczna grafu \(\displaystyle{ K_{n}}\) jest równa \(\displaystyle{ n-2}\)
ZA ŁATWO mi to przyszło i szukam jakiegoś haczyka
Indeks chromatyczny grafu pełnego \(\displaystyle{ K_{n}}\) wynosi \(\displaystyle{ n-1}\) dla n parzystych i \(\displaystyle{ n}\) dla n nieparzystych. (dowód podawać? ) I usunięcie jednej krawędzi nam niczego nie zmieni...(i tego nie jestem pewny )
Sprawdź czy do tej pory jest dobrze
Bo nie wiem czy w dobrym kierunku idę
Edit
\(\displaystyle{ K_{3}}\) dla tego grafu się jednak zmieniło więc trzeba pomyślec
ZA ŁATWO mi to przyszło i szukam jakiegoś haczyka
Indeks chromatyczny grafu pełnego \(\displaystyle{ K_{n}}\) wynosi \(\displaystyle{ n-1}\) dla n parzystych i \(\displaystyle{ n}\) dla n nieparzystych. (dowód podawać? ) I usunięcie jednej krawędzi nam niczego nie zmieni...(i tego nie jestem pewny )
Sprawdź czy do tej pory jest dobrze
Bo nie wiem czy w dobrym kierunku idę
Edit
\(\displaystyle{ K_{3}}\) dla tego grafu się jednak zmieniło więc trzeba pomyślec
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Liczba i indeks chromatyczny grafu
W pierwszej części odpowiedź \(\displaystyle{ |G|-1}\). Ograniczenie z dołu otrzymujemy wskazując kolorowania, z góry zauważając, że \(\displaystyle{ K_n}\) bez krawędzi zawiera \(\displaystyle{ K_{n-1}}\).
W drugim z dołu ograniczamy przez minimalny stopień wierzchołka, a z góry przez indeks chromatyczny grafu przed operacją. Te liczby są równe, jeśli wyłączyć 3, który rozważamy oddzielnie.
W drugim z dołu ograniczamy przez minimalny stopień wierzchołka, a z góry przez indeks chromatyczny grafu przed operacją. Te liczby są równe, jeśli wyłączyć 3, który rozważamy oddzielnie.
Liczba i indeks chromatyczny grafu
Przykro mi, ale nie. Zerknij na def liczby chromatycznej.sopi pisze:hmmm, a czy w grafie pełnym\(\displaystyle{ K_{n}}\) liczba chromatyczna nie wynosi przypadkiem \(\displaystyle{ n}\) ??
Liczba i indeks chromatyczny grafu
Ups Przyznaję się zatem do błęduxiikzodz pisze:Może masz gdzieś link do definicji? Moja jest z książki Wilsona i \(\displaystyle{ \chi(K_n)=n}\).
-
- Użytkownik
- Posty: 8
- Rejestracja: 5 sty 2008, o 14:07
- Płeć: Kobieta
- Lokalizacja: PL
- Podziękował: 2 razy
Liczba i indeks chromatyczny grafu
w takiej sytuacji rozwiązanie różni się tylko zamianą n-1 na n czy cos wiecej?