Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Графы. Основные понятия

Содержание

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. Похожие презентации

Понятие графа Линейность является характерной чертой большинства современных естественных и искусственных языков. Линейное представление информации(в виде последовательности символов) не является естественным с точки зрения человеческого восприятия. Использование нелинейных форм во многих случаях существенно облегчает понимание.

В разных задачах удобно использовать чертежи разных типов. Соответственно определенные вариации допускает

Граф G= (V, E) состоит из конечного множества вершин (или узлов) V

На рисунке 1 изображен граф с шестью вершинами, обозначенными цифрами 1,2,3,4, 5,6,

Ребро a связывает вершины 1 и 2; ребра e и f связывают

Два ребра, связывающие одну и ту же пару вершин (как e и

Иногда в определении графа запрещают наличие параллельных ребер и/или петель, иногда нет.

Пусть G= (V, E) – некоторый граф. Граф G′= (V′, E′), вершины

Степенью вершины графа называется число ребер графа, инцидентных этой вершине (петли считаются

Так, для графа из примера имеем: δ(1)= δ(2)= δ(3) = 4, δ(4)

Несложно убедиться в справедливости следующего соотношения:

где m– число ребер графа G= (V, E). В самом деле, ребро,

В некоторых случаях рассматриваются направленные ребра, которые называют дугами. Для дуги, соединяющей

Если все ребра графа направлены, его называют ориентированным графом, или орграфом. В

Когда говорят, что в ориентированном графе дуга a соединяет вершины x и

На рис. 2 изображен орграф. Из вершины 1 выходят дуги a и

Полустепенью исхода вершины орграфа называется число дуг графа, начинающихся в этой вершине;

Полустепени исхода и захода вершины v обозначаются соответственно через

Вершины и дуги графа могут быть дополнительно помечены. В этом случае говорят

Маршруты, цепи и циклыПоследовательность вершин

В случае, когда допускаются параллельные дуги, нужно дополнительно указать, по какой дуге

На самом деле, поскольку концы дуг определены однозначно, маршрут можно представить последовательностью

Вообще говоря, и начальная, и конечная вершины могут встретиться на маршруте как

Маршрут называется цепью, если каждая дуга встречается в нем не более одного

Если начальная вершина маршрута совпадает с конечной, его называют замкнутым. Замкнутый маршрут

Например, в графе на рис.2 маршрут 1a2c3e1, или, короче, ace, является простым

Граф, не содержащий циклов, называется ациклическим. Будем говорить, что вершина y достижима

На рис. 3 представлен ациклический граф; «жирными» наконечниками отмечены дуги, входящие в

На множестве вершин неориентированного графа G отношение достижимости является отношением эквивалентности. Класс

Неориентированный граф G называется связным, если в нем любые две вершины можно

На рис. 4 изображен граф с четырьмя компонентами связности.

Эйлеровы цепи и циклыНа рис. 5 приведена схема мостов в г. Кенигсберге

Построим граф задачи, в котором каждой части города соответствует вершина, а каждому

Решение задачи о кенигсбергских мостах сводится теперь к поиску цикла на построенном

Рассмотрим последовательность «выходов» – «заходов» для вершины из этого цикла. Чтобы у

Таким образом, если на графе имеется эйлеров цикл, степени всех вершин должны

Следовательно, имеет место следующая Теорема. Связный граф обладает эйлеровым циклом тогда и

Матрицы смежности и инцидентностиЛюбой ориентированный граф с вершинами

Для неориентированного графа матрица инцидентности выглядит следующим образом:

Например, граф на рис. 2 можно задать следующей матрицей инцидентности (дуги

Графы без параллельных дуг удобно представлять при помощи матриц смежности. Для графа

Если в графе имеются параллельные дуги, то можно полагать, что значение элемента

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

В матрице А вершины занумерованы, начиная с левой верхней, по часовой стрелке.

Обе матрицы представляют один и тот же граф и получаются одна из

Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например, следующая матрица является матрицей смежности ориентированного графа

Пример. Рассмотрим граф на рис. 8. Пути длины 1 представлены дугами. Все

Матрица смежности графа: дает число путей длины1. Ее квадрат:

Пусть G– ориентированный граф и A– его матрица смежности. Рассмотрим последовательность матрицЗафиксируем

В самом деле, если длина пути превосходит n– 1, то такой путь

Таким образом, если из i в j имеется некоторый путь, то в

Бинарные отношения и графыБинарное отношение R на конечном множестве V может быть

Обратно, всякий ориентированный граф без параллельных дуг G задает бинарное отношение R(G)

Если R – бинарное отношение на конечном множестве V= {1, 2, …,

Рассмотрим, как связаны свойства отношения R и соответствующего ему графа G=G(R).Отношение R

По существу, граф G оказывается неориентированным. Можно считать, что симметричным отношениям отвечают неориентированные графы.

Антисимметричность отношения R означает, что xRy и yRx влечет x= y и

Если R– рефлексивное отношение, то есть xRx для любого x∈V, то граф

Отношение R транзитивно, если из xRy и yRz следует xRz. Для графа

Отношение R называется ацикличным, если граф G(R) не содержит нетривиальных циклов. Если

Слайды презентации

Слайд 2 Понятие графа
Линейность является характерной чертой большинства современных

естественных и искусственных языков. Линейное представление информации(в виде последовательности

символов) не является естественным с точки зрения человеческого восприятия. Использование нелинейных форм во многих случаях существенно облегчает понимание. В математике главным средством нелинейного представления информации служат чертежи.

Слайд 3
В разных задачах удобно использовать чертежи разных типов.

В разных задачах удобно использовать чертежи разных типов. Соответственно определенные вариации

Соответственно определенные вариации допускает и определение графа. Неотъемлемыми атрибутами

графов (при всем разнообразии определений) являются вершины и соединяющие их ребра или дуги.

Слайд 4
Граф G= (V, E) состоит из конечного множества

Граф G= (V, E) состоит из конечного множества вершин (или узлов)

вершин (или узлов) V и конечного множества ребер E.

Каждое ребро связывает(соединяет) пару вершин. Если ребро a соединяет вершины x и y, то говорят, что ребро a и вершины x, y инцидентны.

Слайд 5 Например,

Рис.1

Слайд 6 На рисунке 1 изображен граф с шестью вершинами,

На рисунке 1 изображен граф с шестью вершинами, обозначенными цифрами 1,2,3,4,

обозначенными цифрами 1,2,3,4, 5,6, и восемью ребрами, обозначенными буквами

a, b, c, d, e, f, g, h.

Слайд 7 Ребро a связывает вершины 1 и 2;
ребра

Ребро a связывает вершины 1 и 2; ребра e и f

e и f связывают вершины 1 и 4;
ребро

g связывает вершину 2 саму с собой;
вершина 1 инцидентна ребрам a, b, e, f;
ребро c инцидентно вершинам 2 и 3.

Слайд 8
Два ребра, связывающие одну и ту же пару

Два ребра, связывающие одну и ту же пару вершин (как e

вершин (как e и f), называют параллельными (или кратными);

ребро, связывающее вершину саму с собой (как g), называют петлей.

Слайд 9
Иногда в определении графа запрещают наличие параллельных ребер

Иногда в определении графа запрещают наличие параллельных ребер и/или петель, иногда

и/или петель, иногда нет. Мы не будем жестко фиксировать

определение, оговаривая специально, если это оказывается существенным, какого типа граф рассматривается.

Слайд 10
Пусть G= (V, E) – некоторый граф. Граф

Пусть G= (V, E) – некоторый граф. Граф G′= (V′, E′),

G′= (V′, E′), вершины и ребра которого являются вершинами

и ребрами графа G, т.е. V′⊂V, E′⊂E называется подграфом графа G.

Слайд 11
Степенью вершины графа называется число ребер графа, инцидентных

Степенью вершины графа называется число ребер графа, инцидентных этой вершине (петли

этой вершине (петли считаются дважды). Степень вершины v обозначается

δ(v). Вершина степени 0 называется изолированной, вершина степени1 – висячей.

Слайд 12
Так, для графа из примера имеем: δ(1)= δ(2)=

Так, для графа из примера имеем: δ(1)= δ(2)= δ(3) = 4,

δ(3) = 4, δ(4) = 3, δ(5) = 1,

δ(6) = 0;
Вершина 5 – висячая, вершина 6 – изолированная.

Слайд 13
Несложно убедиться в справедливости следующего соотношения:

Слайд 14
где m– число ребер графа G= (V, E).

где m– число ребер графа G= (V, E). В самом деле,

В самом деле, ребро, соединяющее вершины x и y,

вносит вклад по единице в слагаемые: δ(x) и δ(y) (при x = y ребро является петлей и в соответствии с определением вносит вклад 2 в одно слагаемое δ(x)).

Слайд 15
В некоторых случаях рассматриваются направленные ребра, которые называют

В некоторых случаях рассматриваются направленные ребра, которые называют дугами. Для дуги,

дугами. Для дуги, соединяющей две вершины, указывают, из какой

вершины она выходит (начало дуги), и в какую входит (конец дуги). На рисунке направление дуги указывают стрелкой.

Слайд 16
Если все ребра графа направлены, его называют ориентированным

Если все ребра графа направлены, его называют ориентированным графом, или орграфом.

графом, или орграфом. В орграфе параллельными считаются дуги, соединяющие

одинаковые вершины и имеющие одинаковое направление, то есть дуги, имеющие общее начало и общий конец.

Слайд 17
Когда говорят, что в ориентированном графе дуга a

Когда говорят, что в ориентированном графе дуга a соединяет вершины x

соединяет вершины x и y, предполагают, что дуга a

направлена от x к y.

Слайд 18 На рис. 2 изображен орграф. Из вершины 1

На рис. 2 изображен орграф. Из вершины 1 выходят дуги a

выходят дуги a и b, в нее входит дуга

Слайд 19
Полустепенью исхода вершины орграфа называется число дуг графа,

Полустепенью исхода вершины орграфа называется число дуг графа, начинающихся в этой

начинающихся в этой вершине;
полустепенью захода – число дуг

графа, заканчивающихся в ней.

Слайд 20
Полустепени исхода и захода вершины v обозначаются соответственно

через и

. Так, для графа на рис. 2 имеем

Слайд 21 Вершины и дуги графа могут быть дополнительно помечены.

Вершины и дуги графа могут быть дополнительно помечены. В этом случае

В этом случае говорят о нагруженном, или взвешенном, графе.

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

Слайд 22 Маршруты, цепи и циклы
Последовательность вершин

графа G представляет собой маршрут в этом графе от вершины к вершине , если для любого i = 0, 1, 2, …, k–1 вершины и соединены дугой.

Слайд 23 В случае, когда допускаются параллельные дуги, нужно дополнительно

В случае, когда допускаются параллельные дуги, нужно дополнительно указать, по какой

указать, по какой дуге из в

проходит маршрут. В этом случае маршрут от вершины к вершине , задается последовательностью вида

где – последовательность вершин, – - последовательность дуг, причем дуга соединяет вершину с вершиной .

Слайд 24
На самом деле, поскольку концы дуг определены однозначно,

На самом деле, поскольку концы дуг определены однозначно, маршрут можно представить

маршрут можно представить последовательностью дуг

.
Длиной маршрута считается число дуг, которые он содержит. Все вершины маршрута, кроме начальной и конечной, называют внутренними или промежуточными.

Слайд 25
Вообще говоря, и начальная, и конечная вершины могут

Вообще говоря, и начальная, и конечная вершины могут встретиться на маршруте

встретиться на маршруте как промежуточные вершины. Для любой вершины

имеется маршрут из этой вершины в нее же, не содержащий ни одной дуги (длины0).

Слайд 26 Маршрут называется цепью, если каждая дуга встречается в

Маршрут называется цепью, если каждая дуга встречается в нем не более

нем не более одного раза, и простой цепью, если

любая вершина графа инцидентна не более, чем двум дугам маршрута.
Путем называют маршрут, в котором все вершины различны.
Часто термин «путь» используют как синоним «маршрута».

Слайд 27 Если начальная вершина маршрута совпадает с конечной, его

Если начальная вершина маршрута совпадает с конечной, его называют замкнутым. Замкнутый

называют замкнутым. Замкнутый маршрут называется циклом, если он является

цепью; если эта цепь к тому же простая, то и цикл называется простым. Таким образом, цикл– это замкнутый маршрут, у которого все вершины различны, кроме первой и последней.

Слайд 28 Например, в графе на рис.2 маршрут 1a2c3e1, или,

Например, в графе на рис.2 маршрут 1a2c3e1, или, короче, ace, является

короче, ace, является простым циклом. Поскольку параллельных дуг на

графе нет, этот цикл можно указать и по вершинам: 1231. Ясно, что маршруты 2312 и 3123 представляют тот же цикл. Граф, не содержащий циклов, называется ациклическим.

Слайд 29
Граф, не содержащий циклов, называется ациклическим.
Будем говорить,

Граф, не содержащий циклов, называется ациклическим. Будем говорить, что вершина y

что вершина y достижима из вершины x, если в

графе G имеется путь из x в y.

Слайд 30

Слайд 31

Слайд 32 На рис. 3 представлен ациклический граф; «жирными» наконечниками

отмечены дуги, входящие в базисный граф.

Рис.3

Слайд 33 На множестве вершин неориентированного графа G отношение достижимости

На множестве вершин неориентированного графа G отношение достижимости является отношением эквивалентности.

является отношением эквивалентности.
Класс эквивалентности составляют все вершины, которые

могут быть связаны друг с другом некоторым путем. Эти классы эквивалентности называются компонентами связности.

Слайд 34
Неориентированный граф G называется связным, если в нем

Неориентированный граф G называется связным, если в нем любые две вершины

любые две вершины можно соединить путем. Связный граф имеет

всего одну компоненту связности.

Слайд 35 На рис. 4 изображен граф с четырьмя компонентами

связности.

Рис.4

Слайд 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 Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например,

следующая матрица является матрицей смежности ориентированного графа

Слайд 51

Слайд 52 Пример. Рассмотрим граф на рис. 8. Пути длины

Пример. Рассмотрим граф на рис. 8. Пути длины 1 представлены дугами.

1 представлены дугами. Все пути длины 2 и более

выходят из вершины 2. Путь длины k из вершины 2 в вершину 2 представляет собой петлю, повторенную k раз. Остальные пути получаются как комбинации путей длины 1 и 2 с соответствующим числом повторений петли.

Рис.8

Слайд 53 Матрица смежности графа:

дает число путей длины1. Ее

квадрат:

Слайд 54 Пусть G– ориентированный граф и A– его матрица

Пусть G– ориентированный граф и A– его матрица смежности. Рассмотрим последовательность

смежности. Рассмотрим последовательность матриц

Зафиксируем пару вершин i и j.

Если существует какой-нибудь путь из i в j, то существует и путь длины меньше n.

Слайд 55 В самом деле, если длина пути превосходит n–

В самом деле, если длина пути превосходит n– 1, то такой

1, то такой путь проходит через более чем n

вершин, и, значит, на таком пути хотя бы одна вершина, скажем, v, встретится более одного раза.
Отбросив часть пути, ведущую из вершины v в нее саму, получаем более короткий путь из i в j. Повторив подобную операцию несколько раз, можно получить путь из i в j, длина которого не превосходит n– 1.

Слайд 56 Таким образом, если из i в j имеется

Таким образом, если из i в j имеется некоторый путь, то

некоторый путь, то в одной из матриц последовательности

на

месте (i,j) встретится элемент, отличный от нуля.

Если в матрице на месте (i,j) находится элемент, отличный от нуля, а во всех предшествующих матрицах на месте (i,j) стоят нули, то k– это длина кратчайшего пути из i в j.

Слайд 57 Бинарные отношения и графы
Бинарное отношение R на конечном

Бинарные отношения и графыБинарное отношение R на конечном множестве V может

множестве V может быть представлено ориентированным графом G(R), называемым

графом отношения R. Вершинами графа служат элементы множества V; вершины x и y соединены направленной дугой с началом x и концом y, если (x,y)∈R.

Слайд 58 Обратно, всякий ориентированный граф без параллельных дуг G

Обратно, всякий ориентированный граф без параллельных дуг 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 и соответствующего

Рассмотрим, как связаны свойства отношения R и соответствующего ему графа G=G(R).Отношение

ему графа G=G(R).
Отношение R симметрично, если для любых x,

y∈V из xRy следует yRx. Иными словами, если на ориентированном графе G имеется дуга из x в y, то имеется также и дуга из y в x. В этом случае матрица смежности графа G симметрична.

Слайд 61
По существу, граф G оказывается неориентированным. Можно считать,

что симметричным отношениям отвечают неориентированные графы.

Слайд 62 Антисимметричность отношения R означает, что xRy и yRx

Антисимметричность отношения R означает, что xRy и yRx влечет x= y

влечет x= y и равносильна тому, что две различные

вершины графа G могут быть связаны дугой лишь в одном направлении.
Если отношение R асимметрично, то есть xRy влечет ¬yRx, то, кроме того, граф G не должен иметь петель.

Слайд 63 Если R– рефлексивное отношение, то есть xRx для

Если R– рефлексивное отношение, то есть xRx для любого x∈V, то

любого x∈V, то граф G имеет петлю в каждой

вершине, а диагональ матрицы смежности состоит из одних единиц.
Соответственно отношение R антирефлексивно тогда и только тогда, когда граф G не имеет петель.

Слайд 64 Отношение R транзитивно, если из xRy и yRz

Отношение R транзитивно, если из xRy и yRz следует xRz. Для

следует xRz.
Для графа G это означает, что если

G содержит дуги из x в y и из y в z, то он содержит и дугу из x в z. Более того, если существует путь из вершины x в вершину y, то имеется и дуга из x в y.