Решение задач с помощью граф

Графы

р

е

л

с

о

б

р

р

а

п

г

д

а

о

и

н

д

у

е

в

г

о

н

н

и

д

р

р

е

ы

е

т

а

в

й

и

р

ф

в

о

и

а

ш

е

н

р

к

н

История появления теории

Годом зарождения теории графов считается 1736-й, когда математик Леонард Эйлер опубликовал в Санкт-Петербургской Академии наук работу, посвящённую семи мостам города Кёнигсберга.

Мосты Кёнигсберга

В XVI веке в Кёнигсберге были построены

7 мостов, соединяющих разные части города.

Среди горожан известна загадка о том, как пройти по всем мостам лишь однажды.

Мосты Кёнигсберга

Для решения этой задачи Эйлер вводит понятие «графа» как множества непересекающихся рёбер или связей, соединяющих пары вершин.

Характеристики графа

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

Задание 1

Начертите граф , на котором были бы изображены высказывания:

«8 кратно 2»

«9 кратно 3»

«8 кратно 1»

«4 кратно 2»

«8 кратно 4»

«4 кратно 1»

«2 кратно 1»

Каждая стрелка графа должна обозначать «кратно».

9

3

4

8

2

1

«Социальные сети»

Задание 2

В социальной сети Дима дружит с Юрой, Толей, Аленой, Леной и Машей. Лена дружит с Машей, а Алена с Юрой. Профили всех ребят закрытые, т.е. просматривать сообщения друг у друга могут только друзья.

У кого из друзей на стене может оставить секретное послание Дима, не опасаясь, что об этом узнают остальные?

Могут ли девочки общаться, сохраняя свои секреты от ребят?

Задание 3

Между планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

• Земля – Меркурий;
• Плутон – Венера;
• Земля – Плутон;
• Плутон – Меркурий;
• Меркурий – Венера;
• Уран – Нептун;
• Нептун – Сатурн;
• Сатурн – Юпитер;
• Юпитер – Марс
• Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Задание 4

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

Задание 5

Между населёнными пунктами A, B, C, D, E построены дороги. Протяженность которых приведена в таблице:

Определите кратчайший путь между дорогами A и D .

1

2

3