Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
9 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
84.06 kB
Просмотров:
71
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Введение в теорию графов.](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img0.jpg)
Содержание слайда: Введение в теорию графов.
Способы представления ориентированных и неориентированных графов
Лекция 22
№2 слайд![Основные понятия и](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img1.jpg)
Содержание слайда: Основные понятия и определения
Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Будем также использовать обозначения |V| = n и |Е| = m.
Если пара вершин неупорядочена, то ее принято называть ребром. Если упорядочена – дугой.
Граф, состоящий только из ребер называется неориентированным графом. Граф, содержащий только дуги - ориентированным графом или орграфом.
Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами. Если вершины соединены дугой (x,y), то вершина x смежна вершине y, а обратной смежности нет.
№3 слайд![Два ребра называют смежными](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img2.jpg)
Содержание слайда: Два ребра называют смежными ребрами, если они имеют общую вершину.
Два ребра называют смежными ребрами, если они имеют общую вершину.
Ребро и любая из двух его вершин называются инцидентными.
Любому ребру или вершине графа может быть присвоен вес, такой граф называется взвешенным.
Вес вершины – число, которое характеризует вершину, вес ребра – число, характеризующее отношение между двумя вершинами.
Например, для графа автомобильных дорог вес ребра может означать длину дороги от одного города до другого.
Граф называется связным, если между любой парой вершин графа существует как минимум один путь.
№4 слайд![Способы представления графа в](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img3.jpg)
Содержание слайда: Способы представления графа в памяти
Матрица инцидентности
Матрица смежности
Список пар вершин, соответствующих ребрам графа
Списки инцидентности
№5 слайд![В теории графов классическим](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img4.jpg)
Содержание слайда: В теории графов классическим способом представления графа служит матрица инцидентности.
В теории графов классическим способом представления графа служит матрица инцидентности.
Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x,y) содержит 1 в строке, соответствующей вершине х, -1 в строке, соответствующей вершине у, и нули во всех остальных строках. В случае неориентированного графа столбец, соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и нули в остальных строках.
Этот способ один из самых худших способов представления графов с алгоритмической точки зрения. Он требует n*m ячеек памяти, причем большинство этих ячеек занято нулями. Неудобен также доступ к информации.
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».
№6 слайд![Лучшим способом представления](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img5.jpg)
Содержание слайда: Лучшим способом представления графа является матрица смежности, определяемая как матрица В = [bij] размера nхn, где bij =1, если существует ребро, идущее из вершины х в вершину у, bij =0 в противном случае. Если граф взвешенный, то вместо 1 в матрице ставится вес ребра, идущего из вершины i в вершину j.
Лучшим способом представления графа является матрица смежности, определяемая как матрица В = [bij] размера nхn, где bij =1, если существует ребро, идущее из вершины х в вершину у, bij =0 в противном случае. Если граф взвешенный, то вместо 1 в матрице ставится вес ребра, идущего из вершины i в вершину j.
Здесь мы подразумеваем, что ребро {х,у} неориентированного графа идет как от х к у, так и от у к х, так что матрица смежности такого графа всегда является симметричной.
Недостатком является тот факт, что независимо от числа ребер объем занятой памяти составляет n2.
Этот способ хорош, когда нам надо проверять смежность или находить вес ребра по двум заданным вершинам.
№7 слайд![Более экономным в отношении](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img6.jpg)
Содержание слайда: Более экономным в отношении памяти (особенно в случае, неплотных графов, когда m гораздо меньше n2) является метод представления графа с помощью списка пар, соответствующих его ребрам.
Более экономным в отношении памяти (особенно в случае, неплотных графов, когда m гораздо меньше n2) является метод представления графа с помощью списка пар, соответствующих его ребрам.
Пара соответствует дуге <х,у>, если граф ориентированный, и ребру {х,y} в случае неориентированного графа. Очевидно, что объем памяти в этом случае составляет 2m.
Неудобством является большое число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.
№8 слайд![Ситуацию можно значительно](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img7.jpg)
Содержание слайда: Ситуацию можно значительно улучшить, упорядочив множество пар лексикографически и применяя двоичный поиск, но лучшим решением во многих случаях оказывается структура данных, которая называется списками инцидентности.
Ситуацию можно значительно улучшить, упорядочив множество пар лексикографически и применяя двоичный поиск, но лучшим решением во многих случаях оказывается структура данных, которая называется списками инцидентности.
Она содержит для каждой вершины v список вершин u, таких, что v смежно с u. Каждый элемент такого списка является записью, содержащей вершину и указатель на следующую запись в списке.
№9 слайд![Домашнее задание . Составить](/documents_6/a7df59aad3a9b083adf177b8f4a24d69/img8.jpg)
Содержание слайда: Домашнее задание
1. Составить опорный конспект лекции по теме «Введение в теорию графов.Способы представления ориентированных и неориентированных графов» на основе презентации.
2. Комбинаторика для программистов. Липский В. М.: «Мир», 1988, стр. 79-83.