7. Grafy

7.1. Zadania na zajęcia

Ćwiczenie 7.3

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?

Ćwiczenie 7.4

Na ile sposobów można pokolorować graf \(K_5\) (\(K_n\) - graf pełny o \(n\) wierzchołkach) sześcioma kolorami?

Ćwiczenie 7.5

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.

Ćwiczenie 7.6

Narysować spójny graf planarny, w którym każdy wierzchołek ma stopień 4 i każda ściana jest ograniczona trzema krawędziami.

Ćwiczenie 7.7

Dla jakich \(n\in \mathbb{N}\) graf pełny \(K_n\) jest eulerowski?

Ćwiczenie 7.8

Dla jakich \(m,n\in \mathbb{N}\) graf pełny dwudzielny \(K_{m,n}\) jest hamiltonowski?

Ćwiczenie 7.9

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.

7.2. Zadania dodatkowe

Ćwiczenie 7.10

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.

Ćwiczenie 7.11

Pokazać, że graf, w którym każdy wierzchołek jest stopnia \(d\) i który ma \(2d+1\) wierzchołków jest eulerowski.

Informacja

Materiały na tej stronie przygotowała Agata Pilitowska.

Projekt „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.

Zadanie 7 pn. „Pilotażowa realizacja innowacyjnej ścieżki kształcenia obejmującej znaczny komponent zespołowych zajęć projektowych we wczesnej fazie studiów” realizowane w ramach projektu „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.