- •Понятие множества. Способы задания множеств.
- •Операции над множествами. Диаграммы Эйлера-Венна.
- •Алгебра множеств.
- •Кортеж. График. Свойства графиков.
- •Соответствия. Свойства соответствий.
- •Отношения. Свойства отношений. Примеры.
- •Высказывания. Операции над высказываниями.
- •Формы представления высказываний. Примеры.
- •Преобразования высказываний. Примеры.
- •Минимизация высказываний методом Квайна. Пример.
- •Минимизация высказываний с помощью карт Карно. Пример.
- •Понятие графа. Способы задания графа. Пример.
- •Виды графов: эйлеров, полный, планарный, деревья. Примеры.
- •Определение путей в графе. Пример.
- •Приведение графа к ярусно-параллельной форме. Пример.
- •Внутренняя и внешняя устойчивость графа. Ядро графа. Пример.
- •4.9. Множество внешней устойчивости. Ядро графа
- •Поиск минимального остова в графе.
- •Понятие автомата. Виды автоматов.
- •Минимизация автоматов.
- •Переход от автомата Милли к автомату Мура и наоборот.
-
Определение путей в графе. Пример.
a b
g
c
f
e d
Требуемые результаты получаются путем перемножения матриц смежности графа.
M
a b c
d
e f
g a 0 0 1 1 0 0 1 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 1 0 0 0 0 0 e 0 1 0 0 0 0 1 f 0 1 1 1 0 0 0 g 0 0 0 0 0 0 0
М2
a b c d e f g a 0 0 1 1 0 0 1 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 1 0 0 0 0 0 e 0 1 0 0 0 0 1 f 0 1 1 1 0 0 0 g 0 0 0 0 0 0 0 М2
|
a |
b |
c |
d |
e |
f |
g |
a |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
c |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
d |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
e |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
f |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
g |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
М
|
a |
b |
c |
d |
e |
f |
g |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
a |
0 |
1 |
0 |
0 |
0 |
0 |
1
a b c
d
e f
g a 0 1 0 0 0 0 0 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 f 0 1 0 0 0 0 0 g 0 0 0 0 0 0 0
М4 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
c |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
d |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
f |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
g |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
М3
Матрица M2 дает все пути длиной в 2
Матрица Мn - пути длиной в n.
Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц
M* = M1 M2 M3 ...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.