kolorowanie

warning: Creating default object from empty value in /usr/share/drupal6/modules/taxonomy/taxonomy.pages.inc on line 33.

Ćwiczenia 1: planarność, kolorowanie

Zadanie 1
Wierzchołki grafu permutacji $G_n$ są etykietowane permutacjami zbioru $n$-elementowego. Dwa wierzchołki w tym grafie są połączone krawędzią, jeśli odpowiadające im permutacje różnią się transpozycją sąsiednich elementów. Dla jakich $n$ graf $G_n$ jest planarny?

Zadanie 2
Pokaż nieplanarność grafu Petersena
(a) z tw. Kuratowskiego (zawiera podgraf homeomorf. z K3,3 lub K5);
(b) wyprowadzając ograniczenie górne na liczbę krawędzi dla grafów planarnych o obwodzie r.

Zadanie 3

Subskrybuje zawartość