Графы

Кенигсбергские мосты К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города. Задача : нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут. Термин « граф » впервые ввел в 1936 г. венгерский математик Д. Кениг, хотя задачи по теории графов решал еще Л.Эйлер в XVIII веке. Из истории теории графов

–множество вершин V и набор E неупорядоченных и упорядоченных пар вершин. Граф - G(V, E)

Ребро – это неупорядоченная пара вершин. Дуга – это упорядоченная пара вершин. Неориентированный граф Ориентированный (орграф)

Вершины, соединенные ребром или дугой, называются смежными. Ребра, имеющие общую вершину, тоже называются смежными.

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

М атрица смежности П еречень списков смежных вершин Представление графа в памяти ЭВМ

1, если вершины i, j смежные A[i,j] = 0, если вершины i, j несмежные – это двумерный массив А размерностью N N, где N – количество вершин графа. Матрица смежности

– это N списков, каждый из которых содержит номера всех смежных вершин. Перечень списков смежных вершин Указатели на первые элементы списков объединены в массив.

Пример nil Матрица смежности Списки смежных вершин nil

Алгоритмы поиска в графе

Начиная с первой вершины идем «вглубь», пока это возможно. Выбирается вершина, смежная с предыдущей, и процесс повторяется. Если на очередном шаге оказалось, что нет непросмотренных вершин, связанных с текущей, то выполняется возврат к предыдущей и ищется новая вершина, связанная с ней, и так до тех пор, пока не вернемся к начальной вершине. Поиск в глубину (1) (2) (3) (4) (5) Очередность просмотра вершин

Начиная с начальной вершины проверяются все вершины, смежные с данной. Их номера заносятся в очередь. Далее процесс продолжается с первой из вершин, записанной в очереди. И до тех пор, пока очередь не окажется пустой. Поиск в ширину (1) (2) (4) (3) (5) Очередность просмотра вершин

Задание nil

Очередность обхода графа при поиске в глубину (1) (2) (3) (4) (5) (6)

Очередность обхода графа при поиске в ширину (1) (2) (5) (3) (6) (4)

Деревья

– это связный граф без циклов. (В нем нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину) Дерево Корень Узлы Листья ? ?

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

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

= m – n +1, где m – количество ребер, n – количество вершин показывающего, сколько ребер графа нужно удалить, чтобы в нем не осталось ни одного цикла. Преобразование графа в остовное связное дерево с помощью цикломатического числа,

= ? = 5 – 5 + 1=

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

2.Ребра последовательно по возрастанию их весов включаются в остовное дерево. 3.Алгоритм заканчивается, когда все вершины будут объединены в одно связное множество, оставшиеся ребра не включаются в остовное дерево

Примеры неориентированных графов ГрафВершиныРебра СемьяЛюдиРодственные связи ГородПерекресткиУлицы СетьКомпьютерыКабели ДоминоКостяшкиВозможность ДомКвартирыСоседство ЛабиринтРазвилки и тупики Переходы МетроСтанцииПересадки Листок в клеточку КлеточкиНаличие общей границы

Примеры ориентированных графов ОрграфВершиныДуги ЧайнвордСловаСовпадение последней и первой букв (возможность связать два слова в цепочку) СтройкаРаботыНеобходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.) ОбучениеКурсыНеобходимое предшествование (например, курс по языку Pascal полезно изучить прежде, чем курс по Delphi, и т.п.) Одевание ребенка Предметы гардероба Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.) Европейский город ПерекресткиУзкие улицы с односторонним движением ОрганизацияСотрудникиИерархия (начальник - подчиненный)

Примеры взвешенных графов ГрафВершины Вес вершины Ребра (дуги) Вес ребра (дуги) Тамож ни ГосударстваПлощадь территории Наличие наземной границы Стоимость получения визы Переез ды ГородаСтоимость ночевки в гостинице ДорогиДлина дороги Супер- чайнво рд Слова-Совпадение конца и начала слов(возможность "сцепить" слова) Длина пересекающих ся частей КартаГосударстваЦвет на картеНаличие общей границы - СетьКомпьютеры-Сетевой кабельСтоимость кабеля

Примеры деревьев ДеревоВершиныРебра (дуги) АрмияСолдаты и офицеры Иерархия (командир - подчиненный) Династия (родословная по мужской линии) МонархиОтношение "отец - сын"