Теория графов Теория графов – обширный самостоятельный раздел дискретной математики




НазваниеТеория графов Теория графов – обширный самостоятельный раздел дискретной математики
Дата конвертации30.01.2013
Размер445 b.
ТипПрезентации


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


Теория графов – обширный самостоятельный раздел дискретной математики.

  • Теория графов – обширный самостоятельный раздел дискретной математики.

  • Используется при проектировании компьютерных сетей, трубопроводов, строительстве дорог для минимизации затрат на прокладку коммуникаций.



Граф

  • это конечное множество вершин V и множество ребер R, соединяющих пары вершин, G=(V,R).

  • Мощности множеств V и R равны N и M.

  • Множество ребер может быть пустым.

  • Примеры вершин – объекты любой природы (населенные пункты, компьютерные сети).

  • Примеры ребер – дороги, стороны, линии.



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

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

  • Ребро и любая из его двух вершин называются инцидентными.

  • Степень вершины – количество инцидентных ей ребер.

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



  • Ориентированный граф Неориентированный граф

  • В орграфе ребро называют дугой.



Маршрут графа – последовательность вершин и ребер.

  • Маршрут графа – последовательность вершин и ребер.

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

  • Маршрут – простая цепь, если все вершины и ребра различны.

  • Граф связный, если каждая вершина достижима из любой другой.

  • Вершины, не имеющие инцидентных ребер, называются изолированными.



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

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

  • Вес сети равен сумме весов ее ребер.



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

  • матрица инциденций,

  • матрица смежности,

  • списки связи,

  • перечни ребер.



Матрица инциденций

  • N – количество вершин

  • M – количество ребер

  • Матрица инциденций – это двумерный массив размерности N×M



Матрица инциденций



Матрица смежности

  • – это двумерный массив N*N.



Матрица смежности графа



Матрица смежности сети (с учетом весов ребер)



Списки связи

  • Задание графа списками связи осуществляется с помощью одномерного массива размерности N для хранения указателей.

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



Списки связи



Перечень ребер

  • Для хранения перечня ребер необходим двумерный массив размерности M×2.

  • Строка массива описывает ребро.



Перечень ребер



Подграфы и деревья

  • Подграф графа G называют граф, у которого все вершины и ребра принадлежат графу G.

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



Подграфы и деревья

  • Дерево – это граф, в котором нет циклов.

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



Преобразование графа в остовное связное дерево минимального веса

  • Пусть G=(V,R) – связанный взвешенный неориентированный граф.

  • Граф G можно представить в виде матрицы смежности, содержащий значения весов ребер.



Граф в форме схемы



Матрица смежности связного взвешенного неориенторованного графа



Подграф графа, остовной связный подграф, остовное связное дерево



Цикломатическое число γ показывает сколько ребер графа нужно удалить, чтобы в нем не осталось циклов.

  • Цикломатическое число γ показывает сколько ребер графа нужно удалить, чтобы в нем не осталось циклов.

  • γ=m-n+1

  • Пример, γ=8-5+1=4

  • Для каждого графа обычно существует несколько связных деревьев, с различными весами.



Остовные связные деревья графа G



Построение остовного связного дерева минимального веса. Алгоритм Крускала

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

  • Ребра сортируются по возрастанию весов.

  • Ребра последовательно, по возрастанию их весов, включаются в остовное дерево.



Существует 4 случая:

  • Существует 4 случая:

  • 1) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество;

  • 2) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая;

  • 3) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества;

  • 4) Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.



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

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



Пример построения остовного дерева минимального веса для графа G









Вопросы для закрепления

  • В какой форме можно представить граф?

  • В чем разница между орграфом и не орграфом?

  • Какие графы являются деревьями?

  • Какой граф обладает минимальным весом?



Изучение графов на языке Паскаль. Построить остовные связные деревья минимального веса для графов с 5-ю вершинами



Объявление переменных

  • Два целочисленных пятиэлементных массива X и Y для хранения координат вершин графа

  • Целочисленный двумерный массив R для хранения весов ребер графа

  • Целочисленные переменные i, n и k для счетчиков циклов

  • Целочисленная переменная S для хранения суммы весов ребер дерева минимального веса



Тело программы

  • Генерация случайных координат 5-ти вершин графа (цикл по i).

  • Вычисление весов ребер. Вывод матрицы смежности взвешенного орграфа (вложенные циклы по n и по k)

  • Вывод матрицы смежности взвешенного неориентрованного графа – половины элементов начальной матрицы (начальное значение k=n+1)



Тело программы

  • Построение остовного связанного дерева минимального веса с учетом 4-х случаев.



Даны координаты вершин графа. Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса.

  • V1(50,59)

  • V2(84,6)

  • V3(70,32)

  • V4(22,59)

  • V5(91,40)





Решение.





Решение.

  • мин R35=22, {3,5}

  • мин R14=28, {3,5}, {1,4}

  • мин R23=30, {3,5,2}, {1,4}

  • мин R13=34, {1,2,3,4,5}

  • S=22+28+30+34=114





Ответы



68 50

  • 68 50

  • 22 88

  • 86 10

  • 78 58

  • 79 29



Ответы

  • 68 50

  • 22 88

  • 86 10

  • 78 58

  • 79 29

  • 60 44 13 24

  • 101 64 82

  • 49 20

  • 29

  • 13 1 4

  • 20 3 5

  • 24 1 5

  • 60 1 2

  • 117



Практическая работа

  • 46 51

  • 51 83

  • 43 53

  • 6 60

  • 17 96

  • 32 4 41 54

  • 31 51 36

  • 38 50

  • 38

  • 6

  • 4 1 3

  • 31 2 3

  • 36 2 5

  • 38 3 4

  • 109



  • 4 67

  • 45 74

  • 25 39

  • 43 83

  • 4 33

  • 42 35 42 34

  • 40 9 58

  • 48 22

  • 63

  • 6

  • 9 2 4

  • 22 3 5

  • 34 1 5

  • 35 1 3

  • 100



  • 83 88

  • 78 64

  • 1 43

  • 89 34

  • 83 51

  • 25 94 54 37

  • 80 32 14

  • 88 82

  • 18

  • 6

  • 14 2 5

  • 18 4 5

  • 25 1 2

  • 80 2 3

  • 137



  • 65 34

  • 69 12

  • 33 63

  • 57 18

  • 18 58

  • 22 43 18 53

  • 62 13 69

  • 51 16

  • 56

  • 6

  • 13 2 4

  • 16 3 5

  • 18 1 4

  • 43 1 3

  • 90



  • 29 35

  • 64 37

  • 26 58

  • 73 1

  • 47 82

  • 35 23 56 50

  • 43 37 48

  • 74 32

  • 85

  • 6

  • 23 1 3

  • 32 3 5

  • 35 1 2

  • 37 2 4

  • 127



  • 40 57

  • 7 70

  • 86 76

  • 88 3

  • 98 81

  • 35 50 72 63

  • 79 105 92

  • 73 13

  • 79

  • 6

  • 13 3 5

  • 35 1 2

  • 50 1 3

  • 72 1 4

  • 170



  • 48 37

  • 86 62

  • 40 3

  • 31 40

  • 99 70

  • 45 35 17 61

  • 75 59 15

  • 38 89

  • 74

  • 6

  • 15 2 5

  • 17 1 4

  • 35 1 3

  • 38 3 4

  • 105



  • 2 23

  • 96 36

  • 56 76

  • 89 96

  • 1 20

  • 95 76 114 3

  • 57 60 96

  • 39 78

  • 116

  • 6

  • 3 1 5

  • 39 3 4

  • 57 2 3

  • 60 2 4

  • 159



  • 87 51

  • 11 6

  • 51 15

  • 66 51

  • 59 34

  • 88 51 21 33

  • 41 71 56

  • 39 21

  • 18

  • 6

  • 18 4 5

  • 21 1 4

  • 21 3 5

  • 41 2 3

  • 101



  • 1 54

  • 67 23

  • 50 13

  • 13 61

  • 93 58

  • 73 64 14 92

  • 20 66 44

  • 61 62

  • 80

  • 6

  • 14 1 4

  • 20 2 3

  • 44 2 5

  • 61 3 4

  • 139



Похожие:

Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconПрименение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям
Создать мотивационную базу для изучения самого молодого раздела современной математики; познакомиться с интенсивно развивающимся...
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconТеория графов Граф – это средство для наглядного представления состава и структуры системы
Граф, в котором все линии направленные, называется ориентированным графом(орграфом)
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconОсновные понятия теории графов граф и его свойства примеры графов
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconУрока: «Решение комбинаторных задач с помощью графов» Вопросы к уроку. Чем занимается комбинаторика? Что такое граф? Какие задачи относятся к комбинаторным?
Комбинаторика-раздел математики,рассматривающий вопросы(задачи), связанные с подсчётом числа всевозможных комбинаций из элементов...
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconИсследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель математики папкова мария юрьевна
Проектное исследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель...
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconОбщая Теория Относительности (или альтернативная теория гравитации) Общая Теория Относительности (или альтернативная теория гравитации)
Параметризованный пост-Ньютоновский (ппн) формализм морально устарел, требует модернизации. Причина
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconПознакомиться с историей развития теории многогранников; Познакомиться с историей развития теории многогранников
В тоже время теория многогранников современный раздел математики. Она имеет большое значение не только для теоретических исследований...
Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconДискретные случайные величины. Законы распределения дискретной случайной величины Теория вероятностей и математическая статистика

Теория графов Теория графов – обширный самостоятельный раздел дискретной математики icon«Современные проблемы экономической науки» (магистратура) Раздел Макроэкономика тема 10. Теория экономического роста

Теория графов Теория графов – обширный самостоятельный раздел дискретной математики iconВведение в теорию графов

Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница