Исследование графов

Задание № 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

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

1. Локальные степени и окружения каждой вершины в виде структуры смежности;

2. Построить матрицы инцидентности и смежности;

3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;

4. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;

5. Определить центр, диаметр и радиус графа.

Считая граф ориентированным, определить

6. Степени вершин

7. Матрицы инцидентности и смежности.

8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.

1 Решение:

Степени вершин:

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. Построить матрицы инцидентности и смежности

Матрица смежности

Матрица инцидентности:

3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа.

Граф 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 вершины графа.

r (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;

Центрами являются все вершины.

Считая граф ориентированным, определить

6. Степени вершин

Ребро графа называется ориентированным, если одну вершину считают началом ребра, а другую — концом.

Граф, все ребра которого ориентированы, называется ориентированным графом.

Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.

Степенью выхода вершины, А ориентированного графа называется число выходящих из, А ребер (обозначение: d+(A)).

Степенью входа вершины, А ориентированного графа называется число входящих в А ребер (обозначение: d — (A)).

d+(a)=3; d — (a)=1;

d+(b)=1; d — (b)=2;

d+(c)=1; d — (c)=2;

d+(d)=3; d — (d)=1;

d+(e)=1; d — (e)=3;

d+(f)=2; d — (f)=1;

d+(q)=2; d — (q)=3;

7. Матрицы инцидентности и смежности Матрица смежности

Матрица инцидентности:

8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла Путём в ориентированном графе от вершины 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 — цикл

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

Простой цикл не содержит повторяющихся вершин.

Контур — путь, у которого начальная и конечная вершина совпадают.

Простой контур не содержит повторяющихся вершин.

Контур может включать петли в отличии от цикла, в нашем случае контур равен циклу.