- •Понятие множества. Способы задания множеств.
- •Операции над множествами. Диаграммы Эйлера-Венна.
- •Алгебра множеств.
- •Кортеж. График. Свойства графиков.
- •Соответствия. Свойства соответствий.
- •Отношения. Свойства отношений. Примеры.
- •Высказывания. Операции над высказываниями.
- •Формы представления высказываний. Примеры.
- •Преобразования высказываний. Примеры.
- •Минимизация высказываний методом Квайна. Пример.
- •Минимизация высказываний с помощью карт Карно. Пример.
- •Понятие графа. Способы задания графа. Пример.
- •Виды графов: эйлеров, полный, планарный, деревья. Примеры.
- •Определение путей в графе. Пример.
- •Приведение графа к ярусно-параллельной форме. Пример.
- •Внутренняя и внешняя устойчивость графа. Ядро графа. Пример.
- •4.9. Множество внешней устойчивости. Ядро графа
- •Поиск минимального остова в графе.
- •Понятие автомата. Виды автоматов.
- •Минимизация автоматов.
- •Переход от автомата Милли к автомату Мура и наоборот.
-
Приведение графа к ярусно-параллельной форме. Пример.
Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ), если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
a
h b
g c
f d
e
|
a |
b |
c |
d |
e |
f |
g |
h |
a |
|
|
1 |
|
|
|
|
|
b |
|
|
|
|
|
|
|
|
c |
|
1 |
|
|
|
|
|
|
d |
|
|
|
|
1 |
|
|
1 |
e |
1 |
|
|
|
|
|
1 |
|
f |
|
|
1 |
|
|
|
|
|
g |
|
1 |
1 |
|
|
|
|
|
h |
1 |
|
|
|
|
1 |
|
|
Алгоритм приведения к ЯПФ:
0. Строим матрицу смежности графа.
1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.
2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.
3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.
4. Прорисовываются дуги.
В результате, вышеприведенный граф примет вид:
d
e h
g f
a
c
b
Ширина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.