Вариант 18

Задача 1. Построение глубинного дерева (d-дерева)

Условие. Построить глубинное дерево (d-дерево) графа $G$, начиная с вершины $1$, считая, что вершины в $\operatorname{list}(v)$ упорядочены по возрастанию номеров.

Массив смежности

$$\begin{aligned} \operatorname{list}(1)&=\{2,3,4,5\}\\ \operatorname{list}(2)&=\{1,3,5,6\}\\ \operatorname{list}(3)&=\{1,2,4,6\}\\ \operatorname{list}(4)&=\{1,3,5,7\}\\ \operatorname{list}(5)&=\{1,2,4,6,9\}\\ \operatorname{list}(6)&=\{2,3,5,7,8,10\}\\ \operatorname{list}(7)&=\{4,6,8,10,11\}\\ \operatorname{list}(8)&=\{6,7,9,11,12\}\\ \operatorname{list}(9)&=\{5,8,10,11,12\}\\ \operatorname{list}(10)&=\{6,7,9,11,12\}\\ \operatorname{list}(11)&=\{7,8,9,10,12\}\\ \operatorname{list}(12)&=\{8,9,10,11\} \end{aligned}$$

---

Решение

Проведём поиск в глубину, начиная с вершины $1$.

Обозначения:

• $T$ — множество древесных рёбер,
• $B$ — множество обратных рёбер,
• $\operatorname{num}$ — массив номеров посещения,
• $\operatorname{father}$ — массив предков,
• $S$ — стек,
• $i$ — следующий номер.

---

Шаг 1 (инициализация)

$$\begin{aligned} \operatorname{num} &:= (1,0,0,0,0,0,0,0,0,0,0,0),\\ \operatorname{father} &:= (0,0,0,0,0,0,0,0,0,0,0,0),\\ S &:= (1),\\ i &:= 2,\\ T &:= \varnothing. \end{aligned}$$

---

Шаг 2

$\operatorname{top}(S)=1$, берём минимальную вершину $2\in \operatorname{list}(1)$ с $\operatorname{num}(2)=0$:

$$\begin{aligned} \operatorname{num}(2)&:=2,\\ i&:=3,\\ T&:=\{\{1,2\}\},\\ \operatorname{father}(2)&:=1,\\ S&:=(1,2). \end{aligned}$$

Состояние после шага 2:

$$\operatorname{num}=(1,2,0,0,0,0,0,0,0,0,0,0),\\ \operatorname{father}=(0,1,0,0,0,0,0,0,0,0,0,0).$$

---

Шаг 3

$\operatorname{top}(S)=2$, берём $3\in \operatorname{list}(2)$ с $\operatorname{num}(3)=0$:

$$\begin{aligned} \operatorname{num}(3)&:=3,\\ i&:=4,\\ T&:=\{\{1,2\},\{2,3\}\},\\ \operatorname{father}(3)&:=2,\\ S&:=(1,2,3). \end{aligned}$$ $$\operatorname{num}=(1,2,3,0,0,0,0,0,0,0,0,0),\\ \operatorname{father}=(0,1,2,0,0,0,0,0,0,0,0,0).$$

---

Шаг 4

$\operatorname{top}(S)=3$, берём $4\in \operatorname{list}(3)$ с $\operatorname{num}(4)=0$:

$$\begin{aligned} \operatorname{num}(4)&:=4,\\ i&:=5,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\}\},\\ \operatorname{father}(4)&:=3,\\ S&:=(1,2,3,4). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,0,0,0,0,0,0,0,0),\\ \operatorname{father}=(0,1,2,3,0,0,0,0,0,0,0,0).$$

---

Шаг 5

$\operatorname{top}(S)=4$, берём $5\in \operatorname{list}(4)$ с $\operatorname{num}(5)=0$:

$$\begin{aligned} \operatorname{num}(5)&:=5,\\ i&:=6,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\}\},\\ \operatorname{father}(5)&:=4,\\ S&:=(1,2,3,4,5). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,0,0,0,0,0,0,0),\\ \operatorname{father}=(0,1,2,3,4,0,0,0,0,0,0,0).$$

---

Шаг 6

$\operatorname{top}(S)=5$, берём $6\in \operatorname{list}(5)$ с $\operatorname{num}(6)=0$:

$$\begin{aligned} \operatorname{num}(6)&:=6,\\ i&:=7,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\}\},\\ \operatorname{father}(6)&:=5,\\ S&:=(1,2,3,4,5,6). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,0,0,0,0,0,0),\\ \operatorname{father}=(0,1,2,3,4,5,0,0,0,0,0,0).$$

---

Шаг 7

$\operatorname{top}(S)=6$, берём $7\in \operatorname{list}(6)$ с $\operatorname{num}(7)=0$:

$$\begin{aligned} \operatorname{num}(7)&:=7,\\ i&:=8,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\}\},\\ \operatorname{father}(7)&:=6,\\ S&:=(1,2,3,4,5,6,7). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,0,0,0,0,0),\\ \operatorname{father}=(0,1,2,3,4,5,6,0,0,0,0,0).$$

---

Шаг 8

$\operatorname{top}(S)=7$, берём $8\in \operatorname{list}(7)$ с $\operatorname{num}(8)=0$:

$$\begin{aligned} \operatorname{num}(8)&:=8,\\ i&:=9,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\}\},\\ \operatorname{father}(8)&:=7,\\ S&:=(1,2,3,4,5,6,7,8). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,8,0,0,0,0),\\ \operatorname{father}=(0,1,2,3,4,5,6,7,0,0,0,0).$$

---

Шаг 9

$\operatorname{top}(S)=8$, берём $9\in \operatorname{list}(8)$ с $\operatorname{num}(9)=0$:

$$\begin{aligned} \operatorname{num}(9)&:=9,\\ i&:=10,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\},\{8,9\}\},\\ \operatorname{father}(9)&:=8,\\ S&:=(1,2,3,4,5,6,7,8,9). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,8,9,0,0,0),\\ \operatorname{father}=(0,1,2,3,4,5,6,7,8,0,0,0).$$

---

Шаг 10

$\operatorname{top}(S)=9$, берём $10\in \operatorname{list}(9)$ с $\operatorname{num}(10)=0$:

$$\begin{aligned} \operatorname{num}(10)&:=10,\\ i&:=11,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\},\{8,9\},\{9,10\}\},\\ \operatorname{father}(10)&:=9,\\ S&:=(1,2,3,4,5,6,7,8,9,10). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,8,9,10,0,0),\\ \operatorname{father}=(0,1,2,3,4,5,6,7,8,9,0,0).$$

---

Шаг 11

$\operatorname{top}(S)=10$, берём $11\in \operatorname{list}(10)$ с $\operatorname{num}(11)=0$:

$$\begin{aligned} \operatorname{num}(11)&:=11,\\ i&:=12,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\},\{8,9\},\{9,10\},\{10,11\}\},\\ \operatorname{father}(11)&:=10,\\ S&:=(1,2,3,4,5,6,7,8,9,10,11). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,8,9,10,11,0),\\ \operatorname{father}=(0,1,2,3,4,5,6,7,8,9,10,0).$$

---

Шаг 12

$\operatorname{top}(S)=11$, берём $12\in \operatorname{list}(11)$ с $\operatorname{num}(12)=0$:

$$\begin{aligned} \operatorname{num}(12)&:=12,\\ i&:=13,\\ T&:=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\},\{8,9\},\{9,10\},\{10,11\},\{11,12\}\},\\ \operatorname{father}(12)&:=11,\\ S&:=(1,2,3,4,5,6,7,8,9,10,11,12). \end{aligned}$$ $$\operatorname{num}=(1,2,3,4,5,6,7,8,9,10,11,12),\\ \operatorname{father}=(0,1,2,3,4,5,6,7,8,9,10,11).$$

---

Завершение

Далее для любой вершины $\operatorname{top}(S)$ не существует $u\in \operatorname{list}(\operatorname{top}(S))$ с $\operatorname{num}(u)=0$ (все вершины уже посещены), поэтому вершины последовательно извлекаются из стека $S$, и алгоритм завершается.

---

Ответ

$$T=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\},\{8,9\},\{9,10\},\{10,11\},\{11,12\}\}.$$ $$B=E_G\setminus T=\{\{1,3\},\{1,4\},\{1,5\},\{2,5\},\{2,6\},\{3,6\},\{4,7\},\{5,9\},\{6,8\},\{6,10\},\{7,10\},\{7,11\},\{8,11\},\{8,12\},\{9,11\},\{9,12\},\{10,12\}\}.$$

Задача 2. Разбиение множества $E_G$ на $l$ цепей

Найти разбиение множества $E_G$ рёбер графа $G$ на $l$ цепей, где $l$ — половина от числа вершин нечётной степени.

---

1) Вершины нечётной степени и число цепей

Определим вершины нечётной степени в графе $G$.
Обозначим их через $u_i$ по возрастанию номеров:

$$u_1=5,\ u_2=7,\ u_3=8,\ u_4=9,\ u_5=10,\ u_6=11.$$

Значит,

$$l=\frac{6}{2}=3,$$

и возможно разбить множество рёбер графа на 3 цепи с концами из множества

$$\{5,7,8,9,10,11\}.$$

---

2) Нумерация рёбер по возрастанию весов

Обозначим рёбра графа $G$ через $e_i$ по возрастанию их весов:

$$\begin{aligned} &e_1=\{1,4\},\ e_2=\{1,2\},\ e_3=\{10,11\},\ e_4=\{5,6\},\ e_5=\{7,8\},\\ &e_6=\{2,5\},\ e_7=\{3,6\},\ e_8=\{8,9\},\ e_9=\{11,12\},\ e_{10}=\{8,11\},\\ &e_{11}=\{6,7\},\ e_{12}=\{1,5\},\ e_{13}=\{6,8\},\ e_{14}=\{5,9\},\ e_{15}=\{6,10\},\\ &e_{16}=\{8,12\},\ e_{17}=\{1,3\},\ e_{18}=\{4,7\},\ e_{19}=\{2,6\},\ e_{20}=\{4,5\},\\ &e_{21}=\{7,10\},\ e_{22}=\{3,4\},\ e_{23}=\{7,11\},\ e_{24}=\{10,12\},\ e_{25}=\{9,10\},\\ &e_{26}=\{9,11\},\ e_{27}=\{2,3\},\ e_{28}=\{9,12\}. \end{aligned}$$

---

3) Добавление фиктивных рёбер

Добавим фиктивные рёбра:

$$f_1=u_1u_2=\{5,7\},\quad f_2=u_3u_4=\{8,9\},\quad f_3=u_5u_6=\{10,11\}.$$

Заметим, что граф $G+f_1+f_2+f_3$ имеет кратные рёбра, так как вершины $8$ и $9$ инцидентны рёбрам $e_8$ и $f_2$, а вершины $10$ и $11$ — рёбрам $e_3$ и $f_3$. Будем это учитывать при построении эйлеровой цепи.

---

4) Построение эйлеровой цепи (стековый алгоритм)

Шаг 1. (инициализация)

$$\begin{aligned} &SW_{ork}=(1).\\[2mm] &\text{listW}= \bigl[\,[2,3,4,5],\ [1,3,5,6],\ [1,2,4,6],\ [1,3,5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

Пока $SW_{ork}$ непуст, выполняем:

---

Шаг 2.

Вершиной стека $SW_{ork}$ является вершина $1$ и так как $\text{listW}[1]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2),\\ &\text{удаляем } e_2=\{1,2\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[3,4,5],\ [3,5,6],\ [1,2,4,6],\ [1,3,5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 3.

Вершиной стека $SW_{ork}$ является вершина $2$ и так как $\text{listW}[2]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3),\\ &\text{удаляем } e_{27}=\{2,3\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[3,4,5],\ [5,6],\ [1,4,6],\ [1,3,5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 4.

Вершиной стека $SW_{ork}$ является вершина $3$ и так как $\text{listW}[3]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1),\\ &\text{удаляем } e_{17}=\{1,3\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[4,5],\ [5,6],\ [4,6],\ [1,3,5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 5.

Вершиной стека $SW_{ork}$ является вершина $1$ и так как $\text{listW}[1]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4),\\ &\text{удаляем } e_1=\{1,4\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[5],\ [5,6],\ [4,6],\ [3,5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 6.

Вершиной стека $SW_{ork}$ является вершина $4$ и так как $\text{listW}[4]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3),\\ &\text{удаляем } e_{22}=\{3,4\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[5],\ [5,6],\ [6],\ [5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,3,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 7.

Вершиной стека $SW_{ork}$ является вершина $3$ и так как $\text{listW}[3]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6),\\ &\text{удаляем } e_7=\{3,6\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[5],\ [5,6],\ [\,],\ [5,7],\ [1,2,4,6,7,9],\\ &\qquad [2,5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 8.

Вершиной стека $SW_{ork}$ является вершина $6$ и так как $\text{listW}[6]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2),\\ &\text{удаляем } e_{19}=\{2,6\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[5],\ [5],\ [\,],\ [5,7],\ [1,2,4,6,7,9],\\ &\qquad [5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 9.

Вершиной стека $SW_{ork}$ является вершина $2$ и так как $\text{listW}[2]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5),\\ &\text{удаляем } e_6=\{2,5\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[5],\ [\,],\ [\,],\ [5,7],\ [1,4,6,7,9],\\ &\qquad [5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 10.

Вершиной стека $SW_{ork}$ является вершина $5$ и так как $\text{listW}[5]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,1),\\ &\text{удаляем } e_{12}=\{1,5\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [5,7],\ [4,6,7,9],\\ &\qquad [5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 11.

Вершиной стека $SW_{ork}$ является вершина $1$ и так как $\text{listW}[1]=\varnothing$, поэтому вершину $1$ удаляем из стека $SW_{ork}$ и вталкиваем в стек $S_{Res}$:

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5),\\ &S_{Res}=(1). \end{aligned}$$

---

Шаг 12.

Вершиной стека $SW_{ork}$ является вершина $5$ и так как $\text{listW}[5]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4),\\ &\text{удаляем } e_{20}=\{4,5\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [7],\ [6,7,9],\\ &\qquad [5,7,8,10],\ [4,5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 13.

Вершиной стека $SW_{ork}$ является вершина $4$ и так как $\text{listW}[4]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7),\\ &\text{удаляем } e_{18}=\{4,7\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [6,7,9],\\ &\qquad [5,7,8,10],\ [5,6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 14.

Вершиной стека $SW_{ork}$ является вершина $7$ и так как $\text{listW}[7]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5),\\ &\text{удаляем } f_1=\{5,7\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [6,9],\\ &\qquad [5,7,8,10],\ [6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 15.

Вершиной стека $SW_{ork}$ является вершина $5$ и так как $\text{listW}[5]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6),\\ &\text{удаляем } e_4=\{5,6\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [7,8,10],\ [6,8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 16.

Вершиной стека $SW_{ork}$ является вершина $6$ и так как $\text{listW}[6]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7),\\ &\text{удаляем } e_{11}=\{6,7\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [8,10],\ [8,10,11],\ [6,7,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 17.

Вершиной стека $SW_{ork}$ является вершина $7$ и так как $\text{listW}[7]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8),\\ &\text{удаляем } e_5=\{7,8\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [8,10],\ [10,11],\ [6,9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 18.

Вершиной стека $SW_{ork}$ является вершина $8$ и так как $\text{listW}[8]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6),\\ &\text{удаляем } e_{13}=\{6,8\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [10],\ [10,11],\ [9,11,12],\ [5,8,10,11,12],\\ &\qquad [6,7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 19.

Вершиной стека $SW_{ork}$ является вершина $6$ и так как $\text{listW}[6]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10),\\ &\text{удаляем } e_{15}=\{6,10\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [\,],\ [10,11],\ [9,11,12],\ [5,8,10,11,12],\\ &\qquad [7,9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 20.

Вершиной стека $SW_{ork}$ является вершина $10$ и так как $\text{listW}[10]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7),\\ &\text{удаляем } e_{21}=\{7,10\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [\,],\ [11],\ [9,11,12],\ [5,8,10,11,12],\\ &\qquad [9,11,12],\ [7,8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 21.

Вершиной стека $SW_{ork}$ является вершина $7$ и так как $\text{listW}[7]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11),\\ &\text{удаляем } e_{23}=\{7,11\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [\,],\ [\,],\ [9,11,12],\ [5,8,10,11,12],\\ &\qquad [9,11,12],\ [8,9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 22.

Вершиной стека $SW_{ork}$ является вершина $11$ и так как $\text{listW}[11]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8),\\ &\text{удаляем } e_{10}=\{8,11\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [\,],\ [\,],\ [9,12],\ [5,8,10,11,12],\\ &\qquad [9,11,12],\ [9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 23.

Вершиной стека $SW_{ork}$ является вершина $8$ и так как $\text{listW}[8]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9),\\ &\text{удаляем } e_8=\{8,9\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [9],\\ &\qquad [\,],\ [\,],\ [9,12],\ [5,8,10,11,12],\\ &\qquad [9,11,12],\ [9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 24.

Вершиной стека $SW_{ork}$ является вершина $9$ и так как $\text{listW}[9]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ 5),\\ &\text{удаляем } e_{14}=\{5,9\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [9,12],\ [8,10,11,12],\ [9,11,12],\ [9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 25.

Вершиной стека $SW_{ork}$ является вершина $5$ и так как $\text{listW}[5]=\varnothing$, поэтому вершину $5$ удаляем из стека $SW_{ork}$ и вталкиваем в стек $S_{Res}$:

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9),\\ &S_{Res}=(1,5). \end{aligned}$$

---

Шаг 26.

Вершиной стека $SW_{ork}$ является вершина $9$ и так как $\text{listW}[9]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8),\\ &\text{удаляем } f_2=\{8,9\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [12],\ [10,11,12],\ [9,11,12],\ [9,10,12],\ [8,9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 27.

Вершиной стека $SW_{ork}$ является вершина $8$ и так как $\text{listW}[8]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12),\\ &\text{удаляем } e_{16}=\{8,12\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [10,11,12],\ [9,11,12],\ [9,10,12],\ [9,10,11]\,\bigr]. \end{aligned}$$

---

Шаг 28.

Вершиной стека $SW_{ork}$ является вершина $12$ и так как $\text{listW}[12]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9),\\ &\text{удаляем } e_{28}=\{9,12\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [10,11],\ [9,11,12],\ [9,10,12],\ [10,11]\,\bigr]. \end{aligned}$$

---

Шаг 29.

Вершиной стека $SW_{ork}$ является вершина $9$ и так как $\text{listW}[9]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10),\\ &\text{удаляем } e_{25}=\{9,10\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [11],\ [11,12],\ [9,10,12],\ [10,11]\,\bigr]. \end{aligned}$$

---

Шаг 30.

Вершиной стека $SW_{ork}$ является вершина $10$ и так как $\text{listW}[10]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11),\\ &\text{удаляем } e_3=\{10,11\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [11],\ [11,12],\ [9,10,12],\ [10,11]\,\bigr]. \end{aligned}$$

---

Шаг 31.

Вершиной стека $SW_{ork}$ является вершина $11$ и так как $\text{listW}[11]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11,\ 9),\\ &\text{удаляем } e_{26}=\{9,11\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [\,],\ [11,12],\ [10,12],\ [10,11]\,\bigr]. \end{aligned}$$

---

Шаг 32.

Вершиной стека $SW_{ork}$ является вершина $9$ и так как $\text{listW}[9]=\varnothing$, поэтому вершину $9$ удаляем из стека $SW_{ork}$ и вталкиваем в стек $S_{Res}$:

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11),\\ &S_{Res}=(1,5,9). \end{aligned}$$

---

Шаг 33.

Вершиной стека $SW_{ork}$ является вершина $11$ и так как $\text{listW}[11]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11,\ f_3\,10),\\ &\text{удаляем } f_3=\{10,11\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [\,],\ [12],\ [12],\ [10,11]\,\bigr]. \end{aligned}$$

---

Шаг 34.

Вершиной стека $SW_{ork}$ является вершина $10$ и так как $\text{listW}[10]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11,\ f_3\,10,\ 12),\\ &\text{удаляем } e_{24}=\{10,12\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\\ &\qquad [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [12],\ [11]\,\bigr]. \end{aligned}$$

---

Шаг 35.

Вершиной стека $SW_{ork}$ является вершина $12$ и так как $\text{listW}[12]\neq\varnothing$, то

$$\begin{aligned} &SW_{ork}=(1,2,3,1,4,3,6,2,5,4,7,5,6,7,8,6,10,7,11,8,\ e_8\,9,\ f_2\,8,\ 12,\ 9,\ 10,\ e_3\,11,\ f_3\,10,\ 12,\ 11),\\ &\text{удаляем } e_9=\{11,12\},\ \text{т.е.}\\ &\text{listW}= \bigl[\,[\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,],\ [\,]\,\bigr]. \end{aligned}$$

После шага 35 использованы все рёбра, а значит, перетаскиваем вершины из $SW_{ork}$ в стек $S_{Res}$:

$$\begin{aligned} S_{Res}=&\ (1,5,9,11,12,10f_3,11e_3,10,9,12,8f_2,9e_8,8,11,7,10,\\ &\ 6,8,7,6,5,7,4,5,2,6,3,4,1,3,2,1). \end{aligned}$$

В стеке $S_{Res}$ получили эйлерову цепь для графа $G+f_1+f_2+f_3$. Удаляя рёбра $f_1$, $f_2$ и $f_3$ из этой цепи, получаем требуемое разбиение:

$$\begin{aligned} E_G ={}&(5,6,7,8,6,10,7,11,8,9)\ \dot{\cup}\\ & (8,12,9,10,11)\ \dot{\cup}\\ & (10,12,11,9,5,1,2,3,1,4,3,6,2,5,4,7). \end{aligned}$$

Ответ:

$$\begin{aligned} E_G ={}&(5,6,7,8,6,10,7,11,8,9)\ \dot{\cup}\\ & (8,12,9,10,11)\ \dot{\cup}\\ & (10,12,11,9,5,1,2,3,1,4,3,6,2,5,4,7). \end{aligned}$$

Задача 3. Минимальный остов графа $G$

Упорядочивание рёбер

Все рёбра графа $G$ упорядочим по возрастанию весов и обозначим их через $e_i$:

$$\begin{aligned} &e_1=\{1,4\},\ e_2=\{1,2\},\ e_3=\{10,11\},\ e_4=\{5,6\},\ e_5=\{7,8\},\ e_6=\{2,5\},\\ &e_7=\{3,6\},\ e_8=\{8,9\},\ e_9=\{11,12\},\ e_{10}=\{8,11\},\ e_{11}=\{6,7\},\ e_{12}=\{1,5\},\\ &e_{13}=\{6,8\},\ e_{14}=\{5,9\},\ e_{15}=\{6,10\},\ e_{16}=\{8,12\},\ e_{17}=\{1,3\},\ e_{18}=\{4,7\},\\ &e_{19}=\{2,6\},\ e_{20}=\{4,5\},\ e_{21}=\{7,10\},\ e_{22}=\{3,4\},\ e_{23}=\{7,11\},\ e_{24}=\{10,12\},\\ &e_{25}=\{9,10\},\ e_{26}=\{9,11\},\ e_{27}=\{2,3\},\ e_{28}=\{9,12\}. \end{aligned}$$

Далее строим минимальный остов по алгоритму Краскала, последовательно рассматривая рёбра $e_1, e_2, \ldots$.

---

Построение по алгоритму Краскала

Шаг 1. Полагаем $\Gamma_1=\Gamma_1^{1}$, где

$$\Gamma_1^{1}=\bigl\{\{1,4\}\bigr\}.$$

Шаг 2. Для ребра $e_2=\{1,2\}$: $1\in V(\Gamma_1)$, $2\notin V(\Gamma_1)$ — случай (2). Получаем

$$\begin{aligned} \Gamma_2 &= \Gamma_2^{1},\\ \Gamma_2^{1} &= \bigl\{\{1,2\},\{1,4\}\bigr\}. \end{aligned}$$

Шаг 3. Вершины $10$ и $11$, инцидентные ребру $e_3=\{10,11\}$, не принадлежат множеству $V(\Gamma_2)$ — случай (1). Поэтому

$$\Gamma_3=\Gamma_3^{1}\,\dot\cup\,\Gamma_3^{2},$$

где

$$\begin{aligned} \Gamma_3^{1} &= \bigl\{\{1,2\},\{1,4\}\bigr\},\\ \Gamma_3^{2} &= \bigl\{\{10,11\}\bigr\}. \end{aligned}$$

Шаг 4. Вершины $5$ и $6$, инцидентные ребру $e_4=\{5,6\}$, не принадлежат множеству $V(\Gamma_3)$ — случай (1). Тогда

$$\Gamma_4=\Gamma_4^{1}\,\dot\cup\,\Gamma_4^{2}\,\dot\cup\,\Gamma_4^{3},$$

где

$$\begin{aligned} \Gamma_4^{1} &= \bigl\{\{1,2\},\{1,4\}\bigr\},\\ \Gamma_4^{2} &= \bigl\{\{10,11\}\bigr\},\\ \Gamma_4^{3} &= \bigl\{\{5,6\}\bigr\}. \end{aligned}$$

Шаг 5. Вершины $7$ и $8$, инцидентные ребру $e_5=\{7,8\}$, не принадлежат множеству $V(\Gamma_4)$ — случай (1). Поэтому

$$\Gamma_5=\Gamma_5^{1}\,\dot\cup\,\Gamma_5^{2}\,\dot\cup\,\Gamma_5^{3}\,\dot\cup\,\Gamma_5^{4},$$

где

$$\begin{aligned} \Gamma_5^{1} &= \bigl\{\{1,2\},\{1,4\}\bigr\},\\ \Gamma_5^{2} &= \bigl\{\{10,11\}\bigr\},\\ \Gamma_5^{3} &= \bigl\{\{5,6\}\bigr\},\\ \Gamma_5^{4} &= \bigl\{\{7,8\}\bigr\}. \end{aligned}$$

Шаг 6. Для ребра $e_6=\{2,5\}$: $2\in V(\Gamma_5^{1})$, $5\in V(\Gamma_5^{3})$ — случай (3). Тогда

$$\Gamma_6=\Gamma_6^{1}\,\dot\cup\,\Gamma_6^{2}\,\dot\cup\,\Gamma_6^{3},$$

где

$$\begin{aligned} \Gamma_6^{1} &= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\}\bigr\},\\ \Gamma_6^{2} &= \bigl\{\{10,11\}\bigr\},\\ \Gamma_6^{3} &= \bigl\{\{7,8\}\bigr\}. \end{aligned}$$

Шаг 7. Для ребра $e_7=\{3,6\}$: $3\notin V(\Gamma_6)$, $6\in V(\Gamma_6^{1})$ — случай (2). Получаем

$$\Gamma_7=\Gamma_7^{1}\,\dot\cup\,\Gamma_7^{2}\,\dot\cup\,\Gamma_7^{3},$$

где

$$\begin{aligned} \Gamma_7^{1} &= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\}\bigr\},\\ \Gamma_7^{2} &= \bigl\{\{10,11\}\bigr\},\\ \Gamma_7^{3} &= \bigl\{\{7,8\}\bigr\}. \end{aligned}$$

Шаг 8. Для ребра $e_8=\{8,9\}$: $9\notin V(\Gamma_7)$, $8\in V(\Gamma_7^{3})$ — случай (2). Тогда

$$\Gamma_8=\Gamma_8^{1}\,\dot\cup\,\Gamma_8^{2}\,\dot\cup\,\Gamma_8^{3},$$

где

$$\begin{aligned} \Gamma_8^{1} &= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\}\bigr\},\\ \Gamma_8^{2} &= \bigl\{\{10,11\}\bigr\},\\ \Gamma_8^{3} &= \bigl\{\{7,8\},\{8,9\}\bigr\}. \end{aligned}$$

Шаг 9. Для ребра $e_9=\{11,12\}$: $12\notin V(\Gamma_8)$, $11\in V(\Gamma_8^{2})$ — случай (2). Получаем

$$\Gamma_9=\Gamma_9^{1}\,\dot\cup\,\Gamma_9^{2}\,\dot\cup\,\Gamma_9^{3},$$

где

$$\begin{aligned} \Gamma_9^{1} &= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\}\bigr\},\\ \Gamma_9^{2} &= \bigl\{\{10,11\},\{11,12\}\bigr\},\\ \Gamma_9^{3} &= \bigl\{\{7,8\},\{8,9\}\bigr\}. \end{aligned}$$

Шаг 10. Для ребра $e_{10}=\{8,11\}$: $8\in V(\Gamma_9^{3})$, $11\in V(\Gamma_9^{2})$ — случай (3). Тогда

$$\Gamma_{10}=\Gamma_{10}^{1}\,\dot\cup\,\Gamma_{10}^{2},$$

где

$$\begin{aligned} \Gamma_{10}^{1} &= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\}\bigr\},\\ \Gamma_{10}^{2} &= \bigl\{\{10,11\},\{11,12\},\{7,8\},\{8,9\},\{8,11\}\bigr\}. \end{aligned}$$

Шаг 11. Для ребра $e_{11}=\{6,7\}$: $6\in V(\Gamma_{10}^{1})$, $7\in V(\Gamma_{10}^{2})$ — случай (3). Получаем единый связный граф

$$\Gamma_{11}=\Gamma_{11}^{1},$$

где

$$\Gamma_{11}^{1}= \bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\},\{10,11\},\{11,12\},\{7,8\},\{8,9\},\{8,11\},\{6,7\}\bigr\}.$$

Так как $\Gamma_{11}$ содержит все вершины графа $G$, то $\Gamma_{11}$ — искомый минимальный остов исходного графа.

Вес получившегося остова:

$$\begin{aligned} c(\Gamma_{11}) &=0.5+1.0+1.3+1.8+1.8+2.0+2.0+2.0+2.0+2.5+3.1\\ &=20.0. \end{aligned}$$

Ответ. Минимальный остов

$$\begin{aligned} T&=\bigl\{\{1,2\},\{1,4\},\{2,5\},\{5,6\},\{3,6\},\{10,11\},\{11,12\},\{7,8\},\{8,9\},\{8,11\},\{6,7\}\bigr\},\\ c(T)&=20.0. \end{aligned}$$