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

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

Основные понятия теории графов, слайд №1

Основные понятия теории графов, слайд №2

Основные понятия теории графов, слайд №3

Основные понятия теории графов, слайд №4

Основные понятия теории графов, слайд №5

Основные понятия теории графов, слайд №6

Основные понятия теории графов, слайд №7

Основные понятия теории графов, слайд №8

Основные понятия теории графов, слайд №9

Основные понятия теории графов, слайд №10

Основные понятия теории графов, слайд №11

Основные понятия теории графов, слайд №12

Основные понятия теории графов, слайд №13

Основные понятия теории графов, слайд №14

Основные понятия теории графов, слайд №15

Основные понятия теории графов, слайд №16

Основные понятия теории графов, слайд №17

Основные понятия теории графов, слайд №18

Основные понятия теории графов, слайд №19

Основные понятия теории графов, слайд №20

Основные понятия теории графов, слайд №21

Основные понятия теории графов, слайд №22

Основные понятия теории графов, слайд №23

Основные понятия теории графов, слайд №24

Основные понятия теории графов, слайд №25

Основные понятия теории графов, слайд №26

Основные понятия теории графов, слайд №27

Основные понятия теории графов, слайд №28

Основные понятия теории графов, слайд №29

Основные понятия теории графов, слайд №30

Основные понятия теории графов, слайд №31

Основные понятия теории графов, слайд №32

Основные понятия теории графов, слайд №33

Основные понятия теории графов, слайд №34

Основные понятия теории графов, слайд №35

Основные понятия теории графов, слайд №36

Основные понятия теории графов, слайд №37

Основные понятия теории графов, слайд №38

Основные понятия теории графов, слайд №39

Основные понятия теории графов, слайд №40

Основные понятия теории графов, слайд №41

Основные понятия теории графов, слайд №42

Основные понятия теории графов, слайд №43

Основные понятия теории графов, слайд №44

Основные понятия теории графов, слайд №45

Основные понятия теории графов, слайд №46

Основные понятия теории графов, слайд №47

Основные понятия теории графов, слайд №48

Основные понятия теории графов, слайд №49

Основные понятия теории графов, слайд №50

Основные понятия теории графов, слайд №51

Содержание ▲

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

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

Слайд 1

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

Тема 3. Основные понятия теории графов

Слайд 2

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

3.1 Абстрактный граф Граф можно определить как совокупность двух множеств: G = (V, E), где V – непустое множество, элементы которого называются вершинами, и Е – произвольное множество пар (vi, vj) элементов из множества V, т. е. vi  V, vj  V, Е  V2. Элементы множества Е называются ребрами.

Слайд 3

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

Само понятие графа подразумевает графическое представление данного объекта. Вершины изображаются точками, а ребра – линиями, соединяющими эти точки. Если ребра представляют упорядоченные пары вершин, соответствующие линии изображаются стрелками. Такие ребра называют ориентированными ребрами или, чаще, дугами. В этом случае имеем дело с ориентированным графом в отличие от неориентированного графа, на ребрах которого порядок вершин не задан. Само понятие графа подразумевает графическое представление данного объекта. Вершины изображаются точками, а ребра – линиями, соединяющими эти точки. Если ребра представляют упорядоченные пары вершин, соответствующие линии изображаются стрелками. Такие ребра называют ориентированными ребрами или, чаще, дугами. В этом случае имеем дело с ориентированным графом в отличие от неориентированного графа, на ребрах которого порядок вершин не задан.

Слайд 4

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

Примеры графов а) неориентированный; б) ориентированный

Слайд 5

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

Вершины неориентированного графа, связываемые ребром, считаются концами этого ребра. Принято обозначать ребра также парами их концов, например е2  v1v3. Всякая упорядоченная пара вершин (vi, vj), представляющая дугу в ориентированном графе, имеет начало vi и конец vj. Говорят, что дуга выходит из начала и входит в конец. Можно представить как a4 = (v3, v2). Вершины неориентированного графа, связываемые ребром, считаются концами этого ребра. Принято обозначать ребра также парами их концов, например е2  v1v3. Всякая упорядоченная пара вершин (vi, vj), представляющая дугу в ориентированном графе, имеет начало vi и конец vj. Говорят, что дуга выходит из начала и входит в конец. Можно представить как a4 = (v3, v2).

Слайд 6

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

Между вершинами и ребрами неориентированного графа так же, как между вершинами и дугами ориентированного графа, существует отношение инцидентности. При этом в неориентированном графе G = (V, E) вершина v  V и ребро е  Е инцидентны, если v является одним из концов ребра е. В ориентированном графе G = (V, А) вершина v  V и дуга а  А инцидентны, если v является началом либо концом дуги а. Две вершины неориентированного графа смежны, если они инцидентны одному и тому же ребру.

Слайд 7

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

Граф может содержать петли, т. е. ребра, концы которых совпадают, или дуги, у которых начало совпадает с концом. Очевидно, ориентация петли несущественна. Граф может содержать петли, т. е. ребра, концы которых совпадают, или дуги, у которых начало совпадает с концом. Очевидно, ориентация петли несущественна. Множество всех вершин графа G, смежных с вершиной v, называется окрестностью вершины v и обозначается символом N(v). Мощность множества N(v), обозначаемая d(v), называется степенью вершины v.

Слайд 8

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

В ориентированном графе с некоторой вершиной v подобным образом связаны два множества: полуокрестность исхода N +(v) – множество вершин, в которые входят дуги, исходящие из вершины v, и полуокрестность захода N ‑(v) – множество вершин, из которых исходят дуги, заходящие в v. Соответственно мощность множества N +(v) называется полустепенью исхода и обозначается d +(v), а мощность множества N ‑(v) – полустепенью захода и обозначается d ‑(v). В ориентированном графе с некоторой вершиной v подобным образом связаны два множества: полуокрестность исхода N +(v) – множество вершин, в которые входят дуги, исходящие из вершины v, и полуокрестность захода N ‑(v) – множество вершин, из которых исходят дуги, заходящие в v. Соответственно мощность множества N +(v) называется полустепенью исхода и обозначается d +(v), а мощность множества N ‑(v) – полустепенью захода и обозначается d ‑(v).

Слайд 9

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

Можно говорить об окрестности N(v) и Можно говорить об окрестности N(v) и степени d(v) вершины v ориентированного графа. При этом Для неориентированного графа с множеством ребер Е очевидно следующее соотношение: откуда следует, что в любом неориентированном графе число вершин с нечетной степенью всегда четно.

Слайд 10

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

Для ориентированного графа с Для ориентированного графа с множеством дуг А имеем В практических приложениях граф (ориентированный или неориентированный), как правило, является конечным, т.е. его множество вершин конечно. Специальный раздел теории графов изучает также бесконечные графы, у которых множество вершин бесконечно.

Слайд 11

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

Граф G = (V, E), у которого множество Граф G = (V, E), у которого множество ребер пусто, т. е. Е  , называется пустым графом. Неориентированный граф называется полным, если любые две его вершины смежны. Полный граф, число вершин которого n, обозначается символом Kn. Обозначим множество ребер полного графа символом U. Дополнением графа G = (V, E) является графG = (V,E), у которого E = U \ E. Очевидно, что всякий полный граф является дополнением некоторого пустого графа и, наоборот, всякий пустой граф является дополнением некоторого полного графа.

Слайд 12

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

Граф называется двудольным, если Граф называется двудольным, если множество его вершин V разбито на два непересекающихся подмножества V и V , а концы любого его ребра находятся в различных подмножествах. Такой граф задается как G = (V, V, E) или как G = (V, V, A). В полном двудольном графе (V, V, E) каждая вершина из V связана ребром с каждой вершиной из V. Полный двудольный граф, у которого V   p и V   q, обозначается символом Kp, q.

Слайд 13

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

3.2 Графическое представление бинарного отношения Графическое представление отношения между элементами множеств А и В

Слайд 14

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

Представление композиции отношений: а) отношения R и S; б) отношение SR

Слайд 15

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

Представление функционального отношения

Слайд 16

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

3.3 Матричные представления графа Поскольку граф можно рассматривать как графическое представление некоторого бинарного отношения, его можно задать той же булевой матрицей, которая задает данное отношение. Эта матрица называется матрицей смежности графа. Строки и столбцы матрицы смежности соответствуют вершинам графа, а элемент ее на пересечении строки vi и столбца vj имеет значение 1 тогда и только тогда, когда вершины vi и vj смежны. В матрице смежности ориентированного графа этот элемент имеет значение 1, если и только если в данном графе имеется дуга с началом в вершине vi и концом в вершине vj.

Слайд 17

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

Графы имеют следующие матрицы смежности:

Слайд 18

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

Нетрудно видеть, что матрица смежности неориентированного графа обладает симметрией относительно главной диагонали.

Слайд 19

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

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

Слайд 20

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

Матрицы инцидентности этиз графов Матрицы инцидентности этиз графов будут иметь следующий вид:

Слайд 21

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

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

Слайд 22

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

3.4 Части графа Граф Н = (W, F) называется подграфом графа G = (V, E), если W  V, F  E и обе вершины, инцидентные любому ребру из F, принадлежат W. Подграф Н графа G называется его остовным подграфом, если W = V. Если F является множеством всех ребер графа G, все концы которых содержатся в множестве W, то подграф Н = (W, F) называется подграфом, порожденным множеством W.

Слайд 23

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

Любая последовательность вида v1, e1, v2, e2, … , ek, vk+1, где v1, v2, … , vk+1 Любая последовательность вида v1, e1, v2, e2, … , ek, vk+1, где v1, v2, … , vk+1 – вершины некоторого графа, а e1, e2, … , ek – его ребра, причем ei = vivi+1 (i = 1, 2, … , k), называется маршрутом. Маршрут может быть конечным либо бесконечным. Одно и то же ребро может встречаться в маршруте не один раз. Длиной маршрута – это количество входящих в него ребер, причем каждое ребро считается столько раз, сколько оно встречается в данном маршруте.

Слайд 24

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

Маршрут, все ребра которого различны, называется цепью. Цепь, все вершины Маршрут, все ребра которого различны, называется цепью. Цепь, все вершины которой различны, называется простой цепью. С понятием длины цепи связано понятие расстояния в графе. Под расстоянием между двумя вершинами понимается длина кратчайшей цепи, связывающей данные вершины. Маршрут v1, e1, v2, e2, … , ek, v1 называется циклическим. Циклическая цепь называется циклом. Простой цикл – это циклическая простая цепь. Любую цепь и любой цикл графа можно рассматривать как его подграф.

Слайд 25

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

3.5 Достижимость и связность Граф является связным, если между любыми двумя его вершинами имеется цепь. Связный подграф некоторого графа, не содержащийся ни в каком другом его связном подграфе, называется компонентой связности или просто компонентой данного графа.

Слайд 26

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

В ориентированном графе маршрутом называется последовательность вида v1, а1, v2, а2, … , аk, vk+1, где для всякой дуги аi вершина vi является началом, а vi+1 – концом. Вершина v1 является началом маршрута, а вершина vk+1 – его концом. Маршрут, в котором все вершины, кроме, возможно, начальной и конечной, различны, называется путем. Путь вида v1, а1, v2, а2, … , аk, v1 называется контуром. В ориентированном графе маршрутом называется последовательность вида v1, а1, v2, а2, … , аk, vk+1, где для всякой дуги аi вершина vi является началом, а vi+1 – концом. Вершина v1 является началом маршрута, а вершина vk+1 – его концом. Маршрут, в котором все вершины, кроме, возможно, начальной и конечной, различны, называется путем. Путь вида v1, а1, v2, а2, … , аk, v1 называется контуром.

Слайд 27

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

Вершина vj в ориентированном графе Вершина vj в ориентированном графе является достижимой из вершины vj, если в этом графе имеется путь с началом в vi и концом в vj. Ориентированный граф является сильно связным, если любая его вершина достижима из любой вершины. Матрицы достижимостей и контрдостижимостей. Если существует путь, идущий от вершины xi к вершине xj, то говорят, что xj достижима из вершины xj. Обозначим через R(xi) множество вершин графа, достижимых из вершины xi. Определим маршрут дотижимостей R=(rij) с элементами

Слайд 28

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

Очевидно, что все диагональные элементы матрицы R равны 1 (xj достижима из xi). Пусть через Г(xi) обозначено множество вершин, которые достижимы из x с использованием путей длины 1, через Г2(хi) – множество вершин, достижимых из хi с использованием путей длины 2, ….. , Гp(xi) – множество вершин, достижимых из xi c использованием путей длины длинны Р. Тогда R(xi) можно представить в виде

Слайд 29

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

Алгоритм Кристофидеса. Множество R(xi) получается последова-тельным выполнением (слева направо) операций объединения в соотношении () до тех пор, пока «текущее» множество не перестает увеличиваться по размеру при очередной операции объединения. Обозначим через Q(xi) множество вершин, из которых можно достичь вершину xi. Определим маршрут контрадостижимостей Q=(qij) с элементами

Слайд 30

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

Пусть через Г-1(xi) обозначено множество вершин, из которых Пусть через Г-1(xi) обозначено множество вершин, из которых можно достичь вершину xi. С использованием путей длины 1, Г-p(xi) – множество вершин, из которых можно достичь вершину xi с использованием путей длинны р. Тогда Q(xi) можно представить в виде: Q(xi) = {xi}Г-1(xi)Г-2(xi)...Г-p(xi), Где  – операция объединения множеств.

Слайд 31

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

Пример: Построить матрицы достижимостей и контрадостижимостей для графа G.

Слайд 32

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

Матрица смежности C = (Cij)=

Слайд 33

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

Матрица достижимостей R = (rij)

Слайд 34

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

Матрица контрдостижимостей Q = (qij)

Слайд 35

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

3.6 Доминирующие множества графа Подмножество S множества вершин V графа G называется доминирующим множеством графа G, если выполняется условие  множество вершин, смежных с вершиной v. Другими словами, множество S является доминирующим, если каждая вершина из множества V \ S смежна с некоторой вершиной из S.

Слайд 36

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

Если S является доминирующим множест- Если S является доминирующим множест- вом некоторого графа G, то всякое множес- тво вершин S  S этого графа также явля- ется доминирующим. Поэтому представляет интерес задача нахождения минимальных доминирующих множеств, т. е. таких, у которых ни одно собственное подмножество не является доминирующим. Доминирующее множество, имеющее наименьшую мощность, принято называть наименьшим. Эта мощность называется числом доминирования графа G и обозначается символом (G).

Слайд 37

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

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

Слайд 38

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

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

Слайд 39

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

Наименьшими доминирующими множествами графа G Наименьшими доминирующими множествами графа G являются {v3, v7}, {v5, v7} и {v6, v7}.

Слайд 40

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

Его матрица смежности, дополненная единицами на главной диагонали, имеет Его матрица смежности, дополненная единицами на главной диагонали, имеет вид Каждое из соответствующих множеств строк рассматриваемой матрицы покрывает все ее столбцы.

Слайд 41

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

3.7 Независимые множества графа Подмножество S множества вершин V графа G называется независимым множеством графа G, если выполняется условие S  N(S)  , т. е. любые две вершины из S не смежны. Если S – независимое множество, то любое его подмножество также является независимым. Поэтому представляет интерес задача нахождения в графе максимальных независимых множеств, т. е. таких, которые не являются собственными подмножествами никаких других независимых множеств.

Слайд 42

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

Независимое множество, Независимое множество, имеющее наибольшую мощность среди всех независимых множеств графа G, называют наибольшим независимым множеством, а его мощность называют числом независимости графа G и обозначают символом (G).

Слайд 43

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

3.8 Раскраска графа Раскраской некоторого графа G = (V, Е) называется такое разбиение множества вершин V на непересекающиеся подмножества V1, V2, … , Vk, что никакие две вершины из одного, любого, из этих подмножеств не смежны. Считается, что вершины, принадлежащие одному и тому же подмножеству Vi, выкрашены при этом в один и тот же цвет i. Задача состоит в том, чтобы раскрасить вершины графа G в минимальное число цветов. Оно называется хроматическим числом графа и обозначается (G).

Слайд 44

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

Иногда ставится задача раскраски Иногда ставится задача раскраски ребер графа G = (V, Е), где требуется получить такое разбиение множества ребер Е на непересекающиеся подмножества Е1, Е2, … , Ер, что ни одна пара ребер из одного и того же Еi (i = 1, 2, … , р) не имеет общей инцидентной вершины. Данная задача сводится к раскраске вершин.

Слайд 45

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

Иногда можно получить раскраску графа, минимальную или близкую к минималь- Иногда можно получить раскраску графа, минимальную или близкую к минималь- ной, с помощью так называемого «жадного» алгоритма, где на каждом шаге в текущий цвет раскрашивается как можно больше вершин. Желательно для этого брать наибольшее независимое множество. Раскрашенные вершины удаляются из графа, вводится новый цвет, в него раскрашивается опять как можно больше вершин и так далее до тех пор, пока множество вершин графа не станет пустым.

Слайд 46

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

Рассмотрим неограниченную последовательность деревьев Т1, Т2, … , Тi. Дерево Т1 состоит из трех вершин и двух ребер. Дерево Ti получается из Ti–1 присоединением к каждой вершине Ti – 1 двух смежных с ней вершин. Наибольшее независимое множество дерева Ti составляют все вершины, не принадлежащие Ti–1. Число цветов, получаемое при раскраске дерева Ti данным способом, равно i+1, хотя ясно, что всякое дерево можно раскрасить в два цвета. Рассмотрим неограниченную последовательность деревьев Т1, Т2, … , Тi. Дерево Т1 состоит из трех вершин и двух ребер. Дерево Ti получается из Ti–1 присоединением к каждой вершине Ti – 1 двух смежных с ней вершин. Наибольшее независимое множество дерева Ti составляют все вершины, не принадлежащие Ti–1. Число цветов, получаемое при раскраске дерева Ti данным способом, равно i+1, хотя ясно, что всякое дерево можно раскрасить в два цвета.

Слайд 47

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

Деревья, раскрашиваемые «жадным» алгоритмом

Слайд 48

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

Бихроматические графы Граф G называется k-хроматическим, если (G) = k. Очевидно, пустые и только пустые графы являются 1‑хроматическими. Особый класс составляют бихроматические графы, т. е. такие, у которых (G) = 2.

Слайд 49

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

Т е о р е м а К ё н и г а Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Слайд 50

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

3.9 Планарность графов Количество граней можно найти для плоского связного графа. Плоский граф – граф, который укладывается на плоскости так, что никакие два его ребра не пересекаются нигде, кроме как в инцидентной им обоим вершине. Граф называется связным, если между любыми его вершинами существует цепь.

Слайд 51

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

Грань – область плоскости, ограниченная ребрами, любые две точки которой могут быть соединены линией, не пересекающей ребра графа. Грань – область плоскости, ограниченная ребрами, любые две точки которой могут быть соединены линией, не пересекающей ребра графа. Формула Эйлера. Для любой геометрической реализации графа G=(X,E) на плоскости верно: n-r+f=2, где n=|X|, r=|E|, f - число граней.