Без подизања оловке

Често ми ученици као изазов постављају разне задатке из рекреативне математике. Одабрао сам два која ћу овдје да поставим и ријешим. Примјетио сам да се они понављају из године у годину, посебно овај први.

ЗАДАТАК 1.

Може ли се у једном потезу без подизања оловке са папира нацртати отворена коверта са доње слике?

Otvorena кoverta

ЗАДАТАК 2.

Може ли се у једном потезу без подизања оловке са папира нацртати таква затворена крива линија, која сваку дуж на доњој слици пресијеца тачно једанпут?

Slika

Рјешавање једног сличног проблема од стране швајцарског математичара Леонарда Ојлера (Leonhard Paul Euler, 1707-1783) 1736. године, довело је до оснивања теорије графова. Њему су током боравка у Кенигсбергу (у тадашњој Пруској, данашњем Калињинграду у Русији) мјештани поставили сљедећи проблем, тзв. проблем кенигсбершких мостова: „Преко ријеке Прегел која протиче кроз Кенигсберг и коју два острва дијеле на два рукавца, постоји седам мостова који повезују острва и обале ријеке (као што је приказано на доњој слици). Да ли је могуће пријећи све мостове не прелазећи ни преко једног два или више пута?“

7 mostova Kenigsberga

Ојлер је одговорио да то није могуће. Погледајмо сада како је Ојлер дошао до рјешења проблема.

Дијелове копна (лијеву и десну обалу, као и свако острво) можемо означити тачкама, а мостове линијама које повезују те тачке (као што је приказано на горњој слици). Тако добијамо граф са тјеменима и ивицама, тјеменима називамо тачке а ивицама поменуте линије. Ако из неког тјемена графа полази (не)паран број ивица, онда то тјеме можемо назвати (не)парним. Постављени проблем можемо сада овако преформулисати: „Да ли се добијени граф може нацртати у једном потезу без подизања оловке са папира?“ Ако је то могуће, онда приликом цртања графа полазимо из једног његовог тјемена, а затим, прије уласка у произвољно тјеме цртамо једну линију а након изласка другу, да би на крају завршили цртање у неком тјемену. Јасно је да ако цртање почињемо и завршавамо у истом тјемену, сва тјемена графа морају бити парна, а ако то није случај, онда су сва тјемена графа осим почетног и крајњег парна, док су та два непарна. На слици горе видимо да су три тјемена непарна а једно парно. На основу тога и претходног разматрања, закључујемо да је задани начин преласка мостова Кенигсберга немогућ.

Посматрајмо сада слику из првог задатка као граф. Видимо да има два непарна и три парна тјемена, тако да је могуће нацртати отворену коверту са слике, при чему цртање почињемо у једном непарном тјемену а завршавамо у другом. Провјерите!

Што се тиче рјешења другог задатка, нацртајмо граф као што је то приказано на сљедећој слици.

CGraf

Видимо да сваку дуж са слике пресијеца тачно једна ивица графа, при чему не постоје двије које су пресјечене истом. Сада можемо преформулисати овај задатак на исти начин као и проблем кенигсбершких мостова: „Да ли се граф са слике може нацртати у једном потезу без подизања оловке са папира?“ Пошто имамо 4 непарна и 2 парна тјемена, одговор на постављено питање је одречан.

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

ЗАДАТАК 3.

Може ли мрав прошетати ивицама коцке, тако да сваком ивицом прође тачно једанпут? А ивицама тетраедра; октаедра?

Advertisements

3 thoughts on “Без подизања оловке

  1. Повратни пинг: Чекајући мост | Физика у Бранку

Оставите одговор

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

WordPress.com лого

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

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

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

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

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

Google+ photo

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

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