Русский
!

Conference publications

Abstracts

XXII conference

Теорема о величине разреза дерева на два равных кластера вершин

Акифьева К.С., Станкевич Е.В.

Россия, 150000, г. Ярославль, ул. Советская, д.14

1 pp. (accepted)

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

Теорема. Для любого дерева $T(V,E)$ существует сбалансированное разбиение $V = V_{1} V_{2}$ для которого значение выражения $\lfloor\frac{N)}{2}\rfloor$ является верхней оценкой величины его разреза, где $N$ - число вершин дерева.

Далее приведено доказательство теоремы. Заметим, что данная теорема справедлива для деревьев типа звезда. Если дерево не является звездой, то оно имеет рёбра $(v1, v2)$, такие что $\deg v1 > 1$ и $\deg v2 > 1$, назовём их внутренними рёбрами. Если удалить одно такое ребро, то в результате получим два дерева (т.к. не имеют циклов и связны). Повторим этот процесс рекурсивно. Если в графе имелось $t$ внутренних рёбер, то в результате их рекурсивного удаления получим $t + 1$ поддерево: $G_{1}, G_{2}, ... G_{t+1}$. Заметим, что в результате разбиения по внутреннему ребру может получиться только дерево степень которого не меньше $2$, иначе выбранное ребро не является внутренним. Также отметим, что порядок полученных деревьев не превосходит $N - 2t$. Упорядочим полученные деревья по убыванию их степеней. Далее строим множество вершин $V_{1}$ следующим образом: в $V_{1}$ заселяем вершины первых $k$ деревьев из списка, так что $$\begin{cases}\sum_{t=1}^{k-1} \deg G_{t} \leq \lfloor\frac{N}{2}\rfloor \\ \sum_{t=1}^{k} \deg G_{t} > \lfloor\frac{N}{2}\rfloor\end{cases}$$

Назовём $G_{k}$ балансирующим деревом. Для получения сбалансированного разбиения в множество $V_{1}$ необходимо заселить часть вершин из балансирующего дерева (оставшиеся вершины заселяются в $V_{2}$), для этого необходимо совершить ещё $ C $ разрезов. Заметим, что т.к. $\deg G_{k} \le N - 2t$, то $C \le \lfloor\frac{N - 2t}{2}\rfloor$. Учитывая, что уже было произведено $t$ разрезов, то получаем верхнюю оценку числа необходимых разрезов сбалансированного разбиения: $$t + C \le t + \lfloor\frac{N - 2t}{2}\rfloor = \lfloor\frac{N}{2}\rfloor$$

В результате приведённой процедуры было получено равное с точностью до одной вершины (для случая нечётного количества вершин) разбиение вершин дерева с максимальной величиной разреза равной $\lfloor\frac{N}{2}\rfloor$. Теорема доказана.



© 2004 Designed by Lyceum of Informational Technologies №1533