Matematyka dyskretna 1/Ćwiczenia 14: Grafy III
Z Studia Informatyczne
< Matematyka dyskretna 1
Przejdź do nawigacjiPrzejdź do wyszukiwaniaWersja z dnia 15:04, 3 paź 2021 autorstwa Luki (dyskusja | edycje) (Zastępowanie tekstu - "<div class="thumb t(.*)"><div style="width:(.*)px;"> <flash>file=(.*)\.swf\|width=(.*)\|height=(.*)<\/flash> <div\.thumbcaption>(.*)<\/div><\/div> <\/div>" na "$4x$5px|thumb|$1|$6")
Grafy III
Ćwiczenie 1
Wskazówka
Rozwiązanie
Ćwiczenie 2
W pewnym wielościanie wszystkie ściany są pięciokątami i sześciokątami. Ile jest ścian pięciokątnych, jeżeli w każdym wierzchołku spotykają się dokładnie trzy ściany?
Wskazówka
Rozwiązanie
Ćwiczenie 3
Pokaż, że dla spójnego, prostego grafu planarnego
o co najmniej trzech wierzchołkach zachodzi
Wskazówka
Rozwiązanie
Ćwiczenie 4
Pokaż, że spójny graf planarny
o co najmniej jednym wierzchołku posiada wierzchołek o stopniu nie większym niż .Wskazówka
Rozwiązanie
Ćwiczenie 5
Znajdź liczbę chromatyczną
-wymiarowej kostki , czyli grafu, którego wierzchołki to ciągi , gdzie , a krawędzie łączą te ciągi, które różnią się tylko na jednej pozycji.Wskazówka
Rozwiązanie
Ćwiczenie 6
Nie korzystając z Twierdzenia 14.13 o czterech barwach pokaż, że graf planarny bez trójkątów jest czterokolorowalny.
Wskazówka
Rozwiązanie