Witam,
Nie jestem pewien rozwiązania dwóch zadań, na które natrafiłem.
1) Podaj liczbę chromatyczną i indeks chromatyczny grafu, który powstał w wyniku połączenia grafu \(\displaystyle{ K _{9}}\) z wierzchołkiem (który nie należy oczywiście do grafu początkowego) za pomocą dodatkowej krawędzi.
2) Graf początkowy jest: eulerowski, niehamiltonowski, nieplanarny. Do grafu dodano jedną dodatkową krawędź. Czy będzie eulerowski, hamiltonowski lub planarny? Możliwe odpowiedzi: tak, nie, nie wiadomo.
2 zadania z grafów.
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: 2 zadania z grafów.
1) No to liczba chromatyczna kliki wynosi tyle co liczba jej wierzchołków. Dość łatwo to zauważyć. Dołożenie jednego wierzchołka tutaj nic nie zmienia - kolorujemy go kolorem innym niż ten z którym jest połączony.
Indeks chromatyczny kliki o nieparzystej liczbie wierzchołków wynosi tyle co liczba jej wierzchołków. Dodatkową krawędź kolorujemy tym kolorem, którym nie są pokolorowane krawędzie wierzchołka tej krawędzi, który należy do kliki.
Czyli indeks i liczba chromatyczna tego grafu jest równa \(\displaystyle{ 9}\).
2) We wszystkich przypadkach zakładam, że do grafu nie dodajemy dodatkowego wierzchołka.
Jeżeli był eulerowski i dodano jedną krawędź i ta krawędź łączy dwa różne wierzchołki to oczywiście eulerowski już nie będzie, bo sumy stopni tych dwóch wierzchołków do których dodaliśmy krawędź będą nieparzyste. Jeżeli w grafie dopuszczamy pętle, to dodanie takiej pętli nic nie zmieni, także odpowiedź zależy od tego czy dopuszczamy grafy, które nie są proste: nie / nie wiadomo.
Jeżeli był hamiltonowski i dodaliśmy krawędź to dalej ten cykl Hamiltona będzie, nawet może pozostać taki sam jaki był.
No jak nie był planarny, to oczywiście dalej nie będzie planarny, bo dalej nie będzie można narysować go bez przecięć.
Indeks chromatyczny kliki o nieparzystej liczbie wierzchołków wynosi tyle co liczba jej wierzchołków. Dodatkową krawędź kolorujemy tym kolorem, którym nie są pokolorowane krawędzie wierzchołka tej krawędzi, który należy do kliki.
Czyli indeks i liczba chromatyczna tego grafu jest równa \(\displaystyle{ 9}\).
2) We wszystkich przypadkach zakładam, że do grafu nie dodajemy dodatkowego wierzchołka.
Jeżeli był eulerowski i dodano jedną krawędź i ta krawędź łączy dwa różne wierzchołki to oczywiście eulerowski już nie będzie, bo sumy stopni tych dwóch wierzchołków do których dodaliśmy krawędź będą nieparzyste. Jeżeli w grafie dopuszczamy pętle, to dodanie takiej pętli nic nie zmieni, także odpowiedź zależy od tego czy dopuszczamy grafy, które nie są proste: nie / nie wiadomo.
Jeżeli był hamiltonowski i dodaliśmy krawędź to dalej ten cykl Hamiltona będzie, nawet może pozostać taki sam jaki był.
No jak nie był planarny, to oczywiście dalej nie będzie planarny, bo dalej nie będzie można narysować go bez przecięć.