Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Решение задач сервиса с использованием деревьев

Покрывающее дерево

Рассмотрим сайт предприятия сервиса, состоящий из п страниц. На каждой странице есть гиперссылки на другие страницы. Можно ли просмотреть все страницы, переходя по ссылкам, начиная с домашней страницы?

Чтобы решить эту задачу, необходимо построить для полученного графа покрывающее дерево. Поставим в соответствие каждой странице вершину графа и соединим две вершины ребром, если на данной странице есть гиперссылка на другую страницу; обратный переход всегда возможен средствами браузера. Если граф не содержит ни одного покрывающего дерева, то он не будет связным и поэтому невозможно путем перехода по ссылкам просмотреть все страницы сайта.

Решение задачи простым перебором займет очень много времени: даже при небольшом п = 9, согласно формуле (2.1), число возможных деревьев больше миллиона.

Разработаны специальные алгоритмы построения покрывающего дерева [19,21,31]. Суть их заключается в просмотре в произвольном порядке ребер исходного графа. При каждом просмотре в отношении соответствующего ребра принимается решение о том, будет или не будет оно включено в покрывающее дерево. Если ребро не образует цикл с уже включенными в дерево ребрами, то оно включается в дерево, в противном случае — нет. Построение покрывающего дерева завершается, когда число ребер, включенных в дерево, становится равным числу вершин рассматриваемого графа минус единица.

Если необходимо построить все остовные деревья графа, используется алгоритм элементарных преобразований остовов, начиная с некоторого Г0; при этом на каждом следующем шаге для преобразования привлекается только последнее из полученных остовных деревьев [19]. Некоторые алгоритмы основаны на преобразовании матрицы инцидентности в линейную конфигурацию.

Граф для нахождения всех остовов

Рис. 2.6. Граф для нахождения всех остовов

Использование линейной конфигурации. Рассмотрим граф, изображенный на рис. 2.6. Матрица инцидентности графа имеет вид

Вычислим по теореме 2.1 число остовов графа. Для этого образуем матрицу линейной конфигурации S3, придав дугам графа произвольную направленность и удалив из матрицы инцидентности А последнюю строку:

Вычисляя определитель произведения матриц [28], получаем 8 остовов для графа на рис. 2.6:

Для получения всех остовов необходимо найти все миноры, для чего перебрать все возможные Сптх сочетания из столбцов матрицы S3:

Миноры матрицы S3 имеют вид

Чтобы выяснить, является ли данный граф остовом (деревом), воспользуемся теоремой 2.2, согласно которой, если (я, п — 1) граф является деревом, то модуль любого минора порядка п1 матрицы инцидентности этого графа равен 1 и равен 0, если граф не является деревом.

В результате вычисления модуля найденных миноров получим:

Так как ребра ех, е2, е3 и е3, е4, е5 образуют цикл, поэтому миноры Mj и М10 равны нулю. Остальным минорам соответствуют ос- товные деревья графа. Так, минору М2 отвечает дерево, состоящее из ребер eh е2, е4.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>