Wykład o grafach

DEF. Graf to uporz _{}adkowana para zbiorów (V, E), gdzie V to wierzhołki, a E to kraw_{}edzie, czyli pary elementów z V. Jeśli pary s _{}a uporz _{}adkowane, to graf jest skierowany, w przeciwnym razie nieskierowany.

DEF. Graf spójny to taki nieskierowany, że z każdego wierzhołka da si_{}e przejść po kraw_{}edziach do każdego innego. Jeśli graf jest niespójny, to można go podzielić na spójne składowe, czyli maksymalne spójne podgrafy.

DEF. Drzewo jest grafem spójnym nieposiadaj _{}acym cykli. Graf złożony z drzew nazywamy lasem.

ĆW. Pokazać, że drzewo o n wierzchołkach ma n − 1 kraw_{}edzi.

DEF. Niech S(v) oznacza zbiór s _{}asiadów wierzchołka v.

DEF. Graf dwudzielny to taki, którego wierzchołki da si_{}e podzielić na dwa podzbiory tak, aby nie było kraw_{}edzi mi_{}edzy dwoma wierzchołkami z tego samego podzbioru.

DEF. DFS-em nazywamy procedur_{}e przeszukuj _{}ac _{}a graf w nast_{}epuj _{}acy sposób:

procedure DFS(gdzie in V) begin

bylo[gdzie]=k++;

for each v in S(gdzie)

begin

if (bylo[v]==0) DFS(v); end;

end;

ZAD0. Pokazać, że jeśli w spójnym grafie stopień każdego wierzchołka jest parzysty, to graf posiada cykl Eulera.

ZAD1. Znaleźć wszystkie takie grafy o n wierzchołkach, dla których da si_{}e dobrać tak zbiór mniej niż n kraw_{}edzi, aby z każdego wierzchołka wychodziła nieparzysta liczba kraw_{}edzi z tego zbioru.

ZAD2. Pokazać, że w grafie spójnym, w którym stopień każdego wierzchołka wynosi co najmniej 2 da si_{}e tak ponumerować kraw_{}edzie liczbami od 1 do liczby kraw_{}edzi, by NW D kraw_{}edzi wychodz _{}acych z każdego wierzchołka wynosiło 1.

DEF. BFS-em nazywamy procedur_{}e przeszukuj _{}ac _{}a graf w nast_{}epuj _{}acy sposób:

procedure BFS(pocz in V) begin

kol[0]=pocz; kolk=0; kolp=0; while (kolk¡=kolp) begin

gdzie=kol[kolk];

kolk++;

for each v in S(gdzie) begin

if (bylo[v]==false) begin

bylo[v]=true; kolp++; kol[kolp]=v;

end; end;

end; end;

ZAD1. Pokazać, że graf jest dwudzielny wtedy i tylko wtedy, gdy nie posiada cyklu nieparzystej długości.

TW. (Ore) Jeśli w grafie dla każdej pary wierzchołków niepoł _{}aczonych kraw_{}edzi _{}a suma ich stopni wynosi conajmniej n, to w grafie istnieje cykl Hamiltona.

ZAD1. Na przyj_{}eciu spotkało sie n osób (n 5). Wiadomo, ze wśród dowolnych trzech osób pewne dwie znaj _{}a si_{}e. Dowieść, ze spośród uczestników przyj_{}ecia można wybrać nie mniej niż n/2 osób i posadzić przy okr _{}agłym stole tak, aby każdy siedział mi_{}edzy dwoma swoimi znajomymi.

JESZCZE ZADANKO NA MYŚLENIE GRAFOWE

ZAD1. Ogrodnik Hofman opiekuje si_{}e, e swoim ogrodem maj _{}acym kształt nieskończonej płaszczyzny z układem współrz_{}ednych. Na wiosn_{}e Hofman przygotowuje skonczon _{}a liczb_{}e miejsc w punktach kratowych (czyli tych o współrz_{}ednych całkowitych) w których ma zamiar posadzić róże b _{}adź też goździki. Pokazać, że Hofman może w ten sposób posadzić w odpowiednich miejscach róże, a w pozostałych goździki (po jednym kwiacie na kazdym miejscu), aby na kazdej prostej równoległej do którejkolwiek z osi układu współrz_{}ednych liczba posadzonych róż i goździków różniła si_{}e co najwyżej o 1.

TW. (Hall) W grafie dwudzielnym, jeśli dla każdego podzbioru A k wierzchołków z jednej strony co najmniej k różnych wierzchołków z drugiej strony jest poł _{}aczonych kraw_{}edzi _{}a z wierzchołkiem z A, to da si_{}e każdemu wierzchołkowi z pierwszej strony doparować inny wierzchołek z drugiej strony.

ZAD1. Tablica ogłoszeń na warsztaty ma kształt tablicy 2006 × 1 podzielonej na 2006 sekcji 1 × 1. Złośliwy Onufry kazał Joasi przypi _{}ać do tablicy 2006 ogłoszeń, każde o polu 1 w z góry przez niego ustalonych miejscach (przy czym ogłoszenie może mieć dowolny kształt, może nawet nie być spójne). Pokazać, że Joasia może tak przypi _{}ać ogłoszenia szpilkami, aby każde ogłoszenie było przypi_{}ete dokładnie jedn _{}a szpilk _{}a i aby w każdej sekcji była użyta dokładnie jedna szpilka.