Неколико занимљивих задатка са графовима

Многи лепи логичко-комбинаторни задаци могу се решавати помоћу графова. Наведено је неколико задатака са решењима. Задаци су намењени старијим основцима.

Задатак 1. Могу ли се следеће фигуре нацртати без подизања оловке и без пролажења већ нацртаном линијом?

Решење. Могуће је на овај начин нацртати другу фигуру. Уколико се приликом цртања у некој од тачака (чворова графа) где се сусреће више линија (грана графа)  завршава паран број линија, могуће је дату фигуру нацртати без подизања оловке. За прву фигуру то није могуће!

Задатак 2. Између девет планета Сунчевог система уведен је систем комуникације ракетама. Ракете иду следећим маршутама: Земља-Меркур, Плутон-Венера, Земља-Плутон, Плутон-Меркур, Меркур-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Јупитер, Јупитер-Марс и Марс-Уран. Може ли се на помоћу ових веза послати порука са Земље на Марс?

Решење. Представимо односе између ових планета графом.

Сада једноставно видимо да не постоји веза између Земље и Марса.

Задатак 3. На једном пољу су у снегу забележени трагови зеца који се кретао од дрвета до дрвета. Да ли се на основу трагова може тврдити испод ког дрвета се он налази сада?

Решење. Зец може бити испод једног од дрвета која су са непарним бројем стаза повезана са осталима. Постоје два таква дрвета, па не можемо са сигурношћу рећи испод ког се налази зец, али знамо да је испод једог од та два. Када је број стаза паран, значи да је он дошао до испод тог дрвета и отишао одатле.

Задатак 4. У једној држави има градова, од којих је један Тутин. Неки парови градова су повезани путевима, и притом између никоја два града не постоји више од једног пута. Колико највише путева може бити у тој држави ако из Тутина води само 1 пут?

Решење. Пошто у овој држави има градова, a Тутин је један од њих, то без њега има градова. С обзиром на услове задатка, између ових градова може постојати највише путева. А пошто из Тутина иде само један пут, то у овој држави може постојати највише путева.

Задатак 5. У једном граду има неколико тргова. Од сваког трга води по 5 улица. Свака улица почиње код једног трга и завршава се код неког другог трга. Доказаtи да је број тргова паран.

Решење. Нека у овом граду има тргова. Тада је укупан број путева у овом граду . А пошто број путева не може бити разломак, већ мора бити цео број, онда мора бити паран број.

Задатак 6. У једној држави постоји 15 градова. Неки од њих међусобно су повезани авио-линијама, које одржавају три компаније. Познато је да ако било која од ове три компаније обустави своје летове и даље ће бити могуће доћи из било ког града у било који други град (евентуално, са преседањима), користећи услуге друге две компаније.  Колико најмање авио-линија може бити у држави?

Решење. Обележимо број летова прве, друге и треће компаније са , и . Ако се искључи прва компанија из летења, остаће летова, а тај број није мањи од 14, тј. . Слично се добија и ако искључимо другу или трећу компанију: и .

Саберемо ли ове неједначине, добићемо:

а одавде је:

Овим смо показали да број летова не може бити мањи од 21. Ево и једног примера који илуструје на који начин могу бити повезани авио-линијама ови градови.