2.13M

graf (1)

7.

Все эти изображения показывают
Для изображения
изучения связей
связь между иотдельными
между различными
объектами –
элементами.
предметами или понятиями – в
математике применяется граф.

Теория графов зародилась в ходе
решения головоломок двести с лишним
лет назад.
Термин «граф» впервые появился в книге
выдающегося венгерского математика Д.
Кёнига в 1936 г, хотя начальные задачи
теории графов восходят еще к Эйлеру
(XVIII в.).
Основы теории графов как
математической науки заложил в 1736 г.
Леонард Эйлер, рассматривая задачу о
кенигсбергских мостах. Сегодня эта
задача стала классической.

10.

Слово «граф» в математике означает
картинку, где нарисовано несколько
точек,
некоторые
из
которых
соединены
линиями.
В
процессе
решения задач математики заметили,
что
удобно
изображать
объекты
точками, а отношения между ними
отрезками или дугами.

11.

Если объекты обозначить точками, а
связи линиями, то получим граф.
Б
А
Г
Д
Е
В

12.

Граф – изображение объектов и
связей
между ними с помощью точек и
линий.
Б
А
Г
Д
Е
В

13.

Точки в графе – вершины графа.
Линии в графе – рёбра графа.
Б
А
Г
Д
Е
В

14.

Изолированной называют вершину,
из которой не выходит ни одно
ребро.
Б
А
Г
Д
Е
В

15.

А, Б, В, Г, Д, Е – вершины графа,
Е – изолированная вершина.
Б
А
Г
Д
Е
В

16.

Рёбра графа – линии, соединяющие
точки в графе.
Б
А
Г
Д
Е
В
АБ, АВ, БВ, БГ, ВГ, ГД – рёбра графа.

17.

Какие графы считаются
одинаковыми?
Если в двух графах вершины связаны
рёбрами в одном и том же порядке, то
графы считаются одинаковыми.

18.

И в том , и в другом графе рёбра одни и
те же: АВ, ВЖ, ВЕ, БЗ, БД, ЖЕ и ГЗ.
Раз вершины в этих графах связаны
одинаково, значит, графы одинаковы

19.

Степенью (или порядком) вершины
называется количество рёбер, исходящих
из этой вершины.
Вершина называется чётной, если из неё
выходит чётное число рёбер, и нечётной,
если из неё выходит нечётное число
рёбер.

20.

Задача, для решения которой Эйлер
впервые применил графы, - это задача о
мостах Кенигсберга.
В XVIII веке город Кенигсберг (сейчас
Калининград) был построен в месте слияния
двух рек на их берегах и на двух островах. В
нем было семь мостов, которые соединяли
острова между собой и с береговыми частями
города.

21.

План города Эйлер заменил его упрощенной
схемой, на которой части города изображены
точками (вершинами), а мосты - линиями

22. Получился следующий граф:

23.

В итоге Эйлер доказал общее
утверждение: для того чтобы обойти
все рёбра графа по одному разу и
вернуться в исходную вершину,
необходимо и
достаточно выполнения следующих
двух условий:
1. из любой вершины графа должен
существовать путь по его рёбрам в
любую другую вершину (граф должен
быть связным);
2. из каждой вершины должно
выходить чётное количество рёбер.

24.

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

25.

26.

В архипелаге шесть островов и шесть
мостов: между островами Адуак и Бани,
Адуак и Видо, Бани и Видо, Екити и
Гауту, Бани и Джеми, Видо и Джеми.
Можно ли по мостам перейти с острова
Адуака на остров Гауту?

27.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Построим граф.
Острова обозначим вершинами, мосты –
рёбрами.

28.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
В
Построим граф.
Острова обозначим вершинами, мосты –
рёбрами.

29.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
В

30.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
Д
В

31.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
Д
В

32.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
Г
Д
В
Е

33.

В архипелаге шесть островов и шесть мостов:
между островами Адуак и Бани, Адуак и Видо,
Бани и Видо, Екити и Гауту, Бани и Джеми,
Видо и Джеми. Можно ли по мостам перейти с
острова Адуака на остров Гауту?
Б
А
Г
Д
В
Е
Ответ: нет.

34.

35.

В деревне 9 домов. Известно, что
у Петра соседи Иван и Антон,
Максим сосед Ивану и Сергею,
Виктор – Диме и Никите, Евгений
– сосед Никиты, а больше
соседей в этой деревне нет
(соседними считаются дворы, у
которых есть общий участок
забора). Может ли Пётр
огородами пробраться к Никите
за яблоками?

36.

В деревне 9 домов. Известно, что у Петра соседи
Иван и Антон, Максим сосед Ивану и Сергею,
Виктор – Диме и Никите, Евгений – сосед Никиты, а
больше соседей в этой деревне нет (соседними
считаются дворы, у которых есть общий участок
забора). Может ли Пётр огородами пробраться к
Никите за яблоками?
Ответ: нет.