Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Основные понятия теории графов
Содержание
- 1. Основные понятия теории графов
- 2. 3.1 Абстрактный графГраф можно определить как совокупность
- 3. Само понятие графа подразумевает графическое
- 4. Примеры графов а) неориентированный;б) ориентированный
- 5. Вершины неориентированного графа, связываемые ребром,
- 6. Между вершинами и ребрами
- 7. Граф может содержать петли, т. е.
- 8. В ориентированном графе с некоторой
- 9. Можно говорить об окрестности N(v)
- 10. Для ориентированного графа с множеством
- 11. Граф G = (V, E), у которого
- 12. Граф называется двудольным, если
- 13. 3.2 Графическое представление бинарного отношенияГрафическое представление отношения между элементами множеств А и В
- 14. Представление композиции отношений: а) отношения R и S; б) отношение SR
- 15. Представление функционального отношения
- 16. 3.3 Матричные представления графа Поскольку граф можно
- 17. Графыимеют следующие матрицы смежности:
- 18. Нетрудно видеть, что матрица смежности неориентированного графа обладает симметрией относительно главной диагонали.
- 19. Ориентированный граф можно задать
- 20. Матрицы инцидентности этиз графов будут иметь следующий вид:
- 21. Заметим, что при матричном представ- лении
- 22. 3.4 Части графа Граф
- 23. Любая последовательность вида v1, e1, v2, e2, … , ek, vk+1, где
- 24. Маршрут, все ребра которого различны, называется цепью.
- 25. 3.5 Достижимость и связностьГраф является связным, если
- 26. В ориентированном графе маршрутом называется
- 27. Вершина vj в ориентированном графе
- 28. Очевидно, что все диагональные элементы
- 29. Алгоритм Кристофидеса. Множество R(xi) получается последова-тельным
- 30. Пусть через Г-1(xi) обозначено множество вершин, из
- 31. Пример: Построить матрицы достижимостей и контрадостижимостей для графа G.
- 32. Матрица смежности C = (Cij)=
- 33. Матрица достижимостей R = (rij)
- 34. Матрица контрдостижимостей Q = (qij)
- 35. 3.6 Доминирующие множества графаПодмножество S множества вершин
- 36. Если S является доминирующим множест-
- 37. Наглядным примером задачи о наимень-
- 38. Задача о наименьшем доминирующем множестве
- 39. Наименьшими доминирующими множествами графа G
- 40. Его матрица смежности, дополненная единицами
- 41. 3.7 Независимые множества графа Подмножество S
- 42. Независимое множество,имеющее наибольшую мощность среди всех независимых
- 43. 3.8 Раскраска графа Раскраской некоторого графа G = (V, Е)
- 44. Иногда ставится задача раскраски ребер
- 45. Иногда можно получить раскраску графа,
- 46. Рассмотрим неограниченную последовательность деревьев Т1, Т2, … ,
- 47. Деревья, раскрашиваемые «жадным» алгоритмом
- 48. Бихроматические графы Граф G называется
- 49. Т е о р е м а К ё н и г а Непустой граф является бихроматическим
- 50. 3.9 Планарность графов Количество граней можно найти
- 51. Грань – область плоскости, ограниченная
- 52. Скачать презентанцию
3.1 Абстрактный графГраф можно определить как совокупность двух множеств: G = (V, E), где V – непустое множество, элементы которого называются вершинами, и Е – произвольное множество пар (vi, vj) элементов из множества V, т. е.
Слайды и текст этой презентации
Слайд 3 Само понятие графа подразумевает графическое представление данного объекта.
Вершины изображаются точками, а ребра – линиями, соединяющими эти точки.
Если ребра представляют упорядоченные пары вершин, соответствующие линии изображаются стрелками. Такие ребра называют ориентированными ребрами или, чаще, дугами. В этом случае имеем дело с ориентированным графом в отличие от неориентированного графа, на ребрах которого порядок вершин не задан.
Слайд 5 Вершины неориентированного графа, связываемые ребром, считаются концами этого
ребра. Принято обозначать ребра также парами их концов, например е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).
Слайд 9 Можно говорить об окрестности N(v) и
степени d(v) вершины v ориентированного
графа. При этом
Для неориентированного графа с множеством ребер Е очевидно следующее соотношение: откуда следует, что в любом неориентированном графе число вершин с нечетной степенью всегда четно.
Слайд 10 Для ориентированного графа с
множеством дуг А имеем
В практических приложениях граф (ориентированный или неориентированный), как правило,
является конечным, т.е. его множество вершин конечно. Специальный раздел теории графов изучает также бесконечные графы, у которых множество вершин бесконечно.
Слайд 11 Граф 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.
Слайд 133.2 Графическое представление бинарного отношения
Графическое представление отношения между элементами множеств
А и В
Слайд 163.3 Матричные представления графа
Поскольку граф можно рассматривать как графическое
представление некоторого бинарного отношения, его можно задать той же булевой
матрицей, которая задает данное отношение. Эта матрица называется матрицей смежности графа. Строки и столбцы матрицы смежности соответствуют вершинам графа, а элемент ее на пересечении строки vi и столбца vj имеет значение 1 тогда и только тогда, когда вершины vi и vj смежны. В матрице смежности ориентированного графа этот элемент имеет значение 1, если и только если в данном графе имеется дуга с началом в вершине vi и концом в вершине vj.
Слайд 18
Нетрудно видеть, что матрица смежности неориентированного
графа обладает симметрией относительно главной диагонали.
Слайд 19 Ориентированный граф можно задать
также матрицей
инцидентности,
которая определяется следующим образом. Ее строки соответствуют
вершинам графа, столбцы – дугам. Элемент на пересечении строки v и столбца а имеет значение 1, если вершина v является началом дуги а, и значение –1, если v является концом дуги а. Если вершина v и дуга а не инцидентны, то указанный элемент имеет значение 0. Матрица инцидентности неориентированного графа имеет тот же вид, только в ней все значения –1 заменяются на 1. 
Слайд 21 Заметим, что при матричном представ-
лении графа его вершины,
а также реб-
ра или дуги оказываются упорядоченными.
Любая строка
матрицы смежности является векторным представлением окрестности соответствующей вершины. Любой столбец матрицы инцидентности неориентированного графа содержит ровно две единицы. Сумма значений элементов любого столбца матрицы инцидентности ориентированного графа равна нулю. 
Слайд 223.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
– вершины некоторого графа, а e1, e2, … , ek – его ребра,
причем ei = vivi+1 (i = 1, 2, … , k), называется маршрутом. Маршрут может быть конечным либо бесконечным. Одно и то же ребро может встречаться в маршруте не один раз. Длиной маршрута – это количество входящих в него ребер, причем каждое ребро считается столько раз, сколько оно встречается в данном маршруте.
Слайд 24Маршрут, все ребра которого различны, называется цепью. Цепь, все вершины
которой различны, называется простой цепью. С понятием длины
цепи связано понятие расстояния в графе. Под расстоянием между двумя вершинами понимается длина кратчайшей цепи, связывающей данные вершины.Маршрут v1, e1, v2, e2, … , ek, v1 называется циклическим. Циклическая цепь называется циклом. Простой цикл – это циклическая простая цепь.
Любую цепь и любой цикл графа можно рассматривать как его подграф.
Слайд 253.5 Достижимость и связность
Граф является связным, если между любыми двумя
его вершинами имеется цепь. Связный подграф некоторого графа, не содержащийся
ни в каком другом его связном подграфе, называется компонентой связности или просто компонентой данного графа.
Слайд 26 В ориентированном графе маршрутом называется последовательность вида v1, а1, v2, а2, … , аk, vk+1,
где для всякой дуги аi вершина vi является началом, а
vi+1 – концом. Вершина v1 является началом маршрута, а вершина vk+1 – его концом. Маршрут, в котором все вершины, кроме, возможно, начальной и конечной, различны, называется путем. Путь вида v1, а1, v2, а2, … , аk, v1 называется контуром.
Слайд 27 Вершина 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) обозначено множество вершин, из которых
можно
достичь вершину xi. С использованием путей длины 1, Г-p(xi) –
множество вершин, из которых можно достичь вершину xi с использованием путей длинны р. Тогда Q(xi) можно представить в виде:Q(xi) = {xi}∪Г-1(xi)∪Г-2(xi)∪...∪Г-p(xi),
Где ∪ – операция объединения множеств.
Слайд 353.6 Доминирующие множества графа
Подмножество S множества вершин V графа G
называется доминирующим множеством графа G, если выполняется
условие
− множество вершин, смежных с вершиной v. Другими словами, множество S является доминирующим, если каждая вершина из множества V \ S смежна с некоторой вершиной из S.
Слайд 36 Если S является доминирующим множест-
вом некоторого
графа G, то всякое множес-
тво вершин S′ ⊇ S этого
графа также явля-ется доминирующим. Поэтому представляет интерес задача нахождения минимальных доминирующих множеств, т. е. таких, у которых ни одно собственное подмножество не является доминирующим. Доминирующее множество, имеющее наименьшую мощность, принято называть наименьшим. Эта мощность называется числом доминирования графа G и обозначается символом β(G).
Слайд 37
Наглядным примером задачи о наимень-
шем доминирующем
множестве является
одна из задач о ферзях, где
надо расставить на шахматной доске наименьшее число ферзей так, чтобы каждая клетка была под ударом хотя бы одного из них. Для этого достаточно найти наименьшее доминирующее множество в графе, вершины которого соответствуют клеткам шахматной доск две вершины связаны ребром, если и только если они взаимно достижимы ходом ферзя. Найденное множество вершин указывает, куда надо поставить ферзей, а их число, которое в данном случае равно пяти, есть число доминирования данного графа. 
Слайд 38 Задача о наименьшем доминирующем множестве сводится к известной
задаче о кратчайшем покрытии, которая подроб-
но будет рассмотрена
ниже. В данном случае ее можно поставить следующим образом. Матрицу смежности заданного графа G дополним единицами на главной диагонали. Тогда требуется найти минимальную совокупность строк полученной матрицы, такую, что каждый столбец имел бы единицу по крайней мере в одной из строк найденной совокупности. Говорят, что строка матрицы покрывает столбец, если данный столбец имеет единицу в этой строке.
Слайд 40 Его матрица смежности, дополненная единицами на главной диагонали,
имеет
вид
Каждое из соответствующих множеств строк рассматриваемой
матрицы покрывает все ее столбцы. 
Слайд 413.7 Независимые множества графа
Подмножество S множества вершин V
графа G называется независимым множеством графа G, если выполняется условие
S ∩ N(S) = ∅, т. е. любые две вершины из S не смежны. Если S – независимое множество, то любое его подмножество также является независимым. Поэтому представляет интерес задача нахождения в графе максимальных независимых множеств, т. е. таких, которые не являются собственными подмножествами никаких других независимых множеств.
Слайд 42Независимое множество,
имеющее наибольшую мощность среди всех независимых множеств графа G,
называют наибольшим независимым множеством, а его мощность называют числом независимости
графа G и обозначают символом α(G).
Слайд 433.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, хотя ясно, что всякое дерево можно раскрасить в два цвета.
Слайд 48Бихроматические графы
Граф G называется
k-хроматическим, если γ(G) = k.
Очевидно, пустые и только пустые графы являются 1‑хроматическими. Особый класс
составляют бихроматические графы, т. е. такие, у которых γ(G) = 2.
Слайд 49Т е о р е м а К ё н и г а
Непустой граф является бихроматическим тогда и
только тогда, когда он не содержит циклов нечетной длины.
Слайд 503.9 Планарность графов
Количество граней можно найти
для плоского
связного графа. Плоский граф – граф, который укладывается на плоскости
так, что никакие два его ребра не пересекаются нигде, кроме как в инцидентной им обоим вершине. Граф называется связным, если между любыми его вершинами существует цепь.
Слайд 51 Грань – область плоскости, ограниченная ребрами, любые две
точки которой могут быть соединены линией, не пересекающей ребра графа.
Формула Эйлера. Для любой геометрической реализации графа G=(X,E) на плоскости верно: n-r+f=2, где n=|X|, r=|E|, f - число граней.
