KÓŁECZKO Z GRAFÓW (15.10.06)

1. TEORIA

1.1. Graf - wierzchołki i krawędzie między nimi.

1.2. Standardowe oznaczenia =¿ G - graf; V - zbiór wierzchołków; E - zbiór kraw_{}edzi; deg(v) - stopień wierzchołka (liczba kraw_{}edzi wychodz _{}acych z danego wierzchołka).

1.3. Graf spójny to taki, w którym da się przejść z każego wierzchołka do każego. Drzewo, to graf spójny, nie maj _{}acy cyklu. Graf plenarny to taki, który można narysować na płaszczyźnie tak, by jego kraw_{}edzie si_{}e nie przecinały. Graf dwudzielny to taki, którego wszystkie wierzchołki da si_{}e podzielić na dwa podzbiory takie, że każda kraw_{}edź łaczy wierzchołki z różnych podzbiorów.

2.ZADANKA

2.1. W pokoju 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. Ile maksymalnie trzeba b_{}edzie wykonać przeł _{}aczeń, stosuj _{}ac optymalny algorytm, aby zapalić światło?

2.2. W pewnym państwie jest n miast, w tym jedna stolica, niektóre z nich s _{}a poł _{}aczone jednokierunkowymi drogami. Wiadomo, że ze stolicy można dojechać do każego miasta oraz, że z każego miasta wychodzi tyle samo dróg, co do niego wchodzi. Pokazać, że z każdego miasta można dojechać do stolicy.

2.3. W turnieju GO brało udział n graczy. Każdy rozegrał z każdym jeden mecz i nie było remisów. Udowodnić, że istnieje gracz, który ograł każdego innego gracza pośrednio lub bezpośrednio (tzn. ograł innego gracza, który go ograł).

2.4. Pokazać, że graf jest dwudzielny wtedy i tylko wtedy, gdy wszystkie jego cykle s _{}a parzystej długości.

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

2.6. Niech w, k, s oznaczaj _{}a odpowiednio liczby: wierzchołków, kraw_{}edzi i ścian wielościanu. Czy istnieje taki wielościan, w którym:

• w = 8, k = 14, s = 8,

• w = 8, k = 15, s = 9,

• w = 13, k = 35, s = 24,

• w = 25, k = 37, s = 14?