Кьонигсбергски мостове

Леонард Ойлер е автор на занимателната задача Кьонигсбергски мостове. Счита се, че използваните  алгоритми в задачата за седемте моста на Кьонигсберг стават основа за възникване теорията на графите.

Накратко: река Прегол и нейните ръкави разделят Кьонигсберг на отделни квартали. Построени са 7 моста свързващи двата бряга на реката (А, Г) и двата острова (Б, В), като 2х2 моста свързват двата бряга на реката с единия остров, 2 моста свръзват другия остров с двата бряга и 7-мия мост свързва двата острова. В задачата се търси маршрут / последователност, по който се преминава еднократно всеки от мостовете.

За задачата Кьонигсбергски мостове входни данни са: брой на полетата е 4, брой на мостовете 7. Трябва да е реализирана забрана за повторение при преминаване на мост.

Да се реализира проект на тема: Кьонигсбергски мостове, представящ вътрешнопредметни връзки в Информатика.

В проекта да се постави стилизирано изображение на седемте Кьонигсбергски мостове. Всеки от мост да има уникален номер и да свързва две полета с уникално означение. Препоръчително е реализация на функцията Undo - възстанови предходната ситуация.

Реализираният проект чрез списъчни полета извежда информация за:

възможен мост за преминаване;

мост, който вече е преминат;

останалите необходени  мостове.

При събитие On-Click върху ред от първото поле съответният мост се прехвърля в съседното списъчно поле и не участва до края.

В самото начало потребителя има възможност да избере произволен мост и свързаните с него полетата. На всеки следващ ход са достъпни само възможните необиколени мостове за конкретното място.

Част от изводите на Ойлер са:

ако всички върхове на графа са четни (с четен брой ребра), то може с едно вдигане на молива от листа, да се начертае граф, започвайки от произволен връх и завършвайки в същия връх;

за цялостно преминаване броят на нечетните върхове на графа трябва винаги да е четен;

граф с повече от два нечетни върха е невъзможно да се начертае с едно вдигане на молива. 

Разгледайте други примерни проекти реализиращи междупредметни връзки и/или вътрешнопредметни връзки, за които е ползвана подобна логическа структура на графичните обекти и/или приложени сходни алгоритми. Прочетете допълнителен материал за: Ханойски кули, японска дама, магически квадрат.