Алгоритм двух китайцев

Алгоритм двух китайцев — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

Алгоритм

Исходный граф [math]G_0[/math]

Граф [math]C[/math], построенный по графу [math]G_0[/math]

Постановка задачи

Дан взвешенный ориентированный граф [math]G(V, E)[/math] и начальная вершина [math]v[/math]. Требуется построить корневое остовное дерево в [math]G[/math] с корнем в вершине [math]v[/math], сумма весов всех ребер которого минимальна.

Описание

1) Если хотя бы одна вершина графа [math]G[/math] недостижима из [math]v[/math], то требуемое дерево построить нельзя.
2) Для каждой вершины [math]u \ne v[/math] графа [math]G[/math] произведём следующую операцию: найдём ребро минимального веса, входящее в [math]u[/math], и вычтем вес этого ребра из весов всех рёбер, входящих в [math]u[/math]. [math]m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)[/math].
3) Строим граф [math]K = (V,K_0)[/math], где [math]K_0[/math] — множество рёбер нулевого веса графа [math]G[/math] c весовой функцией [math]w'[/math]. Если в этом графе найдётся остовное дерево с корнем в [math]v[/math], то оно и будет искомым.
4) Если такого дерева нет, то построим граф [math]C[/math] — конденсацию графа [math]K[/math]. Пусть [math]y[/math] и [math]z[/math] — две вершины графа [math]C[/math], отвечающие компонентам сильной связности [math]Y[/math] и [math]Z[/math] графа [math]K[/math] соответственно. Положим вес ребра между вершинами [math]y[/math] и [math]z[/math] равным минимальному среди весов рёбер графа [math]G[/math] с весовой функцией [math]w'[/math], идущих из [math]Y[/math] в [math]Z[/math].
5) Продолжим с пункта 2, используя граф [math]C[/math] вместо [math]G[/math].
6) В [math]C[/math] построено MST [math]T[/math]. Построим теперь MST [math]T'[/math] в [math]G[/math] с весовой функцией [math]w'[/math]. Добавим к [math]T'[/math] все вершины компоненты сильной связности графа [math]K[/math], которой принадлежит [math]v[/math] (по путям нулевого веса из [math]v[/math]). Пусть в [math]T[/math] есть ребро [math]yz[/math], где [math]y[/math] отвечает компоненте сильной связности [math]Y[/math], а [math]z[/math] — компоненте сильной связности [math]Z[/math] графа [math]K[/math]. Между [math]Y[/math] и [math]Z[/math] в графе [math]G[/math] с весовой функцией [math]w'[/math] есть ребро [math]y'z'[/math], вес которого равен весу ребра [math]yz[/math]. Добавим это ребро к дереву [math]T'[/math]. Добавим к [math]T'[/math] все вершины компоненты [math]Z[/math] по путям нулевого веса из [math]z'[/math]. Сделаем так для каждого ребра дерева [math]T[/math].
7) Полученное дерево [math]T'[/math] — MST в графе [math]G[/math].

Корректность

1) После перевзвешивания в каждую вершину, кроме [math]v[/math], входит по крайней мере одно ребро нулевого веса.
2) Пусть [math]T[/math] — искомое дерево в [math]G[/math] с весовой функцией [math]w[/math]. [math]w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)[/math], т.е. [math]T[/math] - MST в [math]G[/math] с весовой функцией [math]w[/math] тогда и только тогда, когда [math]T[/math] — MST в [math]G[/math] с весовой функцией [math]w'[/math].
3) Пусть есть некоторый путь от вершины [math]v[/math] до некоторой вершины [math]u[/math] в графе [math]G[/math] с весовой функцией [math]w'[/math]. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа [math]K[/math], которой принадлежит вершина [math]u[/math] (по путям нулевого веса из [math]u[/math]). При этом вес нашего дерева не изменится.
4) Если в графе [math]K[/math] нет остовного дерева с корнем в [math]v[/math], то в графе [math]C[/math] содержится меньше вершин, чем в графе [math]G[/math]. Иначе, если бы в [math]C[/math] было бы столько же вершин, сколько в [math]G[/math], то в [math]K[/math] все компоненты сильной связности состояли бы из единственной вершины. Значит, в [math]G[/math] с весовой функцией [math]w'[/math] не было бы нулевых циклов. То есть мы смогли бы построить в [math]K[/math] остовное дерево с корнем в [math]v[/math], что противоречит нашему предположению.
5) Из сделанных замечаний следует, что дерево [math]T'[/math] — MST в [math]G[/math].

Сложность

Всего будет построено не более [math]|V|[/math] конденсаций. Конденсацию можно построить за [math]O(|E|)[/math]. Значит, алгоритм можно реализовать за [math]O(|V||E|)[/math].

Источники

• Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - ISBN 5-7940-0114-3
• http://is.ifmo.ru