--- title: "Grafy" lecture_number: 6 has_solutions: false has_exercises: true --- ```{include} ../_includes/sagecell-loader.md ``` # Grafy ## Zadania na zajęcia ::::{exercise} :class: [exercise] Siedmiu przyjaciół wyjeżdża na wakacje i obiecuje, że każdy z nich wyśle pocztówki trzem spośród pozostałych. Korzystając z teorii grafów odpowiedzieć, z uzasadnieniem, czy może się zdarzyć, że każdy z nich dostanie pocztówki od tych, do których sam napisze? :::: ::::{exercise} :class: [exercise] Na ile sposobów można pokolorować graf $K_5$ ($K_n$ - graf pełny o $n$ wierzchołkach) sześcioma kolorami? :::: ::::{exercise} :class: [exercise] Narysować spójny graf planarny z więcej niż ośmioma wierzchołkami, w którym każda ściana jest ograniczona czterema lub sześcioma krawędziami i istnieje dokładnie sześć ścian ograniczonych czterema krawędziami. :::: ::::{exercise} :class: [exercise] Narysować spójny graf planarny, w którym każdy wierzchołek ma stopień 4 i każda ściana jest ograniczona trzema krawędziami. :::: ::::{exercise} :class: [exercise] Dla jakich $n\in \mathbb{N}$ graf pełny $K_n$ jest eulerowski? :::: ::::{exercise} :class: [exercise] Dla jakich $m,n\in \mathbb{N}$ graf pełny dwudzielny $K_{m,n}$ jest hamiltonowski? :::: ::::{exercise} :class: [exercise] Niech $G=(\mathcal{P}(\{1,2,3\}),E)$ będzie grafem, w którym $(X,Y)\in E$ wtedy i tylko wtedy, gdy $\max X\in Y$ lub $\max Y\in X .$ Podać minimalną liczbę kolorów za pomocą których można pokolorować wierzchołki otrzymanego grafu w taki sposób, aby sąsiednie miały różne barwy. :::: ## Zadania dodatkowe ::::{exercise} :class: [exercise] Pięciu specjalistów $s_1,s_2,s_3,s_4,s_5$ jest członkami pięciu zespołów: $z_1=\{s_1,s_2\}$, $z_2=\{s_1, s_3,s_4\}$, $z_3=\{s_1,s_2,s_3\}$, $z_4=\{s_3,s_4\}$ oraz $z_5=\{s_1,s_3,s_4,s_5\} .$ Jeden specjalista z każdego zespołu ma być reprezentantem komisji. Czy jest możliwe, aby z każdego zespołu wysłać innego specjalistę? Jeśli tak wskazać przykładową komisję, jeśli nie wyjaśnić dlaczego jest to niemożliwe. :::: ::::{exercise} :class: [exercise] Pokazać, że graf, w którym każdy wierzchołek jest stopnia $d$ i który ma $2d+1$ wierzchołków jest eulerowski. :::: ```{include} ../_includes/titlepage-info.md ```