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

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

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

1slik

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

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

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

slik2

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

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

slik3

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

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

slik4

Решење. Пошто у овој држави има m градова, a Тутин је један од њих, то без њега има m-1 градова. С обзиром на услове задатка, између ових m-1 градова може постојати највише \dfrac{(m-1)(m-2)}{2} путева. А пошто из Тутина иде само један пут, то у овој држави може постојати највише \dfrac{(m-1)(m-2)}{2}+1 путева. \square

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

Решење. Нека у овом граду има n тргова. Тада је укупан број путева у овом граду \dfrac{n\cdot 5}{2}. А пошто број путева не може бити разломак, већ мора бити цео број, онда n мора бити паран број. \square

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

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

Саберемо ли ове неједначине, добићемо:
II+III+I+III+I+II\geq42
а одавде је:
I+II+III\geq21
Овим смо показали да број летова не може бити мањи од 21. Ево и једног примера који илуструје на који начин могу бити повезани авио-линијама ови градови. \square

slik5

Advertisements

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

Оставите коментар

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s