Его величество граф

С незапамятных времён на Путях трёх земных Вещий камень стоит,
И надпись Путнику на нём гласит:
"Направо пойдёшь – коня потеряешь, себя спасёшь"
"Налево пойдёшь – себя потеряешь, коня спасёшь"
"Прямо пойдёшь – и себя, и коня потеряешь".

Случай странный! Случай редкий!
Цифры в ссоре! Вот те на!
Со своей стоять соседкой не желает ни одна!
Труд нелегкий! Труд немалый!
Сделай так, чтоб на листке
Цифра каждая стояла
От соседок вдалеке!

На ваших листочках в свободных кружочках вы должны расставить цифры от 1 до 9, кроме тех, которые уже там есть, таким образом, чтобы ни одна из них не стояла рядом со своей соседкой по порядковому номеру

5

3

7

Надо выбрать, если это возможно города на земном шаре с песней без эпизодов фильма

https://ya.ru/video/preview/2768269125794342365

Задача 1. Небольшая компания ребят встретилась на вокзале, чтобы вместе поехать за город. При встрече они поздоровались друг с другом. Сколько ребят поехало за город, если всего было 15 рукопожатий?

15 рукопожатий

Что такое граф?

Граф – это набор точек, каждые из которых соединены линиями.
Точки – называются вершинами, а соединяющие их линии (я не сказала отрезки) – ребрами.

Что такое граф

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

содержание

3

4

Граф – это наглядное средство представления состава и
структуры системы.

В

А

С

дуга

ребро

петля

вершина

Задача 9. В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель и рис, а из напитков – чай и кофе. Сколько различных вариантов обедов можно составить из указанных блюд?

Мы сейчас с вами выведем алгоритм для решения этой задачи. Для этого нам нужно будет перенестись на более чем 200 лет назад и оказаться вместе с великим математиком Леонардом Эйлером в городе Кёнигсберге (сейчас этот город называется Калининград).

Первая работа по теории графов принадлежит именно ему (1736), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например карта, комплекс, диаграмма, сеть, лабиринт.

Бывший Кёнигсберг расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз.Никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось. Как поступил Эйлер?

Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощенную схему мостов. Получился граф, вершины которого – части города, разделенные рекой, а ребра – мосты.
Попробуйте провести линии по всем ребрам -"мостам", не отрывая карандаша от бумаги.

Все дело в числе ребер, сходящихся в вершине.
Давайте посчитаем, сколько ребер сходится в каждой вершине графа. Напишите рядом с каждой вершиной число, отражающее количество ребер, в ней сходящихся, и назовем вершину четной или нечетной в зависимости от того, какое число, четное или нечетное, стоит рядом. Итак,

в вершине А сходится 5 ребер,

в вершине В-3,

в вершине С-3,

в вершине Д-3.

Какими являются все  эти вершины, четными или нечетными?

Сколько у нас четных вершин?

Сколько нечетных вершин?

5

3

3

3

Леонард Эйлер сформулировал правило:
Обход возможен:
1. ЕСЛИ все вершины – четные, и его можно начать с любого участка.

2. ЕСЛИ 2 вершины – нечетные, то его нужно начать с одной из нечетных вершин.

3. Обход невозможен если нечетных вершин больше 2.

Вернемся к задаче «распечатанное письмо" и применим правило Эйлера.
– Сколько ребер сходится в каждой вершине?

Как нужно совершить обход этого графа, согласно правилу Эйлера?

В вершине А сходится 3 ребра,

в вершине В-4,

в вершине С-2,

в вершине Д-4,

в вершине Е-3.)

– Что вы скажите о четности вершин в этом графе?

С каким понятием мы сегодня познакомились и чему научились? 
Что вы узнали о графе?
ответьте на следующие вопросы:

1. Что такое граф?

2. Вершины?

3. Ребра?

4. Когда вершина называется четной, а когда нечетной?

5. Как вы думаете, где еще вы встречались с графами?

6. Где на практике могут применяться графы?

Выводы

Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ.
В математике даже есть специальный раздел, который так и называется: «Теория графов».

содержание

С помощью графов указываются различные связи между объектами.

Инженер чертит схемы электрических цепей.

Химик рисует структурные формулы, чтобы показать, как в сложной молекуле с помощью валентных связей соединяются друг с другом атомы.

Историк прослеживает родословные связи по генеалогическому дереву.

Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.

Социолог по сложнейшей диаграмме показывает, как подчиняются друг другу различные отделы одной огромной корпораций.

(География 10 кл. В.П. Максаковский)

Сказка «Царевна-лягушка»

Биология 10-11кл. В.И. Сивоглазов

Иерархическая структура системы административного управления (граф в виде дерева), между элементами которых установлены отношения подчиненности.

Применение графов

Лабиринт - это граф. А исследовать его - это найти путь в этом графе.

Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании.