Matematyka dyskretna 1/Ćwiczenia 12: Grafy

Grafy I

<flash>file=Cw grafy operation.swf|width=300|height=150</flash>

<div.thumbcaption>1. Grafy

𝐆_{1}

oraz

𝐆_{2}

Ćwiczenie 1

Niech $𝐆_{1}$ oraz $𝐆_{2}$ będą grafami przedstawionymi na rysunku 1. Przedstaw sumę $𝐆_{1} \cup 𝐆_{2}$ , przecięcie $𝐆_{1} \cap 𝐆_{2}$ , oraz różnicę $𝐆_{1} - 𝐆_{2}$ .

Wskazówka

Rozwiązanie

<flash>file=Cw grafy operation.swf|width=300|height=150</flash>

<div.thumbcaption>2. Grafy

𝐆_{1} \cup 𝐆_{2}

<flash>file=Cw grafy operation.swf|width=300|height=150</flash>

<div.thumbcaption>3. Przecięcie

𝐆_{1} \cap 𝐆_{2}

oraz różnica

𝐆_{1} - 𝐆_{2}

Suma $𝐆_{1} \cup 𝐆_{2}$ jest przedstawiona na rysunku 2, zaś przecięcie $𝐆_{1} \cap 𝐆_{2}$ oraz różnica $𝐆_{1} - 𝐆_{2}$ na rysunku 3.

Ćwiczenie 2

Graf $𝐆 = (V, E)$ jest przedstawiony na rysunku 4. Przedstaw graf ilorazowy $𝐆 / ≜$ dla relacji równoważności $≜ \subseteq V \times V$ zdefiniowanej przez:

v_{i} ≜ v_{j}

w.t.w.

| i - j |

jest wielokrotnością

4 .

{rys. 4 Graf $𝐆$ . Rysunek z pliku:cwgrafyiloraz.eps}

Wskazówka

Rozwiązanie

Iloraz $V / ≜$ zbioru $V = {v_{0}, v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}}$ to ${{v_{0}, v_{4}, v_{8}}, {v_{1}, v_{5}, v_{9}}, {v_{2}, v_{6}}, {v_{3}, v_{7}}}$ . Z faktu, że $v_{0} v_{2} \in E$ wynika, że wierzchołki ${v_{0}, v_{4}, v_{8}}$ oraz ${v_{2}, v_{6}}$ są sąsiednie w grafie $𝐆 / ≜$ . Z kolei krawędzie $v_{1} v_{4}, v_{3} v_{5} \in E$ dają krawędzie ${{v_{0}, v_{4}, v_{8}}, {v_{1}, v_{5}, v_{9}}}$ oraz ${{v_{1}, v_{5}, v_{9}}, {v_{3}, v_{7}}}$ w grafie $𝐆 / ≜$ . Ponadto nie występują tu już żadne inne krawędzie. Graf $𝐆 / ≜$ został przedstawiony na rysunku 5.

{rys. 5 Graf $𝐆 / ≜$ . Rysunek z pliku:cwgrafyilorazodp.eps}

Ćwiczenie 3

Niech $𝐆$ będzie grafem prostym z co najmniej dwoma wierzchołkami. Wykaż, że $𝐆$ zawiera dwa wierzchołki tego samego stopnia.

Wskazówka

Rozwiązanie

Niech $𝐆$ ma $n \geq 2$ wierzchołków. Wierzchołek Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in{\sf V}\!\left(\mathbf{G}\right) } nie może mieć więcej niż Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v \right\rbrace \right\vert=n-1 } sąsiadów. Stopień dowolnego wierzchołka z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right) } leży więc w zbiorze ${0, 1, 2, \dots, n - 1}$ . Jeśli jakiś wierzchołek ma stopień $0$ , czyli jest izolowany, to każdy inny wierzchołek może mieć co najwyżej $n - 2$ sąsiadów. Z kolei gdyby istniał punkt $w$ o stopniu równym $n - 1$ , to każdy wierzchołek ze zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace w \right\rbrace } byłby sąsiadem $w$ , więc nie mogłby mieć stopnia równego $0$ . Zbiór $S$ stopni wierzchołków grafu $𝐆$ zawiera się więc albo w zbiorze ${0, 1, 2, \dots, n - 2}$ , albo w ${1, 2, 3, \dots, n - 1}$ , więc $S$ jest co najwyżej $(n - 1)$ -elementowy. Wszystkich wierzchołków jest $n$ , więc z Zasady Szufladkowej Dirichleta otrzymujemy, że istnieją dwa wierzchołki o tym samym stopniu.

Ćwiczenie 4

Wykaż, że w grupie sześciu osób zawsze znajdą się trzy, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.

Wskazówka

Rozwiązanie

Wybierzmy dowolną osobę z rozważanej szóstki i oznaczmy ją za pomocą inicjału A. Załóżmy, że A w zbiorze pięciu pozostałych osób ma więcej znajomych niż nieznajomych. A ma więc $3$ , $4$ , lub $5$ znajomych. Jeżeli istnieje chociaż jedna para w tym gronie, która się zna, to wraz z A tworzy poszukiwaną trójkę. Jeśli znajomi A nie znają się nawzajem, to trójka z nich tworzyłaby z kolei zbiór osób nieznających siebie. W przypadku, gdy A ma mniej znajomych niż nieznajomych rozumowanie jest symetryczne.

Ćwiczenie 5

Dopełnienie grafu $𝐆 = (V, E)$ to graf Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \overline{\mathbf{G}}=\left( V,\mathscr{P}_{2}\!\left( V \right)- E \right) } . Przedstaw dopełnienie grafu pełnego $𝒦_{n}$ oraz dwudzielnego grafu pełnego $𝒦_{m, n}$ . Przedstaw graf, którego dopełnienie jest z nim izomorficzne.

Wskazówka

Rozwiązanie

Dopełnieniem grafu pełnego jest graf pusty, tzn. $\overline{𝒦_{n}} = 𝒜_{n}$ . Na odwrót dopełnienie grafu pustego jest grafem pełnym: $\overline{𝒜_{n}} = 𝒦_{n}$ . Z kolei dopełnienie pełnego grafu dwudzielnego $𝒦_{n, n}$ jest rozłączną sumą dwóch klik $𝒦_{m} \cup 𝒦_{n}$ .

Cykl piecioelementowy oraz ścieżka czteroelementowa są przykładami grafów izomorficznych ze swoimi dopełnieniami.

Ćwiczenie 6

Niech $𝐆$ będzie grafem prostym, w którym każdy wierzchołek ma co najmniej $r \geq 2$ sąsiadów. Wykaż, że $𝐆$ zawiera cykl o długości co najmniej $r + 1$ .

Wskazówka

Spróbuj budować indukcyjnie możliwie długą ścieżkę. Pokaż, że musi mieć co najmniej $r$ elementów. Aby znaleźć cykl, rozważ sąsiadów ostatniego wierzchołka na tej ścieżce.

Rozwiązanie

Wskażemy odpowiednią ścieżkę definiując ją indukcyjnie. Załóżmy, że istnieje ścieżka o długości $k < r$ tzn. $v_{1} \to v_{2} \to \dots \to v_{k}$ . Wierzchołek $v_{k}$ ma co najmniej $r$ sąsiadów, musi więc mieć sąsiada $v_{k + 1}$ poza $k$ -elementowym zbiorem ${v_{1}, v_{2}, \dots, v_{k}}$ . Skonstruowaliśmy więc ścieżkę $v_{1} \to v_{2} \to \dots \to v_{k} \to v_{k + 1}$ odwiedzającą $k + 1$ wierzchołków. Powtarzając tę czynność tak długo jak $k < r$ , otrzymujemy $r$ -elementową ścieżkę:

v_{1} \to v_{2} \to \dots \to v_{r} .

Wiemy więc, że ścieżka o możliwie największej długości ma $k \geq r$ wierzchołków. Niech $w_{1} \to w_{2} \to \dots \to w_{k}$ będzie taką ścieżką. Z jej maksymalności wiemy, że wszyscy sąsiedzi $w_{k}$ są już na tej ścieżce, bo inaczej można by ją było przedłużyć. Niech więc $w_{i}$ będzie sąsiadem $w_{k}$ o najmniejszym indeksie. Ścieżka $w_{i} \to w_{i + 1} \to \dots \to w_{k}$ odwiedza $r$ sąsiadów wierzchołka $w_{k}$ , więc jest długości co najmniej równej $r$ . Wraz z wierzchołkiem $w_{k}$ tworzy więc cykl:

w_{i} \to w_{i + 1} \to \dots \to w_{k} \to w_{i}

o długości co najmniej $r + 1$ .

Ćwiczenie 7

Niech $𝐆$ będzie grafem prostym o $2 k$ wierzchołkach, niezawierającym trójkątów. Wykaż, że $𝐆$ ma co najwyżej $k^{2}$ krawędzi i podaj przykład grafu, w którym to górne oszacowanie jest osiągnięte.

Wskazówka

Zastosuj indukcję względem $k$ usuwając z grafu jedną krawędź, jej końce, a także krawędzie incydentne z tymi końcami.

Rozwiązanie

Dowód zostanie przeprowadzony indukcyjnie ze względu na $k$ . Dla $k = 1$ mamy po prostu graf bez krawędzi. Załóżmy więc, że ograniczenie liczby krawędzi zachodzi dla wszystkich grafów o $2 k \geq 2$ wierzchołkach. Niech teraz graf $𝐆$ posiada $2 k + 2$ wierzchołków. Jeśli $𝐆$ nie posiada krawędzi, to nie ma czego dowodzić. Załóżmy więc, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle vw\in{\sf E}\!\left(\mathbf{G}\right) } . Na mocy założenia indukcyjnego podgraf Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathbf{G}|_{{\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace} } posiada co najwyżej $k^{2}$ krawędzi. Ponadto, gdyby istniał Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u\in{\sf V}\!\left(\mathbf{G}\right) } sąsiadujący zarazem z $v$ jak i $w$ , to ${v, w, u}$ byłby trójkątem. Tak więc zbiór sąsiadów $v$ jest rozłączny ze zbiorem sąsiadów $w$ . Zbiór krawędzi łączących wierzchołki $v$ oraz $w$ z wierzchołkami Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace } jest więc nie większy niż rozmiar Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace } , czyli ograniczony przez $2 k$ . Zbiór wszystkich krawędzi w $𝐆$ składa się z:

krawędzi grafu $𝐆 - {v, w}$ ,
krawędzi łączących wierzchołki $v$ oraz $w$ z wierzchołkami Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace } ,
krawędzi $v w$ .

W sumie więc rozmiar zbioru krawędzi grafu $𝐆$ jest ograniczony przez

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert\leq k^2+2k+1=\left( k+1 \right)^2. }

Ćwiczenie 8

Wskaż jakieś drzewo rozpinające w grafie Petersena z rysunku 6.

{rys. 6 Graf Petersena. Rysunek z pliku:cwgrafypetersen.eps}

Wskazówka

Rozwiązanie

Ćwiczenie 9

Pokaż, że w dowolnym drzewie o co najmniej dwu wierzchołkach, istnieją co najmniej dwa wierzchołki o stopniu równym jeden.

Wskazówka

Rozwiązanie

Niech $n$ będzie liczbą wierzchołków drzewa. Drzewo jest grafem spójnym, więc każdy wierzchołek ma stopień co najmniej jeden. Załóżmy, że co najwyżej jeden wierzchołek ma stopień jeden, czyli jest co najmniej $n - 1$ wierzchołków o stopniu równym $2$ lub więcej. Sumując teraz stopnie tych wierzchołków i pamiętając, że suma taka to podwojona liczba krawędzi, dostajemy, że liczba krawędzi jest równa co najmniej

\frac{2 (n - 1) + 1}{2} = n - \frac{1}{2} .

Przeczy to faktowi, że drzewo o $n$ wierzchołkach ma $n - 1$ krawędzi.

Ćwiczenie 10

Centrum spójnego grafu $𝐆$ to taki wierzchołek $v$ , dla którego maksymalna odległość pomiędzy $v$ i dowolnym innym wierzchołkiem grafu $𝐆$ jest możliwie najmniejsza. Udowodnij, że każde drzewo ma albo dokładnie jedno centrum, albo dwa sąsiednie centra.

Wskazówka

Rozwiązanie

Zauważmy najpierw, że :

W drzewie o co najmniej trzech wierzchołkach żaden liść nie może być centrum.

Niech $v$ będzie liściem, oraz $w$ jedynym jego sąsiadem. Ścieżka pomiędzy liściem $v$ , a dowolnym innym wierzchołkiem musi przechodzić przez wierzchołek $w$ . Jeśli tylko w drzewie istnieje jeszcze jakiś wierzchołek $u$ poza $v, w$ , to $w$ leży bliżej $u$ niż $v$ .

Gdy $x$ jest wierzchołkiem drzewa, to wierzchołek najbardziej oddalony od $x$ jest liściem.

Rozważmy dowolny wierzchołek $y$ realizujący największą odległość od $x$ i załóżmy, że nie jest on liściem w drzewie $𝐓$ . Usunięcie $y$ rozspaja drzewo $𝐓$ na dwa niepuste drzewa $𝐓_{1}$ oraz $𝐓_{2}$ . Bez straty ogólności załóżmy, że $x \in 𝐓_{1}$ . Ścieżka w $𝐓$ z $x$ do dowolnego wierzchołka z $𝐓_{2}$ odwiedza $y$ , tak więc jest dłuższa niż ścieżka pomiędzy $x$ i $y$ . A zatem $y$ nie może być najdalej oddalonym wierzchołkiem od $x$ .

Usunięcie liści nie zmienia zbioru centrów w drzewie.

Usunięcie liścia nie zmienia odległości pomiędzy pozostałymi wierzchołkami. Ustalmy wierzchołek $v$ i przez $k$ oznaczmy odległość $v$ od wierzchołków najbardziej oddalonych od $v$ . Usuwając wszystkie liście, usuwamy między innymi najbardziej oddalone wierzchołki od wierzchołka $v$ . W tym zmniejszonym drzewie, parametr $k$ zmienia się więc na $k - 1$ . A zatem, usunięcie wszystkich liści, zmniejsza każdemu wierzchołkowi parametr decydujący o tym, czy jest on centrum drzewa, o jeden . Tym samym centra w drzewie z obciętymi liśćmi to centra w oryginalnym drzewie.

Drzewo o co najmniej trzech wierzchołkach posiada wierzchołek nie będący liściem.

Wynika to z faktu, że drzewo, jak każdy inny graf, posiada centrum, które nie może być liściem.

Wyposażeni w te obserwacje, z drzewa $𝐓^{0} : = 𝐓$ konstruujemy sukcesywnie drzewa $𝐓^{j}$ usuwając wszystkie liście drzewa $𝐓^{j - 1}$ tak długo, jak długo otrzymane drzewa są niepuste. A zatem ostatnie ma jeden lub dwa (ale wtedy połączone) wierzchołki, które są wobec tego centrami wyjściowego drzewa $𝐓^{0} = 𝐓$ .

Matematyka dyskretna 1/Ćwiczenia 12: Grafy

Grafy I

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia