Количество треугольников в графе (7 видео)

Количество треугольников в графе

Алиса и Боб больше не играют ни в какие игры; теперь они дружно изучают свойства различных графов. Алиса придумала следующее занятие: из полного неориентированного графа с n вершинами она выбирает какие-то m ребер и оставляет их себе. Оставшиеся же ребер достаются Бобу.

Алисе и Бобу очень нравятся «треугольники» в графах, то есть циклы длины 3. Поэтому они хотят узнать ответ на такой вопрос: какое суммарное количество треугольников находится в двух графах, образованных ребрами Алисы и ребрами Боба, соответственно?

Первая строка содержит два целых числа n и m ( 1 ≤ n ≤ 10 6 , 0 ≤ m ≤ 10 6 ), разделенные пробелом — количество вершин в изначальном полном графе, а также количество ребер в графе Алисы, соответственно. Далее следуют m строк: i -тая строка содержит два целых числа a i , b i ( 1 ≤ a i, b i ≤ n , a i ≠ b i ), разделенные пробелом — номера двух вершин, соединенных i -тым ребром графа Алисы. Гарантируется, что граф Алисы не содержит кратных ребер и петель. Изначальный полный граф также не содержит кратных ребер и петель.

Считайте, что вершины графа пронумерованы некоторым образом от 1 до n .

Выведите единственное число — суммарное количество циклов длины 3 в графах Алисы и Боба.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin , cout или спецификатор %I64d .

Содержание

Каков эффективный алгоритм подсчета числа треугольников в графе?
6 ответов
Количество треугольников в неориентированном графе
📺 Видео

Видео:Число маршрутов в графеСкачать

Каков эффективный алгоритм подсчета числа треугольников в графе?

каков эффективный алгоритм подсчета количества треугольников в неориентированном графе ) (где граф-это набор вершин и ребер)? Я искал Google и читал на полке учебники по несколько часов каждый день в течение трех дней подряд.

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

для уточнения треугольник на графике представляет собой цикл длиной три. Фокус в том, что он должен работать на множествах вершин не более 10 000 узлов.

в настоящее время я работаю на C#, но больше забочусь об общем подходе к решению этой проблемы, чем о коде для копирования и вставки.

на высоком уровне, мои попытки до сих пор включено:

широкий первый поиск, который отслеживал все уникальные циклы длины три. Это казалось мне прекрасной идеей, но я не мог заставить ее работать
цикл по всем узлам в графе, чтобы увидеть, разделяют ли три вершины ребро. Это слишком медленное время работы для больших наборов данных. O (n^3).

сам алгоритм является частью вычисления коэффициента кластеризации.

Видео:Сколько треугольников на рисунке? Универсальный алгоритм решения задачиСкачать

6 ответов

эта проблема так же сложна, как умножение матрицы. Увидеть это ссылка.

вы знаете что-нибудь о графиках? Они редкие? Если нет, я не думаю, что вы сделаете намного лучше, чем O(n^3).

вам понадобится глубина первый поиск. Алгоритм такой:

1) для текущего узла прошу всех непосещенных смежных вершин

2) для каждого из этих узлов запустите depth two проверьте, является ли узел на глубине 2 вашим текущим узлом с шага one

3) отметить текущий узел как посещенный

4) Сделайте каждый незваный соседний узел своим текущим узлом (1 на 1) и запустите тот же алгоритм

зависит от того, как представлены ваши графики.

Если у вас есть матрица смежности A, Число треугольников должно быть tr (a^3)/6, другими словами, в 1/6 раза больше суммы диагональных элементов (разделение заботится об ориентации и вращении).

Если у вас есть списки смежности, просто начните с каждого узла и выполните поиск глубины-3. Подсчитайте, как часто вы достигаете этого узла — > разделить на 6 снова.

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

соответствующий цикл должен проверить для каждого из n узлов против каждого из их соседей(n*(n-1)) и продолжить цикл, чтобы увидеть, являются ли соседи соседа соседа n: (n*(n-1)) (n-1) (n-1), что почти 10^16 для 10000 n. С миллионом узлы эти петли становятся глупыми, но для ваших 10000 у вас не должно быть никаких проблем, если вы хотите, чтобы brute-force it:)

вы упомянули, что кодируете на C#, а graph (который доступен для C) имеет отличный алгоритм подсчета треугольников, написанных Габором Csardi. Он насчитал 1,3 миллиона треугольников в моем случайном графике 10000 узлов и один миллион ребер за 1,3 секунды на пятилетнем ноутбуке:) Габор Csardi был бы парнем, чтобы спросить 🙂

С точки зрения разных программные подходы, возможно, вам стоит посмотреть на данные, в которых вы храните свою сеть. Если хранится в матрице смежности, количество циклов фиксировано,но в списке ребер сети из трех ребер количество циклов кратно трем независимым от количества узлов. Вы можете запросить список ребер для соседей узла, не проверяя каждую комбинацию i — >j.

Я написал педагогический сценарий в R, чтобы проиллюстрировать подходы и измерить различные скорость алгоритмов очень простой способ. Есть много проблем со скоростью, присущих использованию R здесь (версия edge-list полностью завалена слишком большим количеством ребер), но я думаю, что пример кода должен получить некоторые идеи о том, как думать о скорости грубого принуждения треугольника. Это в R, и не очень аккуратно, но хорошо прокомментирован. Надеюсь, вы сможете преодолеть языковой барьер.

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

самый быстрый алгоритм, известный для поиска и подсчета треугольников, опирается на быстрое матричное произведение и имеет временную сложность O(nw), где ω

Видео:Подобие треугольников. Признаки подобия треугольников (часть 1) | МатематикаСкачать

Количество треугольников в неориентированном графе

Учитывая неориентированный простой граф, нам нужно найти, сколько треугольников у него может быть. Например, приведенный ниже график содержит 2 треугольника.

Пусть A [] [] будет матричным представлением графа смежности. Если мы вычислим A 3 , то число треугольников в Undirected Graph будет равно trace (A 3 ) / 6. Где trace (A) — это сумма элементов на главной диагонали матрицы A.

Ниже приведена реализация вышеприведенной формулы.

// C ++ программа для поиска
// количество треугольников в
// Неориентированный граф. Программа
// для матрицы смежности
// представление графика
#include

using namespace std;

// Количество вершин в графе
#define V 4

// Функция полезности для матрицы
// умножение

void multiply( int A[][V], int B[][V], int C[][V])

for ( int i = 0; i

for ( int j = 0; j

for ( int k = 0; k

// Сервисная функция для расчета
// трассировка матрицы (сумма
// диагностические элементы)

int getTrace( int graph[][V])

for ( int i = 0; i

// Сервисная функция для расчета
// количество треугольников в графе

int triangleInGraph( int graph[][V])

// Сохранить график ^ 2

// Сохранить график ^ 3

for ( int i = 0; i

for ( int j = 0; j

aux2[i][j] = aux3[i][j] = 0;

// aux2 — это график ^ 2 теперь printMatrix (aux2);

multiply(graph, graph, aux2);

// после этого умножения aux3

// график ^ 3 printMatrix (aux3);

multiply(graph, aux2, aux3);

int trace = getTrace(aux3);

return trace / 6;

printf ( «Total number of Triangle in Graph : %dn» ,

// Java программа для поиска номера
// треугольников в неориентированном
// График. Программа для
// матричное представление смежности
// графика

// Количество вершин в

// Сервисная функция для

void multiply( int A[][], int B[][],

for ( int i = 0 ; i

for ( int j = 0 ; j

for ( int k = 0 ; k

// Сервисная функция для расчета

// трассировка матрицы (сумма

int getTrace( int graph[][])

for ( int i = 0 ; i

// Сервисная функция для

// треугольники на графике

int triangleInGraph( int graph[][])

// Сохранить график ^ 2

int [][] aux2 = new int [V][V];

// Сохранить график ^ 3

int [][] aux3 = new int [V][V];

// Инициализация вспомогательных матриц

for ( int i = 0 ; i

for ( int j = 0 ; j

aux2[i][j] = aux3[i][j] = 0 ;

// aux2 теперь граф ^ 2

multiply(graph, graph, aux2);

// после этого умножения aux3

// является графиком ^ 3 printMatrix (aux3)

multiply(graph, aux2, aux3);

int trace = getTrace(aux3);

return trace / 6 ;

public static void main(String args[])

Directed obj = new Directed();

System.out.println( «Total number of Triangle in Graph : » +

// Этот код предоставлен Аншикой Гоял.

# Программа Python3 для определения количества
# треугольники в неориентированном графе.
# программа для матрицы смежности
# представление графа

# Функция полезности для матрицы
# умножение

def multiply(A, B, C):

for i in range (V):

for j in range (V):

for k in range (V):

# Сервисная функция для расчета
# след матрицы (сумма
# диагностические элементы)

for i in range (V):

# Полезная функция для расчета
количество треугольников на графике

# Хранить график ^ 2

aux2 = [[ None ] * V for i in range (V)]

# Хранить график ^ 3

aux3 = [[ None ] * V for i in range (V)]

for i in range (V):

for j in range (V):

aux2[i][j] = aux3[i][j] = 0

# aux2 — это график ^ 2 теперь printMatrix (aux2)

multiply(graph, graph, aux2)

# после этого умножения aux3

# graph ^ 3 printMatrix (aux3)

multiply(graph, aux2, aux3)

return trace / / 6

# Количество вершин в графе

graph = [[ 0 , 1 , 1 , 0 ],

print ( «Total number of Triangle in Graph :» ,

# Этот код предоставлен PranchalK

// C # программа для поиска номера
// треугольников в неориентированном
// График. Программа для
// матричное представление смежности
// графика

<
// Количество вершин
// в графе

// Сервисная функция для
// матричное умножение

void multiply( int [,]A, int [,]B,

for ( int i = 0; i

for ( int j = 0; j

for ( int k = 0; k

// Функция полезности для
// вычислить след
// матрица (сумма
// диагностические элементы)

int getTrace( int [,]graph)

for ( int i = 0; i

trace += graph[i, i];

// Сервисная функция для
// вычисляем количество
// треугольники на графике

int triangleInGraph( int [,]graph)

// Сохранить график ^ 2

int [,] aux2 = new int [V, V];

// Сохранить график ^ 3

int [,] aux3 = new int [V, V];

// Инициализация вспомогательных матриц

for ( int i = 0; i

for ( int j = 0; j

aux2[i, j] = aux3[i, j] = 0;

// aux2 теперь граф ^ 2

multiply(graph, graph, aux2);

// после этого умножения aux3

// является графиком ^ 3 printMatrix (aux3)

multiply(graph, aux2, aux3);

int trace = getTrace(aux3);

return trace / 6;

public static void Main()

GFG obj = new GFG();

Console.WriteLine( «Total number of » +

«Triangle in Graph : » +

// Этот код предоставлен anuj_67.

Выход:

Как это работает?
Если мы вычисляем A n для представления графа в матрице смежности, то значение A n [i] [j] представляет количество различных переходов между вершинами i по j в графе. В A 3 мы получаем все различные пути длины 3 между каждой парой вершин.

Треугольник — это циклический путь длины три, т.е. начинается и заканчивается в одной и той же вершине. Таким образом, A 3 [i] [i] представляет треугольник, начинающийся и заканчивающийся вершиной i. Поскольку у треугольника есть три вершины, и он считается для каждой вершины, нам нужно разделить результат на 3. Кроме того, поскольку граф является ненаправленным, каждый треугольник в два раза больше, чем ipqj и iqpj, поэтому мы также делим на 2. Следовательно, количество треугольников является следом (A 3 ) / 6.

Сложность времени:
Временная сложность вышеупомянутого алгоритма составляет O (V 3 ), где V — количество вершин в графе, мы можем улучшить производительность до O (V 2.8074 ), используя алгоритм умножения матриц Штрассена .

Эта статья предоставлена Уткаршем Триведи. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.