- •16. Типы конечных графов
- •Типы конечных графов
- •Матрицы смежности и инцидентности
- •Изоморфизм графов общего вида
- •Признаки непланарных графов
- •Алгоритм поиска в глубину
- •Реализация
- •Способы построения матрицы достижимости [править]Перемножение матриц
- •[Править]Случай нескольких путей
- •Каркас неориентированного графа
- •Формулировка
- •[Править]Оценка
- •Обозначения
- •[Править]Псевдокод
- •[Править]Описание
- •[Править]Доказательство корректности
- •Неформальное описание
- •[Править]Формальное описание
- •Основные определения
- •Классификация автоматов по логическим свойствам функций переходов и выходов
- •[Править]Автомат Мили
- •[Править]Автомат Мура
- •Форма компактного представления, применяемая во время выполнения
- •Реализация компактного представления
- •Анализ конечных автоматов.
- •Описание
- •Алгоритм симплекс-метода [править]Усиленная постановка задачи
- •[Править]Алгоритм
- •Модели вычислений
- •Описание
- •Устройство машины Тьюринга
- •[Править]Описание машины Тьюринга
- •Условия применимости
- •[Править]Принцип жадного выбора
- •[Править]Оптимальность для подзадач
Реализация
Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.
--------21. Матрица связности, тоже самое что и матрица смежности.
Матрица достижимости простого ориентированого графа — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Способы построения матрицы достижимости [править]Перемножение матриц
Пусть дан простой граф , матрица смежности которого есть , где . Матрица смежности даёт информацию о всех путяхдлины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения с самим собой:
.
По определению, матрица композиции отношений есть , где —конъюнкция, а — дизъюнкция.
После нахождения матриц композиций для всех , будет получена информация о всех путях длины от до . Таким образом, матрица есть искомая матрица достижимости.
[Править]Случай нескольких путей
Если булевы операции дизъюнкции и конъюнкции заменить обычными алгебраическими операциями сложения и умножения соответственно, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.
Граф
Матрица контрдостижимости Q = [ qij], i, j =1, 2, ... n, где n – число вершин графа, определяется следующим образом:
qij=1, если из вершины xj можно достичь вершину xi ,
qij=0, в противном случае.
Контрдостижимым множеством Q (xi) является множество таких вершин, что из любой вершины этого множества можно достичь вершину xi . Аналогично построению достижимого мно-жества R (xi) можно записать выражение для Q (xi):
.
Таким образом, видно, что Q (xi) – это есть не что иное как обратное транзитивное замыкание вершины xi , т. е. Q (xi) = Т-xi). Из определений очевидно, что столбец xi матрицы Q (в котором qij=1, если , и qij=0 в противном случае) совпадает со строкой xi матрицы R, т. е. Q = RT,где RT – матрица, транспонированная к матрице достижимости R.
Рис. 4.1. Достижимость в графе: а –граф; б – матрица смежности; в – матрица достижимости; г- матрица контрдостижимости.
-------22. Граф и его каркасы
Каркас неориентированного графа
Оптимальным каркасом взвешенного графа называется каркас, минимизирующий некоторую функцию от весов входящих в него ребер. Чаще всего в качестве такой функции выступает сумма весов ребер, реже — произведение. Оптимальный каркас еще называют кратчайшей связывающей сетью для данного графа.
Задача о построении кратчайшей связывающей сети встречается в различных приложениях достаточно часто.
ПОСТРОЕНИЕ ПОИСКОМ В ГЛУБИНУ И ШИРИНУ СМ ВОПРОС 19, 20
-------23. Минимальный каркас (или Каркас минимального веса, Минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
Алгоритм Крускала (или алгоритм Краскала)