Презентация по теме: "Графы"

Графы.

Решение логических задач с помощью графов.

Основные понятия

Графы  – это рисунки, которые состоят из точек и линий, соединяющих эти точки.

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

Основные понятия

Точки называются  вершинами графа , а линиями  рёбрами .

Ребро  может иметь направление, которое указывается стрелочкой.

У графа обязательно есть  вершины .

Граф без рёбер называется  пустым .

Основные понятия

Направленная линия (со стрелкой) называется дуга .

Линия ненаправленная (без стрелки) называется ребро .

Линия, выходящая из некоторой вершины и входящая в неё же, называется петля .

ребро

А

дуга

петля

В

С

А,В,С – вершины графа

Основные понятия

Степень вершины графа - это количество ребер, выходящих из данной вершины

A

Степень A – 1

Степень B – 3

B

C

Степень C – 2

Степень D – 2

D

Основные понятия

Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2.

A

C

D

(1+3+2+3+2+1):2=6

B

E

F

Какие бывают графы?

Неориентированный граф

Неориентированный граф - граф, вершины которого соединены ребрами.

С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.

Юра

Аня

Маша

Витя

Коля

Граф, отражающий отношение «переписываются» между объектами класса «дети»

Какие бывают графы?

Ориентированный граф (орграф)

Ориентированный граф - граф, вершины которого соединены дугами.

С помощью таких графов могут быть представлены схемы односторонних отношений.

Юра

Аня

Маша

Витя

Коля

Граф, отражающий отношение «пишет письма».

Какие бывают графы?

Взвешенный граф

Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

182

127

158

Владимир, 1108

Москва, 1147

Переславль Залесский, 1152

Какие бывают графы?

Связные и несвязные графы

Связный граф можно нарисовать не отрывая карандаша от бумаги

Какие бывают графы?

Полный граф

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

Если полный граф имеет n вершин , то количество ребер будет равно

Типы моделей на графах

• Иерархия (дерево). Принцип связи – «один ко многим».
• Сеть. Принцип связи – «многие ко многим».

Информационные модели на графах

Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.

Директор

Заместители директора

Учителя

Ученики

Отношения подчиненности в школе

Информационные модели на графах

Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

компьютер

суперкомпьютер

рабочая станция

персональный компьютер

настольный

портативный

карманный

Классификация компьютеров

Информационные модели на графах

Корень – главная вершина дерева.

Предок – объект верхнего уровня.

Потомок – объект нижнего уровня.

Листья – вершины, не имеющие потомков.

Чемпион

Финалисты

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Олимпийская система спортивных соревнований

Сеть

Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза.

Цикл – цепь, начальная и конечная вершины которой совпадают.

Граф с циклом называют сетью

Юра

Аня

Маша

Витя

Коля

Семантическая сеть

Иван-Царевич

указала

Баба Яга

пустил

Стрела

сжёг

нашёл

Лягушачья кожа

прилетела

Лягушка

сбросила

нашёл

победил

превратилась

Лебедь

Василиса Прекрасная

превратилась

улетела

Кощей Бессмертный

Домашнее задание:

Построить граф, отражающий семейное дерево ученика.

Решение логических задач с помощью графов.

Основоположники теории графов.

Л. Эйлер (1707-1782),

Г. Кирхгоф (1824-1871),

российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук)

иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев)

17

Проблема Кёнигсбергских мостов

В 1736 году Эйлер нашел решение головоломки, носящей название «проблема Кёнигсбергских мостов».

17

Задача Эйлера

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

В XVIII веке город Кенигсберг (сейчас Калининград ) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами.

Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

Задача Эйлера

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

Задача Эйлера

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

Задача Эйлера

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

достаточно выполнения следующих двух условий:

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

2. из каждой вершины должно выходить чётное количество рёбер.

Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой.

Решение задачи о Кёнигсбергских мостах

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

Графы в современном мире

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

В государстве 100 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

№ 1

Решение:

Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 .

(100 ∙ 4) : 2 = 200 .

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

№ 2

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Решение:

Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 .

Нет, не может, так как

если X- число городов

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

№ 3

Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).

Сколько всего рукопожатий было сделано?

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

Решение:

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

Количество ребер полного графа

(5 ∙ 4) : 2=10.

Значит, было сделано 10 рукопожатий

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

№ 4

• Алексей, Борис, Виталий и Геннадий – друзья.
• Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель.
• Журналист написал статьи об Алексее и Геннадие.
• Тренер и журналист вместе с Борисом ходили в поход.
• Алексей и Борис были на приеме у врача.
• У кого какая профессия?

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

Алексей, Борис, Виталий и Геннадий – друзья.

Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель.

Журналист написал статьи об Алексее и Геннадии.

Тренер и журналист вместе с Борисом ходили в поход.

Алексей и Борис были на приеме у врача.

У кого какая профессия?

Алексей

строитель

тренер

Борис

журналист

Виталий

Геннадий

врач

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

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

Я задумал число. Если к нему прибавить 24,

потом полученную сумму умножить на 9, затем

из произведения вычесть 76 и, наконец, полученную

разность разделить на 19, то получится число 23.

Найти задуманное число.

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

Если задуманное число умножить на 5 и к результату прибавить 1, потом сумму увеличить в 6 раз и к результату прибавить 2, затем новую сумму умножить на 7 и полученное произведение увеличить на 4, то получим число, которое в 16 раз больше числа 135. Найдите это число.

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

Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II – половину остатка и еще 1 яблоко, III – половину нового остатка и еще 1 яблоко и т.д. Последнему – шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница?

Домашнее задание:

На вопрос путника: «Сколько у тебя в стаде голов скота?» - пастух ответил: «Если бы к моему стаду добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козленок». Сколько голов скота было в стаде?