Исследование графов
Задание №1
1. Проверить справедливость
тождеств или включений, используя алгебру множеств и диаграммы Эйлера-Венна.
а) X/Y = (; б) A/(B/C) = /B)
Решение:
a).Покажем, что X/Y = XЕсли X/Y, то элемент аX и аY;
Так как аY, то а, т.е., тогда для выполнения обоих условий необходимо:
а (X).
X = = (правило де Моргана)
Множество (X)
является подмножеством (X, поэтому: (X, тогда
X/Y = (X
б). Покажем, что A/(B/C) = /B):
A/(B/C) =A/(B) = A = A
B/C
= B
A
AA/(B
Задание №2
Изобразите граф и матрицу отношения,
обладающего свойствами рефлексивности, транзитивности и антисиммеричности. (не
менее 5 вершин)
Решение:
Рефлексивность:
Бинарное отношение R на множестве X называется рефлексивным, если всякий элемент этого множества
находится в отношении Rс самим собой.
Все диагональные элементы матрицы
равны 1; граф содержит петли во всех узлах.
Антисимметричность:
Бинарное отношение R на множестве X называется антисимметричным, если для каждой пары элементов
множества а, b выполнение отношений aRb и bRa влечет a=b.
В матрице нет симметрично
расположенных 1; для графа не существует двух различных узлов, связанных парой
разнонаправленных дуг.
Транзитивность:
Бинарное отношение R на множестве X называется транзитивным, если для любых трех элементов множества а,
b, с выполнение отношений aRbи bRс влечет выполнение отношения aRc.
В графе для любых двух дуг, таких,
что одна направлена от а к b, а другая от b к с, существует дуга, соединяющая а и с
Задание №3
тождество граф ассиметричность
неориентированный
Считая данный граф
неориентированным, обозначить его вершины и рёбра разными символами и
определить.
. Локальные степени и окружения
каждой вершины в виде структуры смежности;
. Построить матрицы инцидентности и
смежности;
. Рассмотреть части графа. Привести
примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх
вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры
пересечения и объединения частей графа;
. Привести примеры циклического
маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
. Определить центр, диаметр и радиус
графа.
Считая граф ориентированным,
определить
. Степени вершин
. Матрицы инцидентности и смежности.
. Привести примеры пути,
ориентированной цепи, простой цепи, контура, цикла и простого цикла.
Решение:
Степени вершин:
a - 4; NG(a) = 4;
b - 3; NG(b) = 3;
c - 3; NG(c) = 3;
d - 4; NG(d) = 4;
e - 4; NG(e) = 4;
f - 3; NG(f) = 3;
q - 5; NG(q) = 5;
Количество ребер, инцидентных
вершине Х называют локальной степенью вершины.
Множество вершин графа, смежных с
некоторой вершиной Х, называется окружением вершины Х и обозначается через NG(X).
2. Построить матрицы
инцидентности и смежности
Матрица смежности
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
a
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
b
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
c
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
d
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
e
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
f
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
g
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
Матрица инцидентности:
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
3
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
4
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
5
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
6
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
7
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
8
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
9
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
10
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
11
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
12
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
13
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
. Рассмотреть части графа. Привести
примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх
вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры
пересечения и объединения частей графа.
Граф G:
Цифры (1,2,3,4,5,6,7,8,9,10,11,12,13
- название рёбер)
Не считать рёбра нагруженными.
Суграф-часть графа,
образованная удалением из исходного графа некоторых рёбер. Количество вершин
графа и суграфа одинаково (если в графе G
есть изолированная вершина q,
не инцидентная ни одному ребру, покрывающие суграфы этого графа не существуют).
Пример суграфа
Пример накрывающего
суграфа
Часть графа,
сохраняющего все дуги, инцидентные выделенным вершинам графа G (исходного графа), называют подграфом, порождённым графом G.
Подгаф, состоящий из
трёх вершин:
(f, e, q); (f, a, e); (e, a, q); (q, c, d); (d, b, c); (q, d, e) - в данном графе G можно найти 7 подграфов состоящих
из трёх вершин.
Объединение: (f, a, q)(f, e, q)
Пересечение
4. Привести примеры
циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл
Циклом в неориентированном графе
называется цепь, у которой совпадают начало и конец. Цикл будет называться
простым, если в нём нет одинаковых вершин (кроме первой и последней).
Конечная последовательность
необязательно различных рёбер E1…..En называется маршрутом длины n, если существует последовательность
V1……Vn необязательно различных
вершин, что Ei=(Vi-1, Vi).
Маршрут, в котором все рёбра попарно
различны называется цепью.
Маршрут, в котором все вершины
попарно различны называется простой цепью.
В данном графе не может быть
Эйлорова цикла, согласно теореме: Если граф G обладает Эйлоровым циклом, то он
является связным, а все его вершины чётными. В нашем случае четыре вершины
имеют нечётную степень.
(Эйлоров цикл-путь, проходящий по
всем рёбрам графа и притом только по одному разу).
цепь: 1→2→3→4→5→6→7→11→10
простая цепь: a→f→e→d→c→q→a
цикл: a→q→d→e→q→f→a
простой цикл: a→b→c→d→e→f→a
5. Определить центр, диаметр и
радиус графа.
Диаметром связного графа называется максимально возможное расстояние между
двумя его вершинами.
Центром графа называется такая вершина, что максимальное расстояние между
ней и любой другой вершиной является наименьшим из всех возможных; это
расстояние называется радиусом графа.
Чтобы определить центры, радиус,
диаметр графа G, найдем матрицу D(G) расстояний между вершинами
графа. Определим r(i)=max d (i, j), где i, j вершины графа.
|
a
|
b
|
c
|
d
|
e
|
f
|
q
|
a
|
0
|
1
|
2
|
2
|
1
|
1
|
1
|
b
|
1
|
0
|
1
|
1
|
2
|
2
|
2
|
c
|
2
|
1
|
0
|
1
|
2
|
2
|
1
|
d
|
2
|
1
|
1
|
0
|
1
|
2
|
1
|
e
|
1
|
2
|
2
|
1
|
0
|
1
|
1
|
f
|
1
|
2
|
2
|
2
|
1
|
0
|
1
|
q
|
1
|
2
|
1
|
1
|
1
|
1
|
0
|
(a)=2; r(b)=2; r(c)=2;
r(d)=2; r(e)=2; r(f)=2; r(q)=2;
Минимальное из полученных чисел
является радиусом графа G, максимальное - диаметром графа G.
В нашем случае:
R=2;
D=2;
Центрами являются все вершины.
Считая граф ориентированным,
определить
. Степени вершин
Ребро
графа называется ориентированным, если одну вершину считают началом
ребра, а другую - концом.
Граф, все ребра которого
ориентированы, называется ориентированным графом.
Одна и та же вершина
ориентированного графа может служить началом для одних ребер и концом для
других. Соответственно различают две степени вершины: степень выхода и
степень входа.
Степенью выхода
вершины А ориентированного графа называется число выходящих из А ребер
(обозначение: d+(A)).
Степенью входа вершины А
ориентированного графа называется число входящих в А ребер (обозначение:
d - (A)).
d+(a)=3; d -
(a)=1;+(b)=1; d - (b)=2;+(c)=1; d - (c)=2;+(d)=3; d - (d)=1;+(e)=1; d -
(e)=3;+(f)=2; d - (f)=1;+(q)=2;
d - (q)=3;
7. Матрицы инцидентности и смежности
Матрица смежности
|
a
|
b
|
d
|
e
|
f
|
q
|
a
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
b
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
c
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
d
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
e
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
f
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
q
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
Матрица инцидентности:
|
a
|
b
|
c
|
d
|
e
|
f
|
q
|
1
|
1
|
-1
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
-1
|
-1
|
0
|
0
|
0
|
0
|
3
|
0
|
0
|
-1
|
1
|
0
|
0
|
0
|
4
|
0
|
0
|
0
|
1
|
-1
|
0
|
0
|
5
|
0
|
0
|
0
|
0
|
-1
|
1
|
0
|
6
|
-1
|
0
|
0
|
0
|
0
|
1
|
0
|
7
|
1
|
0
|
0
|
0
|
-1
|
0
|
0
|
8
|
0
|
0
|
0
|
0
|
0
|
-1
|
1
|
9
|
0
|
1
|
0
|
-1
|
0
|
0
|
0
|
10
|
0
|
0
|
-1
|
0
|
0
|
0
|
1
|
11
|
0
|
0
|
0
|
0
|
1
|
0
|
-1
|
12
|
0
|
0
|
0
|
1
|
0
|
0
|
-1
|
13
|
1
|
0
|
0
|
0
|
0
|
0
|
-1
|
. Привести примеры пути,
ориентированной цепи, простой цепи, контура, цикла и простого цикла
Путём в ориентированном
графе от вершины A1 к вершине An называется последовательность ориентированных рёбер A1, A2…..An, в которой конец каждого предыдущего ребра совпадает с началом
следующего и каждое ребро в этой последовательности встречается только один
раз.
1. a→b→d→q→c - простая цепь
2. b→d→e→q→c-простая цепь
3. a→b→d→e→q→f→e - цепь
Ориентированным циклом
называется замкнутый путь в ориентированном графе:
1. a→b→d→q→f→a - простой цикл
2. a→q→c→b→d→q→f→a - цикл
цикл цепь, у которой конечная и начальная вершины совпадают.
Простой цикл не содержит повторяющихся вершин.
Контур - путь, у которого начальная и конечная вершина совпадают.
Простой контур не содержит повторяющихся вершин.
Контур может включать петли в отличии
от цикла, в нашем случае контур равен циклу.