Каркасы и изоморфизм деревьев

Каркас неориентированного графа

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

Задача о построении кратчайшей связывающей сети встречается в различных приложениях достаточно часто.

Нахождение каркасов в графе

Алгоритм нахождения каркаса на основе поиска в глубину.

Вход.	Связный граф $$G(V,E)$$, заданный списками 
   смежности ЗАПИСЬ $$[{v}],\ v \in V$$.
Выход.	Каркас $$(V,T)$$  графа $$G$$.
Процедура	WGD ( $$G$$: граф; $$v$$: вершина)
//поиск в глубину, с нахождением ребер дерева; 
   переменные НОВЫЙ, ЗАПИСЬ, $$T$$  — глобальные//
Шаг 1. 	НОВЫЙ $$[{v}]={ложь}$$ ;
Шаг 2. 	Для $$u \in$$ (ЗАПИСЬ $$[v]$$  цикл
Шаг 3. 	если НОВЫЙ[ $${u}$$ ] то // $$({v},{u})$$  — новое ребро//
Шаг 4. $$T= T \cup \{(v,u)\}$$ ;
Шаг 5. $$WGD(u)$$ ;
	все
все;
Шаг 6.	Начало //главная программа//
Шаг 7.	Для $$u(V$$  цикл НОВЫЙ $$[{v}] = \t{истина все}$$ ;
Шаг 8. $$T=\oslash$$  //множество найденных к этому моменту ребер//
Шаг 9. $$WGD(r)$$ ; // $$r$$  — произвольная вершина графа//
	все
конец.

Алгоритм нахождения каркаса на основе поиска в ширину.

Вход.	Связный граф $$G(V,E)$$, представленный списками 
  смежности ЗАПИСЬ $$[{v}]$$, $$v(V)$$.
Выход.	Каркас $$(V,T)\ (V,T)$$  графа $$G$$.
Процедура	КАРКАС( $${G}$$: граф; $${v}$$: вершина)
Шаг 1.	для $$u \in V$$  цикл НОВЫЙ[u]=истина все; //инициализация//
Шаг 2. $$T=\oslash$$ ; // — множество найденных к этому моменту ребер//
Шаг 3.	ОЧЕРЕДЬ $$= \oslash$$ ; ОЧЕРЕДЬ $$\Leftarrow r$$ ; //корень каркаса//
Шаг 4.	НОВЫЙ $$[{r}]= \t{ложь}$$ ;
Шаг 5.	Пока ОЧЕРЕДЬ $$\ne \oslash$$  цикл
Шаг 6. $${v} \Leftarrow$$  ОЧЕРЕДЬ;
Шаг 7.	Для $${u}\in$$ ЗАПИСЬ $$[v]$$  цикл
Шаг 8.	если НОВЫЙ $$[{u}]$$  то // $$(v, u)$$  — новое ребро//
Шаг 9.	ОЧЕРЕДЬ $$\Leftarrow u$$ ;
Шаг 10.	НОВЫЙ $$[{u}]= \t{ложь}$$ ;
Шаг 11. $$T= T \cup \{v, u)\}$$ 
			все
		все
	все
все.

Алгоритм Краскала

Вход.	Неориентированный граф $$G=(V, E)$$  с функцией 
  стоимости ребер $$c$$.
Выход.	Оптимальный каркас $${T}=(V,S)$$.
Метод
Процедура Оптимальный каркас ( $$G$$: граф) $$=$$ 
Шаг 1. $$S = \oslash$$ 
Шаг 2. $$VS = \oslash$$ 
Шаг 3.	Построить очередь с приоритетами $$Q$$, 
   содержащую все ребра из $$E$$ ;
Шаг 4.	Для всех $$v$$  из $$T$$  цикла  добавить $$\{v\}$$  к $$VS$$  все;
Шаг 5.	Пока $$|{VS}|> 1$$  цикл
Шаг 6.	Выбрать в $$Q$$  ребро $$(v, w)$$  наименьшей стоимости;
Шаг 7.	удалить ( $$v, w$$ )  из $$Q$$ ;
Шаг 8.	Если $$v$$  и $$w$$  принадлежат 
   различным множествам $$W_1$$  и $$W_2$$  из $$VS$$ 
Шаг 9.	То заменить $$W_1$$  и $$W_2$$  на $$W_1 \cup W_2$$  в $$VS$$:
Шаг 10.	добавить $$(v,w)$$  к $$S$$ 
		все
	все
все.

Пример.

Найдите оптимальный каркас для графа, приведенного на (рис.12.1).

Изоморфизм деревьев

Два графа $$G$$ и $$H$$ изоморфны (записывается $$G \cong H$$ или иногда $${G = H}$$ ), если между множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность.

Инвариант графа $$G$$ — это число, связанное с $$G$$, которое принимает одно и то же значение на любом графе, изоморфном $$G$$. Полный набор инвариантов определяет граф с точностью до изоморфизма.

Пусть дерево $$T=(V,E)$$ и его $$P(e,v,w)$$ инцидентор, т.е. предикат, равный единице в том и только в том случае, когда ребро $$e$$ инцидентно вершинам $$v$$ и $$w$$.

Дерево $$T_1=(V_1,E_1)$$ называется изоморфным дереву $${T}_2=(V_2,E_2$$ ), если между вершинами деревьев, а также между их ребрами можно установить взаимно однозначное соответствие $$V_1 \Leftrightarrow V_2$$ и $$E_1 \Leftrightarrow E_2$$, сохраняющее инцидентор, т.е. такое, что $$(\forall v,w \in V_1)$$ $$(\forall v',w' \in V_2$$ $$(\forall e \in E_1)$$ $$(\forall e' \in E_2)$$ ( $$v \Leftrightarrow v'$$ $$\$$ $$w \Leftrightarrow w'$$ $$\$$ $$e \Leftrightarrow e' \Rightarrow [P_1(e,v,w)] = P_2(e',v',w')$$ ).

Другими словами, два дерева изоморфны, если между их вершинами можно установить взаимно однозначное соответствие, сохраняющее отношение инцидентности (смежности).

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

Пример изоморфных деревьев: нетрудно заметить, что они отличаются лишь способом представления (например, способом изображения на плоскости).

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

Изоморфное отображение дерева $$T$$ на себя называется автоморфизмом дерева. Совокупность всех автоморфизмов дерева $$T$$, обозначаемая $$\Gamma(T)$$, образует группу, называемую группой дерева $$T$$. Таким образом, элементы группы $$\Gamma(T)$$ являются подстановками, действующими на множестве вершин $$V$$. Порядок $$s(T)$$ группы $$\Gamma(T)$$ есть число симметрий дерева $$T$$.

Дерево $$T$$ называется асимметричным, если его группа автоморфизмов есть единичная группа, т.е. $$s(T)=1$$.

Примеры асимметричных деревьев порядка 7, 8, 9.

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

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