KÓŁECZKO Z GRAFÓW (2.01.08) (Z ŻYCZENIAMI NOWOROCZNYMI GRATIS :))

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.0. Pokazać, że graf jest dwudzielny wtedy i tylko wtedy, gdy wszystkie jego cykle s _{}a parzystej długości.

2.1. 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.2. Dowieść, że wśród dwolonych 18 osób istniej _{}a cztery, z których każde dwie si_{}e znaj _{}a lub cztery, z których żadne dwie si_{}e nie znaj _{}a.

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. W państwie znajduje si_{}e 66 miast, a przewozy mi_{}edzy każdymi dwoma obsługuje jeden z czterech przewoźników. Udowodnić, że istniej _{}a takie trzy miasta, źe drogi mi_{}edzy nimi s _{}a obślugiwane przez tego samego przewożnika.

2.5. W przestrzeni dane s _{}a 244 punkty, z których każde 4 nie leż _{}a na jednej płaszczyznie. Każde dwa z punktów poł _{}aczona odcinkiem koloru rózowego, amarantowego, lila, czerwonego lub pink. Udowodnić, że istnieje taka łamana przechodz _{}aca przez 4 punkty i przez każdy tylko raz, że jest pomalowana jednym kolorem.

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 = 13, k = 35, s = 24,

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