szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 cze 2017, o 20:54 
Użytkownik

Posty: 7
Lokalizacja: Wrocław
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 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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 lip 2017, o 19:36 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
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 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ęć.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 Ciągi liczb wierchołków kolejnych stopni grafów?  Sonite  0
 Drzewo i tw. Eulera dla spójnych grafów planarnych  Sonite  6
 3 zadania...  Ciapanek  2
 Niezmienniki izomorfizmu grafów  author  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl