- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Графы. Основные понятия
Содержание
- 2. Понятие графа Линейность является характерной чертой
- 3. В разных задачах удобно использовать чертежи разных
- 4. Граф G= (V, E) состоит из конечного
- 5. Например,
- 6. На рисунке 1 изображен граф с шестью
- 7. Ребро a связывает вершины 1 и 2;
- 8. Два ребра, связывающие одну и ту же
- 9. Иногда в определении графа запрещают наличие параллельных
- 10. Пусть G= (V, E) – некоторый граф.
- 11. Степенью вершины графа называется число ребер графа,
- 12. Так, для графа из примера имеем: δ(1)=
- 13. Несложно убедиться в справедливости следующего соотношения:
- 14. где m– число ребер графа G= (V,
- 15. В некоторых случаях рассматриваются направленные ребра, которые
- 16. Если все ребра графа направлены, его называют
- 17. Когда говорят, что в ориентированном графе дуга
- 18. На рис. 2 изображен орграф. Из вершины
- 19. Полустепенью исхода вершины орграфа называется число дуг
- 20. Полустепени исхода и захода вершины v обозначаются
- 21. Вершины и дуги графа могут быть дополнительно
- 22. Маршруты, цепи и циклыПоследовательность вершин
- 23. В случае, когда допускаются параллельные дуги, нужно
- 24. На самом деле, поскольку концы дуг определены
- 25. Вообще говоря, и начальная, и конечная вершины
- 26. Маршрут называется цепью, если каждая дуга встречается
- 27. Если начальная вершина маршрута совпадает с конечной,
- 28. Например, в графе на рис.2 маршрут 1a2c3e1,
- 29. Граф, не содержащий циклов, называется ациклическим. Будем
- 30.
- 31.
- 32. На рис. 3 представлен ациклический граф; «жирными»
- 33. На множестве вершин неориентированного графа G отношение
- 34. Неориентированный граф G называется связным, если в
- 35. На рис. 4 изображен граф с четырьмя
- 36. Эйлеровы цепи и циклыНа рис. 5 приведена
- 37. Построим граф задачи, в котором каждой части
- 38. Решение задачи о кенигсбергских мостах сводится теперь
- 39. Рассмотрим последовательность «выходов» – «заходов» для вершины
- 40. Таким образом, если на графе имеется эйлеров
- 41. Следовательно, имеет место следующая Теорема. Связный граф
- 42. Матрицы смежности и инцидентностиЛюбой ориентированный граф с
- 43. Для неориентированного графа матрица инцидентности выглядит следующим
- 44. Например, граф на рис. 2 можно
- 45. Графы без параллельных дуг удобно представлять при
- 46. Если в графе имеются параллельные дуги, то
- 47. Матрица смежности неориентированного графа симметрична. Например, матрицей
- 48. В матрице А вершины занумерованы, начиная с
- 49. Обе матрицы представляют один и тот же
- 50. Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например, следующая матрица является матрицей смежности ориентированного графа
- 52. Пример. Рассмотрим граф на рис. 8. Пути
- 53. Матрица смежности графа: дает число путей длины1. Ее квадрат:
- 54. Пусть G– ориентированный граф и A– его
- 55. В самом деле, если длина пути превосходит
- 56. Таким образом, если из i в j
- 57. Бинарные отношения и графыБинарное отношение R на
- 58. Обратно, всякий ориентированный граф без параллельных дуг
- 59. Если R – бинарное отношение на конечном
- 60. Рассмотрим, как связаны свойства отношения R и
- 61. По существу, граф G оказывается неориентированным. Можно считать, что симметричным отношениям отвечают неориентированные графы.
- 62. Антисимметричность отношения R означает, что xRy и
- 63. Если R– рефлексивное отношение, то есть xRx
- 64. Отношение R транзитивно, если из xRy и
- 65.
- 66.
- 67. Скачать презентацию
- 68. Похожие презентации
Понятие графа Линейность является характерной чертой большинства современных естественных и искусственных языков. Линейное представление информации(в виде последовательности символов) не является естественным с точки зрения человеческого восприятия. Использование нелинейных форм во многих случаях существенно облегчает понимание.
Слайд 3
В разных задачах удобно использовать чертежи разных типов.
Соответственно определенные вариации допускает и определение графа. Неотъемлемыми атрибутами
графов (при всем разнообразии определений) являются вершины и соединяющие их ребра или дуги.
Слайд 4
Граф G= (V, E) состоит из конечного множества
вершин (или узлов) V и конечного множества ребер E.
Каждое ребро связывает(соединяет) пару вершин. Если ребро a соединяет вершины x и y, то говорят, что ребро a и вершины x, y инцидентны.Слайд 6 На рисунке 1 изображен граф с шестью вершинами,
обозначенными цифрами 1,2,3,4, 5,6, и восемью ребрами, обозначенными буквами
a, b, c, d, e, f, g, h.
Слайд 7
Ребро a связывает вершины 1 и 2;
ребра
e и f связывают вершины 1 и 4;
ребро
g связывает вершину 2 саму с собой;вершина 1 инцидентна ребрам a, b, e, f;
ребро c инцидентно вершинам 2 и 3.
Слайд 8
Два ребра, связывающие одну и ту же пару
вершин (как e и f), называют параллельными (или кратными);
ребро, связывающее вершину саму с собой (как g), называют петлей.
Слайд 9
Иногда в определении графа запрещают наличие параллельных ребер
и/или петель, иногда нет. Мы не будем жестко фиксировать
определение, оговаривая специально, если это оказывается существенным, какого типа граф рассматривается.
Слайд 10
Пусть G= (V, E) – некоторый граф. Граф
G′= (V′, E′), вершины и ребра которого являются вершинами
и ребрами графа G, т.е. V′⊂V, E′⊂E называется подграфом графа G.
Слайд 11
Степенью вершины графа называется число ребер графа, инцидентных
этой вершине (петли считаются дважды). Степень вершины v обозначается
δ(v). Вершина степени 0 называется изолированной, вершина степени1 – висячей.
Слайд 12
Так, для графа из примера имеем: δ(1)= δ(2)=
δ(3) = 4, δ(4) = 3, δ(5) = 1,
δ(6) = 0;Вершина 5 – висячая, вершина 6 – изолированная.
Слайд 14
где m– число ребер графа G= (V, E).
В самом деле, ребро, соединяющее вершины x и y,
вносит вклад по единице в слагаемые: δ(x) и δ(y) (при x = y ребро является петлей и в соответствии с определением вносит вклад 2 в одно слагаемое δ(x)).
Слайд 15
В некоторых случаях рассматриваются направленные ребра, которые называют
дугами. Для дуги, соединяющей две вершины, указывают, из какой
вершины она выходит (начало дуги), и в какую входит (конец дуги). На рисунке направление дуги указывают стрелкой.
Слайд 16
Если все ребра графа направлены, его называют ориентированным
графом, или орграфом. В орграфе параллельными считаются дуги, соединяющие
одинаковые вершины и имеющие одинаковое направление, то есть дуги, имеющие общее начало и общий конец.
Слайд 17
Когда говорят, что в ориентированном графе дуга a
соединяет вершины x и y, предполагают, что дуга a
направлена от x к y.
Слайд 19
Полустепенью исхода вершины орграфа называется число дуг графа,
начинающихся в этой вершине;
полустепенью захода – число дуг
графа, заканчивающихся в ней.
Слайд 20
Полустепени исхода и захода вершины v обозначаются соответственно
через и
. Так, для графа на рис. 2 имеемСлайд 21 Вершины и дуги графа могут быть дополнительно помечены.
В этом случае говорят о нагруженном, или взвешенном, графе.
Подграфом орграфа G называют любой орграф, вершины которого составляют часть множества вершин графа G, а дуги– часть множества его дуг.
Слайд 22
Маршруты, цепи и циклы
Последовательность вершин
графа G представляет собой маршрут в этом графе от вершины к вершине , если для любого i = 0, 1, 2, …, k–1 вершины и соединены дугой.
Слайд 23 В случае, когда допускаются параллельные дуги, нужно дополнительно
указать, по какой дуге из в
проходит маршрут. В этом случае маршрут от вершины к вершине , задается последовательностью видагде – последовательность вершин, – - последовательность дуг, причем дуга соединяет вершину с вершиной .
Слайд 24
На самом деле, поскольку концы дуг определены однозначно,
маршрут можно представить последовательностью дуг
.Длиной маршрута считается число дуг, которые он содержит. Все вершины маршрута, кроме начальной и конечной, называют внутренними или промежуточными.
Слайд 25
Вообще говоря, и начальная, и конечная вершины могут
встретиться на маршруте как промежуточные вершины. Для любой вершины
имеется маршрут из этой вершины в нее же, не содержащий ни одной дуги (длины0).Слайд 26 Маршрут называется цепью, если каждая дуга встречается в
нем не более одного раза, и простой цепью, если
любая вершина графа инцидентна не более, чем двум дугам маршрута.Путем называют маршрут, в котором все вершины различны.
Часто термин «путь» используют как синоним «маршрута».
Слайд 27 Если начальная вершина маршрута совпадает с конечной, его
называют замкнутым. Замкнутый маршрут называется циклом, если он является
цепью; если эта цепь к тому же простая, то и цикл называется простым. Таким образом, цикл– это замкнутый маршрут, у которого все вершины различны, кроме первой и последней.Слайд 28 Например, в графе на рис.2 маршрут 1a2c3e1, или,
короче, ace, является простым циклом. Поскольку параллельных дуг на
графе нет, этот цикл можно указать и по вершинам: 1231. Ясно, что маршруты 2312 и 3123 представляют тот же цикл. Граф, не содержащий циклов, называется ациклическим.
Слайд 29
Граф, не содержащий циклов, называется ациклическим.
Будем говорить,
что вершина y достижима из вершины x, если в
графе G имеется путь из x в y.Слайд 32 На рис. 3 представлен ациклический граф; «жирными» наконечниками
отмечены дуги, входящие в базисный граф.
Рис.3Слайд 33 На множестве вершин неориентированного графа G отношение достижимости
является отношением эквивалентности.
Класс эквивалентности составляют все вершины, которые
могут быть связаны друг с другом некоторым путем. Эти классы эквивалентности называются компонентами связности.
Слайд 34
Неориентированный граф G называется связным, если в нем
любые две вершины можно соединить путем. Связный граф имеет
всего одну компоненту связности.
Слайд 36
Эйлеровы цепи и циклы
На рис. 5 приведена схема
мостов в г. Кенигсберге времен Эйлера.
Рис.5Слайд 37 Построим граф задачи, в котором каждой части города
соответствует вершина, а каждому мосту– ребро (рис. 6).
Рис.6Слайд 38 Решение задачи о кенигсбергских мостах сводится теперь к
поиску цикла на построенном графе, в который все ребра
графа входят по одному разу. В общем случае цикл, обладающий таким свойством, называется эйлеровым. Аналогично цепь называется эйлеровой, если она проходит по одному разу через каждое ребро.Слайд 39 Рассмотрим последовательность «выходов» – «заходов» для вершины из
этого цикла.
Чтобы у графа имелся эйлеров цикл, степени
всех вершин должны быть четными. Так как вершина должна быть инцидентна четному числу ребер, по которым только и можно «зайти» и «выйти».
Слайд 40
Таким образом, если на графе имеется эйлеров цикл,
степени всех вершин должны быть четными. Граф на рис.
6 этим свойством не обладает, а значит, составить соответствующий маршрут невозможно.
Слайд 41
Следовательно, имеет место следующая
Теорема. Связный граф обладает
эйлеровым циклом тогда и только тогда, когда степени всех
его вершин четны.
Слайд 42
Матрицы смежности и инцидентности
Любой ориентированный граф с вершинами
размера n×m, в которой , если дуга исходит из вершины если дуга заходит в вершину если дуга не инцидентна вершине .
Слайд 43
Для неориентированного графа матрица инцидентности выглядит следующим образом:
если дуга
инцидентна вершине , и если дуга не инцидентна вершине .
Слайд 44 Например, граф на рис. 2 можно задать
следующей матрицей инцидентности (дуги упорядочены в алфавитном порядке):
Слайд 45 Графы без параллельных дуг удобно представлять при помощи
матриц смежности. Для графа с n вершинами матрица смежности–
это квадратная матрица порядка n, состоящая из нулей и единиц.Элемент равен 1, если имеется дуга, соединяющая вершины i и j, и равен 0 в противном случае.
Слайд 46
Если в графе имеются параллельные дуги, то
можно
полагать, что значение элемента матрицы смежности
равны числу дуг, соединяющих вершины i и j.Слайд 47 Матрица смежности неориентированного графа симметрична. Например, матрицей смежности
графа, представленного на рис. 7, служит матрица А.
Рис.7Слайд 48 В матрице А вершины занумерованы, начиная с левой
верхней, по часовой стрелке. Если изменить порядок нумерации вершин,
то изменится и матрица смежности. Например, нумеруя вершины того же графа по часовой стрелке, начав с правой верхней вершины, мы получим матрицу смежностиСлайд 49 Обе матрицы представляют один и тот же граф
и получаются одна из другой перестановкой строк и столбцов.
Вообще, любая перестановка, применяемая одновременно и к строкам и к столбцам матрицы смежности некоторого графа, приводит снова к матрице смежности того же графа.
В случае, когда вершины графа упорядочены, матрица смежности определена однозначно.
Слайд 50 Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например,
следующая матрица является матрицей смежности ориентированного графа
Слайд 52 Пример. Рассмотрим граф на рис. 8. Пути длины
1 представлены дугами. Все пути длины 2 и более
выходят из вершины 2. Путь длины k из вершины 2 в вершину 2 представляет собой петлю, повторенную k раз. Остальные пути получаются как комбинации путей длины 1 и 2 с соответствующим числом повторений петли.Рис.8
Слайд 54 Пусть G– ориентированный граф и A– его матрица
смежности. Рассмотрим последовательность матриц
Зафиксируем пару вершин i и j.
Если существует какой-нибудь путь из i в j, то существует и путь длины меньше n. Слайд 55 В самом деле, если длина пути превосходит n–
1, то такой путь проходит через более чем n
вершин, и, значит, на таком пути хотя бы одна вершина, скажем, v, встретится более одного раза.Отбросив часть пути, ведущую из вершины v в нее саму, получаем более короткий путь из i в j. Повторив подобную операцию несколько раз, можно получить путь из i в j, длина которого не превосходит n– 1.
Слайд 56 Таким образом, если из i в j имеется
некоторый путь, то в одной из матриц последовательности
на
месте (i,j) встретится элемент, отличный от нуля. Если в матрице на месте (i,j) находится элемент, отличный от нуля, а во всех предшествующих матрицах на месте (i,j) стоят нули, то k– это длина кратчайшего пути из i в j.
Слайд 57
Бинарные отношения и графы
Бинарное отношение R на конечном
множестве V может быть представлено ориентированным графом G(R), называемым
графом отношения R. Вершинами графа служат элементы множества V; вершины x и y соединены направленной дугой с началом x и концом y, если (x,y)∈R.Слайд 58 Обратно, всякий ориентированный граф без параллельных дуг G
задает бинарное отношение R(G) на множестве своих вершин, чьим
графом он и является: вершины x и y связаны отношением R(G), если они соединены направленной дугой с началом x и концом y.Слайд 59 Если R – бинарное отношение на конечном множестве
V= {1, 2, …, n}, а G– граф c
вершинамиV = {1, 2, …, n}, то матрица смежности графа G совпадает с характеристической матрицей отношения R в том и только том случае, когда G = G(R) или, что равносильно, R = R(G).
Слайд 60 Рассмотрим, как связаны свойства отношения R и соответствующего
ему графа G=G(R).
Отношение R симметрично, если для любых x,
y∈V из xRy следует yRx. Иными словами, если на ориентированном графе G имеется дуга из x в y, то имеется также и дуга из y в x. В этом случае матрица смежности графа G симметрична.
Слайд 61
По существу, граф G оказывается неориентированным. Можно считать,
что симметричным отношениям отвечают неориентированные графы.
Слайд 62 Антисимметричность отношения R означает, что xRy и yRx
влечет x= y и равносильна тому, что две различные
вершины графа G могут быть связаны дугой лишь в одном направлении.Если отношение R асимметрично, то есть xRy влечет ¬yRx, то, кроме того, граф G не должен иметь петель.
Слайд 63 Если R– рефлексивное отношение, то есть xRx для
любого x∈V, то граф G имеет петлю в каждой
вершине, а диагональ матрицы смежности состоит из одних единиц.Соответственно отношение R антирефлексивно тогда и только тогда, когда граф G не имеет петель.
Слайд 64 Отношение R транзитивно, если из xRy и yRz
