Теория графов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория графов. Доклад-сообщение содержит 59 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Основные понятия теории графов

Слайд 2

Описание слайда:

Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения всех четырех частей суши в задаче о кенигсбергских мостах (1736) Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения всех четырех частей суши в задаче о кенигсбергских мостах (1736)

Слайд 3

Описание слайда:

Основные понятия Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами.

Слайд 4

Описание слайда:

Основные понятия Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Ребра с одинаковыми концевыми вершинами называются параллельными (e1,e4 ). Петля– замкнутое ребро(e5). Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).

Слайд 5

Описание слайда:

Основные понятия Изолированная вершина не инцидентна ни одному ребру (v3). Две вершины смежны, если они являются концевыми вершинами некоторого ребра (v1, v4). Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).

Слайд 6

Описание слайда:

Основные понятия Подграф – любая часть графа, сама являющаяся графом.

Слайд 7

Описание слайда:

Виды графов Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер.

Слайд 8

Описание слайда:

Виды графов

Слайд 9

Описание слайда:

Виды графов Граф G с петлями и кратными ребрами называется псевдограф.

Слайд 10

Описание слайда:

Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве P вершин всегда содержит q=p-1 ребер, т.е. минимальное количество ребер, необходимое для того, чтобы граф был связанным. При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из который представляет собой также дерево или изолированную вершину. Несвязанный граф, компоненты которого являются деревьями, называется лесом. Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве P вершин всегда содержит q=p-1 ребер, т.е. минимальное количество ребер, необходимое для того, чтобы граф был связанным. При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из который представляет собой также дерево или изолированную вершину. Несвязанный граф, компоненты которого являются деревьями, называется лесом.

Слайд 11

Описание слайда:

На практике широко используются такие виды графов, как деревья и прадеревья. На практике широко используются такие виды графов, как деревья и прадеревья. Деревом называется конечный связный неориентированный граф, состоящий, по крайней мере, из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву. Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.

Слайд 12

Описание слайда:

Лесом называется несвязный граф, каждая компонента связности которого является деревом. Лесом называется несвязный граф, каждая компонента связности которого является деревом. Прадеревом называется ориентированный граф G(X) с корнем х0  X, если в каждую вершину хi  х0 (хi  X) заходит ровно одна дуга, а в корень х0 не заходит ни одна дуга. Прадерево не содержит контуров

Слайд 13

Описание слайда:

Неориентированный граф Граф G, рёбра которого не имеют определённого направления, называется неориентированным.

Слайд 14

Описание слайда:

Ориентированный граф Граф G, имеющий определённое направление, называется ориентированным графом или орграфом. Ребра, имеющие направление, называются дугами.

Слайд 15

Описание слайда:

Способы задания графов 1) Явное задание графа как алгебраической системы. Чтобы задать граф, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. {{a,b},{b,c},{a,c},{c,d}}

Слайд 16

Описание слайда:

Способы задания графов 2) Геометрический.

Слайд 17

Описание слайда:

Способы задания графов 3) Матрица смежности. Элементы Aij матрицы смежности A равны количеству ребер между рассматриваемыми вершинами.

Слайд 18

Описание слайда:

Матрица смежности неорграфа Для неорграфа G, представленного на рисунке, матрица смежности имеет вид:

Слайд 19

Описание слайда:

Матрица смежности орграфа Для орграфа G, представленного на рисунке, матрица смежности имеет вид:

Слайд 20

Описание слайда:

Способы задания графов 4) Матрица инцидентности. Матрица инцидентности В –это таблица, строки которой соответствуют вершинам графа, а столбцы - ребрам. Элементы матрицы определяются следующим образом:

Слайд 21

Описание слайда:

Способы задания графов 1) для неорграфа 1, если вершина vi инцидентна ребру ej; bij= 0, в противном случае

Слайд 22

Описание слайда:

Матрица инцидентности орграфа 2) для орграфа -1, если ребро ej входит в вершину vi ; 1, если ребро ej выходит из вершины vi ; bij= 2, если ребро ej –петля из вершины vi ; 0, если ej и vi не инцидентны.

Слайд 23

Описание слайда:

Маршрут Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k.

Слайд 24

Описание слайда:

Маршрут Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6). Маршрут называется замкнутым, если его концевые вершины совпадают (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).

Слайд 25

Описание слайда:

Цепь Маршрут называется цепью, если все его ребра различны. Цепь называется простой, если ее концевые вершины различны(v1, e1, v2, e2, v3, e8, v6, e11, v3). Цепь называется замкнутой, если ее концевые вершины совпадают (v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).

Слайд 26

Описание слайда:

Путь, цикл Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Цикл – это замкнутая цепь ( простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1). Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.

Слайд 27

Описание слайда:

Cвойства путей и циклов 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно. 3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.

Слайд 28

Описание слайда:

Связность графов, компонента связности Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой. Граф называется связным, если в нем существует путь между каждой парой вершин. Компонента связности – максимальный связный подграф в графе.

Слайд 29

Описание слайда:

Степень вершины Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении. Максимальная и минимальная степени вершин графа G обозначаются символами (G) и (G) соответственно: (G)= (G)= Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его вершин одинаковы. Степенью регулярного графа называется степень его вершин.

Слайд 30

Описание слайда:

Сумма степеней вершин графа Утверждение («лемма о рукопожатиях») Сумма всех вершин графа – четное число, равное удвоенному числу ребер: Интерпретация леммы: поскольку в каждом рукопожатии участвуют две руки,то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала). Следствие В любом графе число вершин нечетной степени четно

Слайд 31

Описание слайда:

Изоморфизм графов Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов. Если граф G изоморфен геометрическому графу G' в Rn, то G' называется геометрической реализацией графа G в пространстве Rn.

Слайд 32

Описание слайда:

Пример изоморфных графов Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие ребер: e1e1’, e3e2’, e5e4’, e2e5’, e4e6’, e6e3’.

Слайд 33

Описание слайда:

Изоморфизм как отношение эквивалентности на множестве графов Отношение изоморфизма является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно.

Слайд 34

Описание слайда:

Помеченный и абстрактный графы Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n). Абстрактный (или непомеченный) граф – это класс изоморфных графов.

Слайд 35

Описание слайда:

Характеристики расстояний в графах Характеристики расстояний в графах Пусть G(X) – конечный или бесконечный ориентированный граф. Отклонением d(xi, xj) его вершины xi от вершины xj называется длина кратчайшего пути из хi в xj: d(xi, xj) = min {l[Sk(xi, xj)]}. Отклонение d(xi, xj) удовлетворяет следующим аксиомам метрического пространства: d(xi, xj)  0; d(xi, xj) = 0  xi = xj; d(xi, xj) + d(xj, xk)  d(xi, xk) – неравенство треугольника и не удовлетворяет четвертой аксиоме, а именно: d(xi, xj)  d(xj, xi), так как граф ориентирован. Необходимо отметить, что если xj  G(xi), то d(xi, xj) = .

Слайд 36

Описание слайда:

Отклоненностью вершины xi называется наибольшее из отклонений d(xi, xj) по всем xj: Отклоненностью вершины xi называется наибольшее из отклонений d(xi, xj) по всем xj: В качестве примера рассмотрим схему первой (1870 г.) сети связи для почтовых голубей

Слайд 37

Описание слайда:

Граф, представляющий ее, изображен на рис, а матрица отклонений и вектор отклоненностей – в таблицах соответственно. Граф, представляющий ее, изображен на рис, а матрица отклонений и вектор отклоненностей – в таблицах соответственно. Таблица. Вектор отклонений

Слайд 38

Описание слайда:

Характеристические числа графов Решение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов, поэтому полезно знакомство со следующими характеристиками. Цикломатическое число. Пусть G(X) – неориентированный граф, имеющий n вершин, m ребер и k компонент связности. Цикломатическим числом графа G называется число µ(G) = m - n + k. Это число имеет интересный физический смысл: оно равно наибольшему числу базисных (независимых) циклов в графе. При расчете электрических цепей цикломатическим числом можно пользоваться для определения числа независимых контуров.

Слайд 39

Описание слайда:

Характеристические числа графов Хроматическое число. Пусть р – натуральное число. Граф G(X) называется р-хроматическим, если его вершины можно раскрасить различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р‑хроматическим, называется хроматическим числом графа и обозначается γ(G). Если γ(G) = 2, то граф называется бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нем циклов нечетной длины. Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при программировании. Однако его определение, за исключением γ(G) = 2, представляет собой довольно трудную задачу, требующую применения ЭВМ.

Слайд 40

Описание слайда:

Характеристические числа графов Множество внутренней устойчивости. Множество S  X графа G(X) называется внутренне устойчивым, если никакие две вершины из S не являются смежными, то есть для любого х  S имеет место: G(x)  S = . Множество внутренней устойчивости, содержащее наибольшее число элементов, называется наибольшим внутренне устойчивым множеством, а число элементов этого множества называется числом внутренней устойчивости графа G. Наибольшее внутренне устойчивое множество играет важную роль в теории связи. Множество внешней устойчивости. Множество Т  X графа G(X) называется внешне устойчивым, если любая вершина, не принадлежащая Т, соединена дугами с вершинами из Т, то есть для любого х  Т имеет место: G(x)  Т  . Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества называется числом внешней устойчивости графа G(X).

Слайд 41

Описание слайда:

Эйлеровы и гамильтоновы графы

Слайд 42

Описание слайда:

Слайд 43

Описание слайда:

Граф называется эйлеровым, если он содержит эйлеров цикл Граф называется эйлеровым, если он содержит эйлеров цикл Эйлеров цикл − замкнутый маршрут, который включает каждое ребро графа только один раз (вершины могут повторяться) Пример abcdefcghea

Слайд 44

Описание слайда:

Задача может быть решена в другой постановке: если в граф добавить еще одно ребро, то можно составить маршрут, включающий каждое из ребер только один раз, который начинается в одной из вершин и заканчивается в другой Задача может быть решена в другой постановке: если в граф добавить еще одно ребро, то можно составить маршрут, включающий каждое из ребер только один раз, который начинается в одной из вершин и заканчивается в другой ABCDCBDAB ABDCDABCB Такой маршрут представляет собой эйлерову цепь Граф, содержащий эйлерову цепь, называется полуэйлеровым

Слайд 45

Описание слайда:

Эйлеровы цепи и степени вершин Эйлеровы цепи и степени вершин Эйлеровы циклы и степени вершин

Слайд 46

Описание слайда:

Граф является эйлеровым тогда и только тогда, когда все его вершины имеют четную степень: Граф является эйлеровым тогда и только тогда, когда все его вершины имеют четную степень: G= эйлеров  vV degv=2n, nN Если в графе имеется две вершины нечетной степени, то существует эйлерова цепь, которая начинается в одной из них и заканчивается в другой. При этом граф называется полуэйлеровым

Слайд 47

Описание слайда:

Слайд 48

Описание слайда:

Слайд 49

Описание слайда:

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

Слайд 50

Описание слайда:

Слайд 51

Описание слайда:

Слайд 52

Описание слайда:

Слайд 53

Описание слайда:

Слайд 54

Описание слайда:

Понятие гамильтонова цикла впервые появилось в связи с задачей о кругосветном путешествии, которую рассматривал Уильям Гамильтон: обойти все вершины графа − столицы различных стран − по одному разу и вернуться в исходный пункт Понятие гамильтонова цикла впервые появилось в связи с задачей о кругосветном путешествии, которую рассматривал Уильям Гамильтон: обойти все вершины графа − столицы различных стран − по одному разу и вернуться в исходный пункт Для 20 государств задача представляет обход всех вершин додекаэдра 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1

Слайд 55

Описание слайда:

Слайд 56

Описание слайда:

Слайд 57

Описание слайда:

Слайд 58

Описание слайда:

Слайд 59

Описание слайда:

Эйлеровы графы Эйлеровы графы Определены необходимые и достаточные условия существования эйлеровых циклов Существуют эффективные алгоритмы отыскания эйлеровых циклов Эйлеровы графы встречаются редко Эйлеровы графы менее востребованы

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

Похожие презентации