'

Графы

Понравилась презентация – покажи это...





Слайд 0

Графы


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

– это двумерный массив А размерностью N ? N, где N – количество вершин графа. Матрица смежности


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

Задание


Слайд 14

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


Слайд 15

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


Слайд 16

Деревья


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

? = ? ? = 5 – 5 + 1= 1


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

Примеры взвешенных графов


Слайд 27

Примеры деревьев


×

HTML:





Ссылка: