Графы. Деревья Введение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов Граф (Л.Н.Толстой) Граф (не ориентированный) Граф (ориентированный)

Оглавление Графы и деревья в новых стандартах Исторические задачи на графах Граф. Основные понятия Ориентированный граф (орграф). Основные понятия Представление графа в памяти компьютера Основные задачи на графах просмотр графа в глубину просмотр графа в ширину

Извлечение из стандарта общего образования ОБЯЗАТЕЛЬНЫЙ МИНИМУМ СОДЕРЖАНИЯ … Обработка информации. Алгоритм, свойства алгоритмов. Способы записи алгоритмов; блок- схемы. Алгоритмические конструкции. Логические значения, операции, выражения. Разбиение задачи на подзадачи, вспомогательный алгоритм. Обрабатываемые объекты: цепочки символов, числа, списки, деревья, графы. Восприятие, запоминание и преобразование сигналов живыми организмами. …

Извлечение из стандарта среднего образования (профильный уровень) БАЗОВЫЕ ПОНЯТИЯ ИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ … Логика и алгоритмы. Высказывания, логические операции, кванторы, истинность высказывания. Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности. Индуктивное определение объектов. Вычислимые функции, полнота формализации понятия вычислимости, универсальная вычислимая функция; диагональное доказательство несуществования. Выигрышные стратегии. Сложность вычисления; проблема перебора. Задание вычислимой функции системой уравнений. Сложность описания. Кодирование с исправлением ошибок. Сортировка. …

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

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

Задача о четырех красках Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок.

В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контр примеров к теореме о четырех красках и показать, что ни один случай контр примером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Граф. Основные понятия Определение. Определение. Графом G(V,E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E – множество ребер). Диаграмма графа Вершины графа (v i ) – 1, 2, 3, 4, 5, …, 14, 15, 16 Ребра графа (e i ) – 1-2, 1-10, 1-14, 2-16, 3-4, 3-16, …,

Граф. Основные понятия Определение. Определение. Последовательность ребер (v 0, v 1 ), (v 1, v 2 ),..., (v i -1, v i ), (v i, v i +1 ),..., (v r -1, vr) называется маршрутом, соединяющим вершины v 0 и v r. Маршрут замкнут, если v 0 = v r. Определение. Определение. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны. Определение. Определение. Замкнутая (простая) цепь называется (простым) циклом. Определение. Определение. Граф называется связным, если любая пара его вершин соединена маршрутом.

Граф. Основные понятия Определение. Определение. Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины v i и v j в графе G, называется расстоянием d (v i, v j ) между v i и v j. В связном неориентированном графе расстояние удовлетворяет аксиомам метрики. Определение. Определение. Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз. Определение. Определение. Связный граф с n вершинами и n-1 ребром называется деревом.

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

Ориентированный граф. Основные понятия Определение. Определение. Ориентированным графом (орграфом) G(V,E) называется совокупность непустого множества V (множества узлов) и множества E упорядоченных пар элементов (вершин) V (E – множество дуг). Диаграмма орграфа Вершины орграфа (v i ) – 1, 2, 3, 4, 5, 6, 7, 8 Ребра орграфа (e i ) – 1-5, 5-1, 5-3, 5-4, 6-5, 7-6,

Хранение графа в памяти в виде матрицы смежности a(i,j)=1, если вершины i и j соединены ребром a(i,j)=0, если вершины i и j не соединены ребром a(i,i)=0 по определению

Хранение графа в памяти в виде массива дуг Номер ребра

Хранение графа в памяти в списка смежности Вершина Длина списка Список 142, 10, 13, , , , , , , , , 9, , 14

Задача В одном районе имеется n деревень. Некоторые из них соединены дорогами. Составьте алгоритм, который определяет можно ли проехать по дорогам из деревни номер i до деревни с номером j

Просмотр графа в глубину (стек)

Математическая модель Аргументы n – число деревень, целое k – число дорог, целое a(n, n) – матрица смежности x – номер первой деревни y – номер второй деревни Результаты t – ответ, строковая величина или константа Промежуточные величины f(n) – таблицы флагов посещения деревень, целые, f(i)=0, если деревня еще не посещена, f(i)=0, если деревня посещена s(n) – стек для хранения маршрута, us – указатель стека, целые i – счетчик цикла, целое

Ввод данных Число деревень? n Начало Какие деревни интересуют? x,y f(x)=1 us=1 s(us)=x s(us+1)=0 1 Число дорог? k i=1,k Деревни, соединенные I-той дорогой x,y a(x,y)=1 a(y,x)=1 1 2

Поиск маршрута s(us+1)=s(us+1)+1 2 f(y)=0 и us>0 да s(us+1)>n да нет f(s(us+1))=0 и a(s(us),s(us+1))=1 да us=us+1 f(s(us))=1 s(us+1)=0 us=us-1 3 нет

Печать ответа f(y)=1 да 3 нет Проехать можно. Маршрут: Проехать нельзя i=1,us s(i) Конец

Просмотр графа в ширину (очередь)

Математическая модель Аргументы n – число деревень, целое k – число дорог, целое a(n, n) – матрица смежности x – номер первой деревни y – номер второй деревни Результаты t – ответ, строковая величина или константа Промежуточные величины f(n) – таблицы флагов посещения деревень, целые, f(i)=0, если деревня еще не посещена, f(i)=0, если деревня посещена s(n) – очередь для хранения маршрута, no – указатель начала очереди, ko – указатель конца очереди, целые i – счетчик цикла, целое

Ввод данных Число деревень? n Начало Какие деревни интересуют? x,y no=1 ko=1 s(ko)=x 1 Число дорог? k i=1,k Деревни, соединенные I-той дорогой x,y a(x,y)=1 a(y,x)=1 1 2

Поиск маршрута 2 f(y)=0 и no<=ko да 3 нет i=1,n f(i)=0 и a(s(no),i)=1 да ko=ko+1 s(ko)=i нет no=no+1

Печать ответа f(y)=1 да 3 нет Проехать можно. Проехать нельзя Конец

И это еще не все, но... КОНЕЦКОНЕЦ