связного неориентированного
связного неориентированного графа G=<V,E> каждое дерево <V,T>, где T?E называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами.
Примечание. Понятие цикла будет дано позже. В данной теме ограничимся его интуитивным пониманием.
Число различных каркасов полного связного неориентированного помеченного графа с N вершинами было найдено впервые Кэли и равно N(N-2).
Пример. Граф и его каркасы.
Поиск стягивающего дерева (каркаса). Рассмотрим два алгоритма нахождения каркасов (одного), основанных на методах просмотра графа поиском в глубину и в ширину. Граф описывается матрицей смежности A, массив Nnew (array[1..N] of boolean) служит для хранения признаков. Значение Nnew[i], равное true, говорит о том, что вершина с номером i еще не просмотрена. Для хранения ребер, образующих каркас, будем использовать структуру данных Tree (array[1..2,1..N] of integer).
Известно, что как при поиске в глубину, так и при
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
