Уроки по теме "Графы", "Обход графов"

Практикум

1. Проанализируйте все способы задания графа(1-2 человека на способ, объясните товарищам особенность такого задания)

2. Выполните практические задачи

Обычно граф задают одним из двух способов: перечислением всех его ребер или таблицей, где в клетке на пересечении строки и столбца, соответствующих данным вершинам, указано, соединены эти вершины ребром или нет. Такая таблица называется таблицей смежности. Если граф нагруженный, то для каждого ребра в соответствующей клетке указывается нагрузка.
Ниже для нагруженного графа, изображенного на рис., приведены его задания списком ребер и таблицей смежности.

Список ребер: (AA; 2), (AB; 3), (AC; 6), (BC; 2), (AD; 4), (BD; 3), (CD; 5).

Список ребер для нагруженного графа будем задавать как двумерный массив A[1 : n, 1 : 3], где в первой строке соответствующей этому массиву таблице указывается один конец ребра, во второй — другой его конец, а в третьей — величина нагрузки (здесь n — число ребер в графе). Для ненагруженного графа соответствующий массив содержит только первые две строки. Если граф задается таблицей смежности, то договоримся считать значение первого индекса номером первой вершины, а второго индекса — номером второй вершины; сами номера вершин в массиве не присутствуют. В частности, для графа на рис. 5 при естественной нумерации вершин A — 1, B — 2, C — 3 и D — 4 список ребер в силу нашей договоренности задается массивом, который можно изобразить табл. 3.2, а таблица смежности выглядит так, как показано в табл. 3.3.

Решение задач

1. Существует ли граф с заданным набором степеней вершин? При ответе “Да” надо предъявить соответствующий граф, ответ “Нет” надо обосновать.

   1. 1,1,2,2,2,4

   2. 1,2,2,3,3,4

   3. 2,2,3,3,4,4

2. Для построенного графа из задания 1 привести все 4 способа описания(задания) графа.

3. Найдите, сколько существует разных графов с 4 вершинами.

4. Докажите, что в дереве любые две вершины соединены ровно одним простым путем.

5. В стране Древляндия 101 город, некоторые из них соединены дорогами, при этом любые два города соединяет ровно 1 путь. Сколько в этой стране дорог?

6. Дима нарисовал на доске 7 графов, каждый из которых является деревом с 6 вершинами. Докажите, что среди них есть два одинаковых.
   
   

Тема: «Графы. Методы поиска на графах».

Цели урока:

• Обучающая:

1. освоение принципов обхода графов, составление алгоритмов обхода

2. отработка навыков работы с графами

• Развивающая:

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

2. Способствовать развитию творческих навыков

• Воспитывающая:

1.Создание рабочей обстановки.

2.Воспитание активности и самостоятельности.

Оборудование: раздаточный материал, листы с домашним заданием.

План урока:
I. Орг. момент. (1 мин)
II. Актуализация знаний. (6 мин)
III. Групповая работа -1 часть. (12 мин)
IV. Групповая работа -2 часть. (23 мин)
V. Д/з (1 мин)
VI. Итог урока. (2 мин)

Ход урока:
I. Организационный момент
Приветствие, проверка присутствующих, настрой на работу. Объяснение хода урока.

II. Актуализация знаний
Повторение, опрос: 1) фронтально основные определения, 2) каждый на листе рисует нагруженный граф, рядом с каждой вершиной (в кружке) записывает ее степень. Передаем соседу, который проверяет, ставит знак +/- и, в свою очередь, записывает для этого графа 2-3 способа задания.

III. Групповая работа -1 часть

1. Разбейтесь на группы. Для каждой группы задание- изобразить три графа. Можете разделиться для выполнения задания( на отдельных листах) и потом – взаимопроверка.

2. Вам предлагается разобрать один из методов обхода графа ( мы с вами разберем два метода поиска пути в графе- в ширину и в глубину).
   
   

1. Групповая работа -2 часть

   1. Теперь половина одной группы меняется местами с половиной ребят другой группы. Задача каждой подгруппы – объяснить, показать свой изученный способ поиска.

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

   3. Если вы все быстро успели – думаем над составлением алгоритма поиска на графе( это будет потом ваше домашнее задание).
      
      

1. Д/з решить задачи(на листе заданий).
   
   

2. Итоги урока
   Подведение итогов урока. Выставление оценок.

Тема: «Графы».

Цели урока:

• Обучающая:

1. изучение основных терминов теории графов

2. отработка навыков построения графов

• Развивающая:

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

2. Способствовать развитию творческих навыков

• Воспитывающая:

1.Создание рабочей обстановки.

2.Воспитание активности и самостоятельности.

Оборудование: мультимедийный проектор, раздаточный материал, листы с домашним заданием.

План урока:
I. Орг. момент. (1 мин)
II. Актуализация знаний. (2 мин)
III. Теоретическая часть. (20 мин)
IV. Практическая часть. (15 мин)
V. Вопросы учеников. (3 мин)
VI. Д/з (2 мин)
VII. Итог урока. (2 мин)

Ход урока:
I. Организационный момент
Приветствие, проверка присутствующих, настрой на работу. Объяснение хода урока.

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

III. Теоретическая часть
Изучение нового материала: Лекция с показом на проекторе.

(2-5 слайд) Теория графов — одна из тех немногих математических теорий, для которых точно известен ее создатель, время и место создания: Леонард Эйлер, 1736 г.,
г. Петербург. Именно в этом году Л.Эйлером в “Записках Петербургской академии наук” была опубликована статья, в которой приводилось решение широко теперь известной задачи о Кёнигсбергских мостах. Разумеется, работа Л.Эйлера содержала не только отрицательный ответ на вопрос о возможности обойти все семь мостов г. Кёнигсберга так, чтобы по каждому из них пройти ровно один раз. В ней великий математик сформулировал и обосновал критерий, позволяющий отвечать на данный вопрос для любого графа.

Однако эта статья была единственной в течение почти столетия. Лишь в середине XIX века возродился интерес к теории графов. Исследование электрических сетей, структур молекул и строения кристаллов, применения к решению проблем в биологии и психологии послужили мощным катализатором в становлении данного раздела математики. Графы оказались удобным средством для описания самых разнообразных систем и явились эффективным инструментом структурного анализа. Графы успешно применяются для решения разнообразных задач планирования — выбор оптимального маршрута (транспортная задача), построение сетевого графика, исследование потоков в сетях и т.п. Одной из самых знаменитых задач, которая вызвала фейерверк остроумных работ в области теории графов, была предложенная де Морганом (около 1850 г.) проблема четырех красок: верно ли, что для раскраски любой карты так, чтобы граничащие между собой страны были раскрашены в разные цвета, достаточно четырех красок?
Теорема (о пяти красках)

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

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

Теорема (о четырех красках)

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

(6слайд) Применяется теория графов во многих науках. Многие физики, например, независимо друг от друга много раз открывали элементы теории графов заново.

Приведем ряд примеров приложений теории графов.

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

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

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

•  Управление проектами. С точки зрения теории графов проект - совокупность операций и зависимостей между ними.

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

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

(7слайд) Итак, что же такое граф?

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

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

Теорема 1. Сумма степеней всех вершин графа равна удвоенному числу его ребер.

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

Теорема 2. Количество вершин нечетной степени любого графа всегда четно.

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

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

Доказательство. Пусть в графе n вершин. Ясно, что степень каждой вершины может иметь значение от 0 до n – 1. Если степени всех вершин различны, то каждое из указанных значений должно реализоваться ровно для одной вершины. Рассмотрим вершины степени 0 и степени n – 1. Степень 0 означает, что эта вершина не соединена ни с какой другой; степень n – 1 означает, что эта вершина соединена со всеми другими вершинами. Но одновременно так быть не может.

Маршрутом на графе называется последовательность ребер е1, е2, …, еk, в которой конец одного ребра служит началом следующего. Если при этом конец последнего ребра последовательности совпал с началом первого ребра, то маршрут называется циклическим.

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

Вершины А и В называют связанными, если существует цепь, начинающаяся в вершине А и заканчивающаяся в вершине В.

В теории графов деревом называется связный граф без циклов.

Дерево, как правило, изображают некоторым стандартным образом. Для этого фиксируют одну из вершин, ее называют корнем. Корень изображают внизу, а все остальные вершины распределяют по уровням. На первом уровне размещаются вершины, смежные с корнем, на втором — смежные с вершинами первого уровня, отличные от корня, на третьем — смежные с вершинами второго уровня, отличные от вершин первого уровня, и т.д.

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

Иногда бывает удобно рассматривать ненагруженный граф как нагруженный, у которого каждому ребру поставлено в соответствие число 1.

1. Практическая часть

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

1. Вопросы учеников
   Ответы на вопросы учащихся.

1. Д/з Выучить определения по тетради(справочным материалам), решить задачи(на листе заданий).

1. Итоги урока
   Подведение итогов урока. Выставление оценок.

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

1. Группа туристов хочет попасть из деревни А в деревню В. (см. рисунок; рядом с каждой дорогой указано время, которое тратится на ее прохождение.) За какое наименьшее время это возможно?

1. В выходной день Миша решил навестить своих друзей: Алешу, Борю, Витю, Гену, Диму, Женю, Колю, Славу. Он начертил схему взаимного расположения домов, где живут мальчики, и дорог, соединяющих их. Посетил он их в следующем порядке: Алеша, Боря, Витя, Гена, Дима, Женя, Коля, Слава. Установите, какой дом кому принадлежит, если ни к одному из домов Миша не подходил более одного раза, Известно, что Миша живет в доме М, последним он посетил дом R.

3.* Составить алгоритм поиска «в глубину».

4.* Составить алгоритм поиска «в ширину».

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

1. Существует ли граф с пятью вершинами и следующим набором степеней вершин а) 0, 1, 2, 3, 4; б) 1, 1, 2, 3, 4; в) 1, 1, 2, 2, 4; г) 1, 1, 2, 3, 3 ? При ответе “Да” надо предъявить соответствующий граф, ответ “Нет” надо обосновать.
   
   

2. Какое наибольшее число ребер может содержать граф, имеющий n вершин?
   
   
   

3. Наша шпионская сеть была хорошо законспирирована, — признался на допросе агент 007. — В ней было 77 агентов, но каждый знал только семерых. Почему наверняка можно утверждать, что агент лжет?

1. Выясните, одинаковы ли графы, изображенные на рис. а; на рис. б, в.

1. На конгрессе собрались ученые, среди которых есть друзья. Оказалось, что никакие двое ученых, имеющих равное число друзей, не имеют общих друзей. Доказать, что найдется ученый, который имеет ровно одного друга.

1 вариант

Поиск в глубину

Идея алгоритма такова. Пусть зафиксирована начальная вершина v0. Выберем смежную с ней вершину v1. Затем для v1 поступаем так же: выбираем смежную с ней вершину из числа еще невыбранных вершин. И так далее: если мы уже выбрали вершины v0, v1, …, vk, то следующая вершина выбирается смежной с vk из числа невыбранных. Если для вершины vk такой вершины не нашлось, то возвращаемся к вершине vk – 1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся еще на шаг назад и т.д. Ясно, что так будут перебраны все вершины графа, и поиск закончится. На рис. показаны две реализации поиска в глубину для одного и того же графа (при одинаковом выборе начальной вершины): около каждой вершины написан присвоенный ей порядковый номер при исполнении поиска в глубину. Свое название этот метод получил за то, что при его реализации мы стремимся как можно дальше уйти от исходной вершины, а когда идти уже некуда, возвращаемся в ту вершину, откуда идет хотя бы одно ребро в непройденные еще вершины.

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

Задача: выполните поиск в ширину для графов, заданных таблицами 3.4-3.6.

2 вариант

Поиск в ширину

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

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

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

Будем считать, что граф задан таблицей смежности. Кроме того, организуем одномерный массив В, число элементов в котором совпадает с числом вершин в графе. На k-м месте этого массива будем писать номер вершины, в которую мы попали на k-м шаге. С третьим вопросом поступим так: из всех смежных непройденных вершин будем выбирать вершину с наименьшим номером. Чтобы хранить список вершин, необходима структура данных «очередь».

Задача: выполните поиск в глубину для графов, заданных таблицами 3.4-3.6.

Схема метрополитена

Классификация

Структура молекулы

Теория графов

• Леонард Эйлер, 1736 г.,г. Петербург, решение задачи о Кёнигсбергских мостах.
• де Морган(около 1850 г.) работа по проблеме четырех красок
• Изучение электрических цепей Кирхгофом 1847 г.
• Решение задач органической химии Кэли 1857 г.
• Решение головоломок Гамильтоном 1859 г.

Задача о Кенигсбергских мостах

План мостов

Соответствующий граф

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

Задача о трех домах и трех колодцах

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

Задача о четырех красках

Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. Гипотеза: для этого достаточно четырех красок.

В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию. Суть решения - перебрать большое (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера.

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

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

Граф  — это совокупность непустого множества вершин и множества ребер (пар связанных вершин).

Элементы графа:

• вершины , или узлы графа, связи — дуги , или рёбра .
• вершины , или узлы графа,
• связи — дуги , или рёбра .

Степень вершины v ( а )

v ( а )=4

Теорема 1 . Сумма степеней всех вершин графа равна удвоенному числу его ребер.

Теорема 2 . Количество вершин нечетной степени любого графа всегда четно.

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

а2

а1

а6

а7

а9

а5

а10

а3

а8

а4

Маршрут - последовательность ребер в которой конец одного ребра служит началом следующего.

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

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

Дерево

Нагруженный граф

1

5

6

7

5

7

5

3

2

2

Способы описания графа

• матрица инциденций;
• матрица смежности;
• списки связи;
• перечни ребер.