Презентация: Графы и их применение при решении задач. Теория графов

познакомить учащихся с понятием “Граф”, основными принципами его построения;

формировать умение выделять отношения, связывающие объекты;

развивать внимание, способность к логическому рассуждению;

воспитывать взаимопомощь, умение работать в коллективе

закрепление полученных знаний на практике

развитие памяти, внимания;

развитие самостоятельности;

воспитание познавательной активности.

Оборудование:

• компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
• компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
• оборудование доски (тема урока, новые термины). Раздаточный материал.

План урока.

II. Изложение нового материала. (10 мин.)

III. Закрепление материала. Практическая работа. (15-20 мин.)

IV. Подведение итога урока.(2 мин)

V. Домашнее задание.

I. Организационный момент. Актуализация знаний.

Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.

II Изложение нового материала.

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)

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

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

Граф – это некоторая информационная модель

Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.

Примеры графов (Слайд 4, 5, 6)

Задание 1 (Слайд 7):

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

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

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

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

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

Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?

Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?

Представление графов (Слайд 12)

Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.

Списки дуг	Графическая форма	Табличная форма
(АВ; 7),		А В С А 3 В 4 С 3 4

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

Задание 2 (Слайд 13)

IV. Итог урока

Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)

Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

Что обозначают ребра графа (Пути, движения, направления)

Приведите пример, где в жизни мы можем с ними встретиться?

Как изображаются графы?

V. Домашнее задание. (Слайд 15)

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

Некоторые термины-1

- Пусть R=(a,b) – одно из ребер графа. Тогда
вершины a и b называются концевыми
вершинами ребра;
- Концевые вершины одного и того же ребра
называют соседними;
- Два ребра называют смежными, если они имеют
общую концевую вершину;
- Два ребра называются кратными, если
множества их концевых вершин совпадают;
- Ребро называется петлей, если его концы
совпадают.

Некоторые термины-2

- Степенью вершины V обозначается deg(V)
называется количество ребер, для
которых эта вершина является концевой;
- Вершина называется изолированной, если
она не является концевой ни для одного
ребра;
- Вершина называется листом, если она
является концевой ровно для одного
ребра. Для листа q очевидно deg(q)=1.

Пример:

deg(C)=4
H1,…H4 - Листья

Еще пример:

Города B и Д – изолированные
вершины; Города Г и Е – листья.

Полный граф

Граф называется полным, если любые
две вершины соединены ребром.
Сколько ребер у полного графа
порядка n?
У полного графа порядка n число ребер
равно Cn2=n!/(2*(n-2)!) =n*(n-1)/2

Давайте это докажем…

Полный граф с двумя вершинами
содержит одно ребро – это очевидно.
Подставим n=2 в формулу n*(n-1)/2
Получим:
n*(n-1)/2=1
Формула верна при n=2

Предположение индукции

Предположим, что формула верна для
графа c k вершинами.
Докажем, что отсюда следует
справедливость формулы для графа
c (k+1) вершиной.

Добавим к полному графу с K вершинами еще одну вершину.

И соединим ее с первыми K
вершинами…

Получим:

Считаем, сколько получилось ребер…

K*(K-1)/2 + K
=
K*(K+1)/2
Последнее выражение получается,
если в формулу n*(n-1)/2 вместо n
подставить K+1.

Из предположения справедливости
утверждения при n=k следует
справедливость утверждения при
n=k+1.
Теорема доказана.

Примеры полных графов

Важное уточнение

Пары, задающие ребра в неориентированном графе, неупорядочены (т.е.
пары (a,b) и (b,a) не различают-ся)

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

Если ребра графа есть множество
упорядоченных пар (т.е. (a,b) ≠ (b,a)),
То граф называется ориентированным
(или орграфом)
Как придать понятию ориентации
наглядный смысл?
Очень просто – ребра снабжаются
стрелками (от начала к концу)!

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

Смешанный граф

Смешанный граф – это тройка (V, E, A).
V – множество вершин;
E – множество неориентированных
ребер;
A- множество ориентированных ребер.
Кстати, ориентированные ребра
называются дугами.

Изоморфизм графов

Пусть имеется два графа G1 и G2
Если имеется взаимно-однозначное соответствие F
между вершинами графов G1 и G2 , такое что:
- если в графе G1 есть ребро (a,b), то и в графе G2
есть ребро (F(a),F(b))
- если в графе G2 есть ребро (p,q), то и в графе G1
есть ребро (F-1(p),F-1(q))
то графы G1 и G2 называются изоморфными, а
соответствие F – изоморфизмом.

Уточнение

Для орграфов и смешанных графов
соответствие F должно сохранять
ориентацию дуг.

Необходимое условия изоморфизма

При каких условиях между элементами
двух конечных множеств можно
установить взаимно-однозначное
соответствие?
Тогда и только тогда, число их
элементов одинаково.
Необходимым условием изоморфизма
графов является одинаковой число
вершин.

Достаточно ли это условие?

Нет, поскольку вершины могут быть
соединены по-разному.

Изоморфны ли эти графы?

Число вершин одинаково –
необходимое условие соблюдено…

Пробуем построить соответствие F…

Это – не изоморфизм: в G1 есть ребро (A,Д),
а образы этих ребер в G2 не соединены.

Другая попытка…

А это изоморфизм!

А эти графы изоморфны?

Увы, нет…

С точки зрения теории два
изоморфных графа – это один и тот
же объект (только, может быть, поразному изображенный…)

Пути (цепи):

Путь (цепь) это последовательность
вершин:
a1, a2, … , an
в которой соседние вершины ai и ai+1
соединены ребрами.
Длина пути есть число составляющих его
ребер

Примеры путей:

(А, Г, В) и (А, Б, Д) – пути. (А, Б, В) – не путь.

Понятие пути для орграфа сохраняет
силу, но нуждается в дополнении –
соседние вершины в
последовательности
a1, a2, … , an
должны соединяться дугами.

Циклы

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

Компоненты связности

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

Машинное представление графов.

Матрица смежности

- Занумеруем вершины графа G
последовательными целыми от 1 до n;
- Построим квадратную таблицу n×n и
заполним ее нулями;
- Если имеется ребро, соединяющее
вершины i и j, то в позициях (i,j) и (j,i)
поставим единицы;
- Полученная таблица называется
матрицей смежности графа G.

Пример

Некоторые очевидные свойства матрицы смежности

- Если вершина изолирована, то ее строка и
столбец будут полностью нулевые;
- Количество единиц в строке (столбце)
равно степени соответствующей
вершины;
- Для неориентированного графа матрица
смежности симметрична относительно
главной диагонали;
- Петле соответствует единица, стоящая на
главной диагонали.

Обобщение для орграфа

Матрицу смежности для орграфа
можно строить аналогичным
образом, но, чтобы учесть порядок
вершин, можно поступить так:
Если дуга исходит из вершины j и
входит в вершину k, то в позиции (j,k)
матрицы смежности ставить 1, а в
позиции (k,j) ставить -1.

Матрица инцидентности

- Занумеруем вершины графа G
последовательными целыми от 1 до
n;
- Построим прямоугольную таблицу с
n строками и m столбцами (столбцы
соответствуют ребрам графа);
- Если j-е ребро имеет концевой
вершиной вершину k, то в позиции
(k,j) ставится единица. Во всех
остальных случаях ставится нуль.

Матрица инцидентности для орграфа

- Если j-я дуга исходит из вершины k,
то в позиции (k,j) ставится 1;
- Если j-я дуга входит в вершину k, то
в позиции (k,j) ставится -1.
- В остальных случаях в позиции (k,j)
остается нуль.

Поскольку столбцы матрицы
инцидентности описывают ребра, то
в каждом столбце может быть не
более двух ненулевых элементов

Пример матрицы инцидентности

Список ребер

Еще один способ представления графа
– двумерный массив (список пар).
Количество пар равно числу ребер
(или дуг).

Пример списка ребер

Сравнение разных способов представления

- Список ребер самый компактный, а
матрица инцидентности наименее
компактна;
- Матрица инцидентности удобна при
поиске циклов;
- Матрица смежности проще
остальных в использовании.

Обход графа

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

Соглашение-1

Перед выполнением поиска для графа
с n вершинами заведем массив Chk
из n элементов и заполним его
нулями.
Если Chk[i] = 0, значит i-я вершина еще
не просмотрена.

Соглашение-2

Заведем структуру данных
(хранилище), в котором будем
запоминать вершины в процессе
обхода. Интерфейс хранилища
должен обеспечивать три функции:
- Занести вершину;
- Извлечь вершину;
- Проверить не пусто ли хранилище;

Соглашение-3

Когда вершина j помещается в
хранилище, она отмечается как
просмотренная (т.е. устанавливается
Chk[j]=1)

Алгоритм обхода-1

1) Берем произвольную начальную вершину,
печатаем и заносим ее в хранилище;

3) Берем вершину Z из хранилища;
4) Если есть вершина Q, связанная с Z и не
отмеченная, то возвращаем Z в хранилище,
заносим в хранилище Q, печатаем Q;
5) Переходим к п.2

Алгоритм обхода-2

1) Берем произвольную начальную вершину и
заносим ее в хранилище;
2) Хранилище пусто? Если ДА – конец;
3) Берем вершину Z из хранилища, печатаем и
удаляем из хранилища;
4) Помещаем в хранилище все вершины,
связанные с Z и еще не отмеченные;
5) Переходим к п.2

Какие структуры данных подходят в качестве хранилища?

- Стек (PUSH – занести; POP – извлечь)
- Очередь (ENQUE – занести; DEQUE –
извлечь)
Обе структуры позволяют проверить
наличие данных.

Алгоритм-1 в сочетании со стеком
называется обходом в глубину
Алгоритм-2 в сочетании с очередью
называется обходом в ширину

Слайд 2

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

Слайд 3

Виды (примеры) графов:

Обычный (неориентированный) граф 2 вершины могут быть соединены только одним ребром. Соединяющие линии называются ребрами. (смежные вершины – это 2 вершины, соединенные ребром)

Слайд 4

Ориентированный граф (орграф) - это граф, у которого на линиях, соединяющих вершины, указано направление (соединяющие линии называются дугами)

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 8

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

Слайд 9

Мультиграф 2 вершины соединены 2 ребрами и более (кратные ребра)

Слайд 10

Петля в графе (ребро соединяет вершину саму с собой)

Слайд 11

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

Слайд 12

СВОЙСТВА ГРАФОВ:

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

Слайд 13

1) Маршрут на графе – это последовательность ребер, в которой конец одного ребра служит началом следующего (циклический маршрут – если конец последнего ребра последовательности совпадает с началом 1-го ребра)2) Цепь – это маршрут, в котором каждое ребро содержится не более одного раза3) Цикл – это цепь, являющаяся циклическим маршрутом4) Простая цепь – это цепь, проходящая через каждую свою вершину ровно 1 раз5) Простой цикл – это цикл, являющийся простой цепью6) Связанные вершины – это вершины (например, А и B), для которых существует цепь, начинающаяся в А и заканчивающаяся в B7)Связный граф – это граф, у которого любые 2 вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом)Один и тот же граф может быть изображен по-разному.

Слайд 14

Пример 1

V={1,2,3,4,5,6,7,8,9,10}-это множество вершин графа. Для каждого из перечисленных ниже случаев изобразите граф и определите все степени вершин а) вершины x y соединены ребром тогда и только тогда, когда (x-y)/3 целое число б) вершины x y соединены ребром тогда и только тогда, когда x+y=9 в) вершины x y соединены ребром тогда и только тогда, когда x+y содержится в множестве V={1,2,3,4,5,6,7,8,9,10} г) вершины x y соединены ребром тогда и только тогда, когда |x-y|

1 слайд

2 слайд

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.

3 слайд

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

4 слайд

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе. Задача.

5 слайд

6 слайд

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

7 слайд

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами. Ориентированный граф

8 слайд

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. Таблице (она называется весовой матрицей) соответствует граф. 1 2 4 2 3 A B C D E

9 слайд

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

10 слайд

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2