Орграф (ориентированный граф)

Все рёбра имеют направленность.

Орграф D состоит из конечного множества вершин V и набора упорядоченных пар (U, v) различных вершин.

Любая такая пара (U, v) называется дугой или ориентированным ребром. Дуга идёт от U к v и называется инцидентна вершинам U и v. Говорят, что вершина U смежна к вершине v, а вершина v смежна из вершины U.

Полустепенью из входа вершины v(od(v)) называется число вершин смежных из v, а полустепенью захода idv – число вершин смежных к v. В одном случае =1, а в другом = 2.

Маршрут – представляет чередующуюся последовательность вершин и рёбер.

Путь – маршрут, в котором все вершины различны.

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

Если существует путь из вершины U в вершину v, то говорят, что v достижима из U. Расстоянием называется длина кротчайшего пути.

Орграф – называется сильно связанным или сильным, если любые две вершины взаимно достижимы.

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

Граф называется слабым, если любые две вершины соединены полупутём, т.е. не имеет значения направленных дуг – полупуть.

Орграф называется несвязанным, если он даже не слабый.

ТЕОРЕМА: орграф сильный тогда и только тогда, когда он имеет остовный замкнутый маршрут, односторонний «когда он имеет остовный полупуть.

31. Матрицы смежности, инцидентности, достижимости, расстояний.

Матрица смежности — один из способов представления графа в виде матрицы.

Определение:

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу ребёр из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

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

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют вершинам, строки — ребрам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Матрица достижимости простого ориентированого графа G = (V,E) — бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Пусть задан неориентированный граф G(V, Q).

Матрица расстояний - это квадратная матрица порядка n, где n - число вершин.

Dnґn = 7dij7; dij= м

н

о d(vi, vj), если $ цепь, соединяющая vi и vj

Ґ, если ± цепь, соединяющая vi и vj

d(vi, vj) - длина кротчайшей цепи от vi до vj.

Алгоритм Флойда-Уоршолла нахождения матрицы расстояний D по матрице смежности A

Итерационно находим D(0), D(1),..., D(n).

1. Получаем D(0): dij(0)= м

н

о 0, если i=j

Ґ, если aij=0 и i№j

aij в противном случае

2. D(k): dij(k)=min{dij(k-1), dik(k-1)+dkj(k-1)}

3.D=D(n).

32. Коциклы.

Коцикл — минимальный разрез, минимальное множество ребер, удаление которого делает граф несвязным. 1-коцикл Чеха

· Отображения перехода удовлетворяют условию 1-коцикла Чеха:

Если , то .

Коциклы называются когомологичными, если они лежат в одной орбите этого действия.

— коцикл, обозначает - умножение гомологических и когомологических классов можно ввести понятия коциклов Zk(X,G) = Kerδk.

33. Матрица циклов. Матрица коциклов. Коциклический ранг. Циклический ранг.

Пусть G – граф у которого помечены рёбра и простые циклы.

Изобразим какой-либо граф и опишем его с помощью циклов в виде матрицы.

Матрица || aj || называется матрицей циклов в которой для каждого простого цикла графа есть строка и для каждого ребра столбец. Причём || Сij|| = 1 т.е. элемент = 1, если i – цикл содержит j – ребро и равен нулю в противном случае.

U1 U2 U3 U4 U5 U6 U7 U8

1| 1 1 1 0 0 0 0 0

2| 0 0 1 1 1 1 0 0

3| 0 0 0 0 1 0 1 1

|| cij|| =4| 1 1 0 1 1 1 0 0

5| 0 0 1 1 0 1 1 1

6| 1 1 0 1 0 1 1 1

Матрица позволяет решать практические задачи.

р – м циклы:

1 цикл включает ребра {U1, U2, U3}

2 цикл включает рёбра {U3, U4, U6, U5}

3 цикл включает рёбра {U5, U7, U8}

4 цикл включает рёбра {U1, U4, U2, U6, U5}

5 цикл включает рёбра {U3, U4, U7, U8, U6}

6 цикл включает рёбра {U1, U4, U7, U8, U6, U2}

В отличие от матрицы смежности матрица циклов не определяет граф с точностью до изоморфизма.

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

Подграф нрафа G состоящий из кодерева и одной ветви дерева содержит 1 – коцикл (разрез графа).

ТЕОРЕМА 1: коциклический ранг связанного графа G равен числу коциклов в базисе пространства коциклов графа G.

Данный ранг у нас равен 5. Кодерево Т* остова Т в связанном графе G – подграф в графе G содержащий только те рёбра графа которые Î остову ребра графа Т остова называемым ветвями графа, рёбра графа Т* называются хордами.

ТЕОРЕМА 2: коциклический ранг связанного графа G равен числу рёбер любого его остова.

Следствие 1: если G – связанный граф, имеющий р -вершин и q -рёбер, то коциклический ранг равен: m (G) p = 1 определяется количеством вершин – 1 будет ветви дерева.

Следствие 2: если G граф имеет р -вершин и q -рёбер состоящий из k -компонент связанности, то коциклический ранг определяется как m(G) = p – k

ТЕОРЕМА 3: циклический ранг равен числу хорд кодерева.

Следствие 1: циклический ранг обозначенный m*(G) равен числу рёбер + число вершин + 1.

M*(G) = q - p + 1

Следствие 2: если граф G имеет р -вершин и q -рёбер и имеет k компонент связанности, то

M*(G) = q – p + k

34. Дифференцирование графов.

Пусть задан граф abced. Определить, сколько можно построить.

a – 5 ab -2

b – 5 bc - 2

c – 4 dc - 2

d – 5

e – 5

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

Ещё более полно частота пары рёбер определяется степенью неравномерности участия пар рёбер остова графа.

Производная графа, т.е. графа G по событию S называется неориентированный взвешенный граф <V, (U, P)> носитель которого совпадает с носителем модели определяемой этим событием и пара вершин (vi, vj) взвешены отношением их несовместного участия к частоте fij – совместного участия в событии Si.

Производную определяет следующее выражение:

Значение производной называется значение производной на ребре vi, vj.

Пример: событие S является образованием множества рёбер графа остова, а условиями вхождения рёбер графа в данное множество.

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

Далее определяется частотная матрица

Для данного примера события представляют собой образование ребрами остова графа. Найти производную по событию S. Каждое событие определяет модель j с матрицей Q(j), в которой определены условия формирования модели. Эти условия могут быть буквами модели, а совокупность условий словами модели, т.е. производную можно интерпретировать на условном понятии букв и их вхождений в слова моделей.

Для определения производной от графа G по событию S необходимо:

1. построить модель определяемую данным событием (матрицу Q).

2. Найти данную матрицу отношений F.

3. Вычислить значение производной на рёбрах графа G.

4. Построить граф.

Пример:

8 вариантов остовов

		a	b	c	d	e
Q =

1. транспонируем матрицу

A
B
C
D
e

Частотная матрица

		a	b	c	d	e
	A
	B
F =	C
	D
	E

Вычисляем значение произведения

Элементы 4М означают, что производная графа соответственно по ребру (vi, vj)

35. Булева алгебра. Теоремы булевой алгебры.

Булевой алгеброй называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

36. Начальные основы алгебры логики. Основные операции алгебры логики.

1. Логика – это наука о формах и способах мышления. Одной из основных форм мышления является высказывание.

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.

Алгебру логики называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения.

Алгебра логики оперирует с высказываниями. Высказывание – это предложение, относительно которого имеет смысл говорить истинно оно или ложно

Например: Париж – столица Франции. (истина)

4<3. (ложно)

Высказывания принято обозначать большими буквами латинского алфавита: A, B, C…X, Y и т.д.

Если высказывание С истинно, то пишут С=1, а если оно ложно, то С=0.

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

3. Рассмотрим основные логические операции: конъюнкцию, дизъюнкцию и инверсию.

4. Конъюнкция (логическое умножение)

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

Запишите таблицу истинности для конъюнкции.

A B A&B

0 0 0

0 1 0

1 0 0

1 1 1

Эту операцию принято обозначать A&B. Сложное высказывание A&B истинно только в том случае, когда истинны оба входящих в него высказывания.

Например: 2 х 2=5 и 3 х 3 =10

2 х 2=5 и 3 х 3 =9

2 х 2=4 и 3 х 3 =10

2 х 2=4 и 3 х 3 =9

Из приведенных ниже четырех высказываний истинно только четвертое.

Дизъюнкция (логическое сложение)

Соединение двух (или нескольких) высказываний с помощью союза ИЛИ называется операцией логического сложения или дизъюнкцией.

Запишите таблицу истинности для дизъюнкции.

A B AvB

0 0 0

0 1 1

1 0 1

1 1 1

Эту операцию принято обозначать AvB. Сложное высказывание AvB

истинно, если истинно хотя бы одно из входящих в него высказываний.

Например: 2 х 2=5 или 3 х 3 =10

2 х 2=5 или 3 х 3 =9

2 х 2=4 или 3 х 3 =10

2 х 2=4 или 3 х 3 =9

Из приведенных ниже четырех высказываний ложно только первое.

Инверсия (логическое отрицание)

Присоединение частицы НЕ к данному высказыванию называется операцией отрицания.

Запишите таблицу истинности для инверсии.

A А

0 1

1 0

Эту операцию принято обозначать А. Если высказывание А истинно, то А - ложно и наоборот.

2 х 2 не равно четырем - ложно

2 х 2 равно четырем - истинно

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