Подсчет треугольников в общих графах можно сделать тривиально за раз, и я думаю, что делать намного быстрее сложно (ссылки приветствуются). Как насчет планарных графиков? Следующая простая процедура показывает, что это можно сделать за O ( n log n ) времени. У меня вопрос двоякий:
- Какая ссылка для этой процедуры?
- Можно ли сделать время линейным?
Из алгоритмического доказательства теоремы о плоском сепараторе Липтона-Тарьяна мы можем за время, линейное по размеру графа, найти разбиение вершин графа на три множества , в которых нет ребер с одной конечной точкой в A, а другой в B , S имеет размер, ограниченный O ( √и обаA,Bимеют размеры, ограниченные сверху 2 числа вершин. Обратите вниманиечто любой треугольник на графике либо целиком лежит внутриAили полностью внутриBили использованияпо меньшей мере одна вершинаSс двумя другими вершинами изA∪Sили оба изB∪S. Таким образом, достаточно посчитать количество треугольников в графе наSи соседейSвA(и аналогично дляB). Обратите внимание, чтоSи егоA-окрестности индуцируютk-строчный плоский граф (указанный граф является подграфом плоского графа диаметром4).). Таким образом, подсчет количества треугольников в таком графе может быть осуществлен непосредственно динамическим программированием или применением теоремы Курселя (я точно знаю, что такая версия для подсчета существует в мире Logspace Эльберфельдом и др., И я предполагаю, что она также существует в линейном мире времени), поскольку формирование ненаправленного треугольника является свойством и поскольку разложение дерева ограниченной ширины легко получить из вложенного плоского графа k- кривой.
Таким образом, мы свели задачу к паре задач, каждая из которых на постоянную долю меньше за счет процедуры с линейным временем.
Обратите внимание, что процедуру можно расширить, чтобы найти количество экземпляров любого фиксированного связного графа внутри входного графа за времени.
Ответы:
Число вхождений любого фиксированного подграфа H в планарный граф G можно посчитать за время O (n), даже если H отключен. Это и некоторые связанные с ним результаты описаны в статье Дэвида Эппштейна (1999 г.) « Изоморфизм подграфа в плоских графах и смежные проблемы »; см. теорему 1. В работе действительно используются методы ширины дерева.
источник
Хотя ответ Барта Янсена решает общий случай подсчета подграфа, известно, что проблема подсчета (или перечисления) всех треугольников в плоском графе (или, в более общем случае, в любом графе ограниченной древовидности) является линейным временем гораздо дольше. Видеть
C. Пападимитриу и М. Яннакакис. Кликовская задача для плоских графов. Информ. Proc. Письма 13 (1981), стр. 131–133.
и
N. Chiba и T. Nishizeki, Алгоритмы и алгоритмы распечатки подграфа, SIAM J. Comput. 14 (1985), с. 210–223.
источник