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

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

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

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

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

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

Граф 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)=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. Матрицы инцидентности и смежности

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

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

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

Путём в ориентированном графе от вершины 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 - цикл

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

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

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

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

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