Grafy

Definicje

Graf - wierzchołki i kraw_{}edzie pomi_{}edzy nimi. G oznaczamy graf, V zbiór wierzchołków, E zbiór kraw_{}edzi. Stopień wierzchołka to ilość kraw_{}edzi z niego wychodz _{}acych, oznaczamy deg(v). Cykl Eulera to cykl, który przechodzi przez wszystkie kraw_{}edzie. Cykl Hamiltona to cykl, który przechodzi przez wszystkie wierzchołki dokładnie jeden raz. Graf dwudzielny to taki, którego wierzchołki da si_{}e podzielić na dwa zbiory A i B takie, że pomi_{}edzy dwoma wierzchołkami z tego samego zbioru nie ma kraw_{}edzi. Graf spójny to taki, w którym da si_{}e przejść z każdego wierzchołka do każdego. Graf jest drzewem, gdy jest spójny i nie ma cyklu. Graf jest planarny, gdy da si_{}e go narysować na płaszczyźnie tak, by jego kraw_{}edzie si_{}e nie przecinały.

Fakciki

1. Lemat o uściskach dłoni - ∑ _{v∈V} deg(v) = 2|E|.

2. Jeśli w grafie G zachodzi ∀_{v∈V} deg(v) 2, to istnieje cykl.

3. Jeśli graf G jest spójny, |V | = n, |E| = n − 1, to graf G jest drzewem.

4. Graf G jest dwudzielny wtedy i tylko wtedy gdy w G nie ma cyklu nieparzystej długości

5. Jeśli ∀_{v∈V} 2 | deg(v), to graf G ma cykl Eulera.

6. Tw. Orego Jeśli graf G jest spójny, n-liczba wierzchołków spełnia n > 3 oraz dla każdej pary wierzchołków niepoł _{}aczonych kraw_{}edzi _{}a suma ich stopni jest wi_{}eksza lub równa od n, to wtedy graf G ma cykl Hamiltona.

7. Wniosek Diraca. Jeśli ∀_{v∈V} deg(v) \frac{n}{2}, to G ma cykl Hamiltona.

8. Tw. Halla Jeśli mamy n chłopców i m n dziewczynek, i zachodzi warunek Halla, czyli każda grupa k chłopców poł _{}aczywszy swoj _{}a wiedz_{}e zna niemniej niż k dziewczynek, to można dziewczynki i chłopców poł _{}aczyć w pary tak, by para si_{}e znała i pary były rozł _{}aczne.

Planarność

1. Gdy graf G jest planarny, n oznacza liczb_{}e jego wierzchołków, m liczb_{}e jego kraw_{}edzi, a f liczb_{}e jego ścian licz _{}ac t_{}e nieograniczon _{}a, to n − m + f = 2.

2. Gdy graf G jest planarny, oznaczenia jak poprzednio, n 3 to zachodzi m 3n − 6.

3. Jeśli graf G jest planarny, to zawiera wierzchołek stopnie niewi_{}ekszego niż 5.

4. Jeśli graf G jest planarny, to jego wierzchołki dadz _{}a si_{}e pokolorować na 5 kolorów, tak, by żadne dwa poł _{}aczone kraw_{}edzi _{}a wierzchołki nie były tego samego koloru.

5. Twierdzenie o czterech barwach. Jeśli graf G jest planarny, to jego wierzchołki dadz _{}a si_{}e pokolorować na 4 kolorów, tak, by żadne dwa poł _{}aczone kraw_{}edzi _{}a wierzchołki nie były tego samego koloru (dowód jest trudny, zrobiony dopiero w 1976 roku).

6. K_{5} i K_{3,3} nie s _{}a planarne.

7. Twierdzenie Kuratowskiego. Graf G nie jest planarny wtedy i tylko wtedy, gdy zawiera podgraf homeomorficzny z K_{3,3} lub K_{5}. (grafy G_{1} i G_{2} s _{}a homeomorficzne, jeśli można z nich uzyskać grafy izomorficzne poprzez dostawianie na kraw_{}edziach wierzchołków stopnia 2).

Zadanka

1. Jest n chłopców i n dziewczynek, każda dziewczynka zna dokładnie d chłopców i każdy chłopiec zna dokładnie d dziewczynek. Wykaż, że można tak dobrać w pary dziewczynki i chłopców, aby w każdej parze si_{}e znali (relacja znajomości jest symetryczna).

2. Mówimy, że prostok _{}at na pokratkowanej płaszczyźnie n × m, n > m jest łaciński, gdy wpisano w niego liczby od 1 do n tak, że w każdym wierszu i w każdej kolumnie żadne dwie liczby si_{}e nie powtarzaj _{}a. Wykaż, że każdy prostok _{}at łaciński n × m, n > m można dopełnić do kwadratu łacińskiego n × n.

3. Do sejfu jest n cyfrowy kod złożony z samych zer i jedynek. Zamek działa tak, re jeżeli n ostatnio wpisanych zer i jedynek tworzy otwieraj _{}ac _{}a kombinacj_{}e, to sejf si_{}e otwiera. Wyznacz liczb_{}e klikni_{}ec w klawiatur_{}e któr _{}a musimy wykonać, aby mieć pewność, że otworzymy sejf.

4. Na warsztatach matematycznych jest n wył _{}aczników światła, przy czym światło zapala si_{}e tylko wtedy, gdy wszystkie wył _{}aczniki s _{}a ustawione na zapalenie. Wyznacz ilość pojedynczych przeł _{}aczeń, które b_{}edzie musiała wykonać kadra po ciszy nocnej, aby mieć pewność, że światło zostanie zgaszone (zakładamy, że kadra stosuje optymalny algorytm).

5. Dany jest zbiór liczb od 1 do n + 1. Mówimy, że dwie uporz _{}adkowane n-tki s _{}a ze sob _{}a zaprzyjaźnione, gdy istniej _{}a takie indeksy i oraz j, że na i-tym indeksie w pierwszej n-tce jest ta sama liczba, która jest na j-tym indeksie w drugiej n-tce. Wyznacz maksymaln _{}a moc zbioru n-tek, takiego, że każde dwie s _{}a ze sob _{}a zaprzyjaźnione.

6. Wykaż, że K_{5} i K_{3,3} nie s _{}a planarne.