WikiSort.ru - Не сортированное

Выбор начальной вершины

Для получения хороших результатов необходимо найти периферийную вершину графа ${\displaystyle (V,E)}$ . Эта задача в общем случае является достаточно трудной, поэтому вместо неё обычно ищут псевдопериферийную вершину с помощью одной из модификаций эвристического алгоритма Гиббса и др.

Для описания алгоритма вводится понятие корневой структуры уровней (англ. rooted level structure). Для заданной вершины ${\displaystyle v}$ структурой уровней с корнем в ${\displaystyle v}$ будет разбиение ${\displaystyle {\mathcal {L}}}$ множества вершин ${\displaystyle V}$ :

${\displaystyle {\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\},}$

где подмножества ${\displaystyle L_{i}(v)}$ определены следующий образом:

${\displaystyle L_{0}(v)=\{v\},}$

${\displaystyle L_{1}(v)=\operatorname {Adj} (L_{0}(v))}$

и

${\displaystyle L_{i}(v)=\operatorname {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l(v).}$

Алгоритм нахождения псевдопериферийной вершины^[3]:

1. выбрать произвольную вершину ${\displaystyle r}$ из ${\displaystyle V}$ ;
2. построить структуру уровней для корня ${\displaystyle r}$ : ${\displaystyle {\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots ,L_{l(r)}(r)\}}$ ;
3. выбрать вершину с минимальной степенью ${\displaystyle v}$ из ${\displaystyle L_{l(r)}(r)}$ ;
4. построить структуру уровней для корня ${\displaystyle v}$ : ${\displaystyle {\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}}$ ;
5. если ${\displaystyle l(v)>l(r)}$ , то присвоить ${\displaystyle r:=v}$ и перейти к шагу 3;
6. вершина ${\displaystyle v}$ является искомой псевдопериферийной вершиной.