MAXimal

добавлено: 10 Jun 2008 23:02
редактировано: 10 Jun 2008 23:02

Проверка графа на двудольность и разбиение на две доли

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

Решим эту задачу с помощью поиска в ширину за O (M).

Признак двудольности

Теорема. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют чётную длину.

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

Алгоритм

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

По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.

Реализация

int n;
vector < vector<int> > g;
... чтение графа ...

vector<char> part (n, -1);
bool ok = true;
vector<int> q (n);
for (int st=0; st<n; ++st)
	if (part[st] == -1) {
		int h=0, t=0;
		q[t++] = st;
		part[st] = 0;
		while (h<t) {
			int v = q[h++];
			for (size_t i=0; i<g[v].size(); ++i) {
				int to = g[v][i];
				if (part[to] == -1)
					part[to] = !part[v],  q[t++] = to;
				else
					ok &= part[to] != part[v];
			}
		}
	}

puts (ok ? "YES" : "NO");