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

В математике бинарное отношение на множестве называется антисимметричным, если для каждой пары элементов множества выполнение отношений и влечёт . Бинарное отношение на множестве называется несимметричным, если для каждой пары элементов множества одновременное выполнение отношений и невозможно.

Пример антисимметричного отношения – отношение £: действительно, если а £ в и в£ а, то а=в. Нетрудно убедится в том, что отношение R симметрично тогда и только тогда, когда R=R-1.

Отношение R называется антитранзитивным, если транзитивность отсутствует для любых троек элементов:

Антитранзитивное отношение — отношение победить в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить. Антитранзитивность совпадает с нетранзитивностью.

Антисимметричная:

-1
-1	-1
-1	-1	-1
-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1	-1

Граф. Виды графа. Способы обозначения. Примеры.

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

ОCНОВНЫЕ виды графов:!!!

Граф, или неориентированный граф — это упорядоченная пара , где — это не пустое множество вершин или узлов, а — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Ориентированный граф (сокращённо орграф) — это упорядоченная пара , где — непустое множество вершин или узлов, и — множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Смешанный граф — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой , где , и определены так же, как выше. [Рисунок]

- связным, если для любых вершин , есть путь из в . [Рисунок]

- сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь. [Рисунок]

- полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. [Рисунок]

- Граф, имеющий конечное множество вершин называют конечным.

- Граф, не имеющий ребер, называется пустым. [Рисунок]

- взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра. [Рисунок]

- деревом, если он связный и не содержит нетривиальных циклов. [Рисунок]

13. Матрицы смежности и трансцендентности [скорее инцидентности!?].

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

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

1. Неориентированный граф

a. 1 – вершина инцидентна ребру

b. 0 – вершина не инцидентна ребру

2. Ориентированный граф

a. 1 – вершина инцидентна ребру, и является его началом

b. 0 – вершина не инцидентна ребру

c. -1 – вершина инцидентна ребру, и является его концом

Построим матрицу инцидентности сначала для неориентированного графа, а затем для орграфа.

 

Ребра обозначены буквами от a до e, вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями.

 

14. Расчёт сетевого графика. (!)

Обозначим:

t p - ранний срок наступления события;

t n ­- поздний срок наступления события;

t i j­ - время операций;

i - номер предшествующего события;

j - номер последующего события;

R п - полный резерв времени операции (i, j);

R - резерв времени события;

t p o - ранний срок окончания операции (i, j);

t п о - поздний срок окончания операции (i, j);

 

Пример. В таблице записаны работы (i, j) и время их выполнения tij;

 

i, j	1, 2	1, 3	2, 3	2, 5	3, 4	3, 6	4, 5	4, 6	4, 7	5, 7	6,7
tij

 

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

 

РЕШЕНИЕ По данным работам i, j строим сетевой график. Событий всего 7, значит рисуем 7 вершин. Надо так расположить вершины, чтобы работы i, j не пересекались.

 

 

27

2 4 5 2

2 1 29 10

3

2 12 39

7 0

0 15 39

1 0 5 4 2 5

0 17 8

7 8

8 8

3 0 23 31

8 6 0

t _p 31

N R

t _n