Количество ребер между двумя подмножеств bipartitioned графа

Question

Учитывая график G = (V, E), подмножество S, который принадлежит V, и подмножество S», содержащий каждую вершину G не принадлежит S, я хочу рассчитать общее количество ребер между узлами S и S '.

Алгоритм, который мог бы решить эту проблему с лучшей сложностью, чем O (n^2).

Answer 1

Предполагая, что «ниже O (n^2)» вы имеете в виду что-то вроде O (| E |), тогда вы можете сделать это, используя структуры хэширования. Поместите все узлы S в hashset, итерации по всем ребрам G и для каждого ребра проверьте, находятся ли обе конечные точки в хэш-наборе. Построение хэшета - это O (n), и при условии разумной функции хэширования обработка всех ребер O (| E |). Если |E| in Omega(n^2), вы не можете сделать лучше, чем O (n^2).

EDIT: две вещи:

• последнее утверждение о том, не будучи в состоянии лучше сделать, если |E| in Omega(n^2) неправильно, в зависимости от представления вы используете для графа. Пусть E' = {e = {s,v} in E | s in S} - это набор ребер, инцидентных хотя бы одному ребру в S. Если у вас есть списки инциденций/смежности, вы можете улучшить сложность O (| E '|), только итерации по краям, инцидентным узлу в S , и | E '| может быть меньше, чем | E | по непостоянному фактору, зависящему от S.
• Подход легко переводит на поиск границ между S и V \ S. Просто создайте два хэшета, поместите все узлы в S в первый и все узлы в V \ S в другой. Затем отрегулируйте условие только для приема ребер с одним конечным узлом в одном хэш-наборе, а другой конечный узел в другом хэш-наборе. В зависимости от размеров и плотностей обоих индуцированных подграфов, он должен окупиться только для повторения по краям, инцидентным узлам в множестве инцидентов с меньшим количеством ребер.