Рубрики

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

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

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

Trace of a graph represented as adjacency matrix A[V][V] is,
trace(A[V][V]) = A[0][0] + A[1][1] + .... + A[V-1][V-1]

Count of triangles = trace(A3) / 6

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

C ++

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

using namespace std;

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

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

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

{

    for (int i = 0; i < V; i++)

    {

        for (int j = 0; j < V; j++)

        {

            C[i][j] = 0;

            for (int k = 0; k < V; k++)

                C[i][j] += A[i][k]*B[k][j];

        }

    }

}

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

int getTrace(int graph[][V])

{

    int trace = 0;

    for (int i = 0; i < V; i++)

        trace += graph[i][i];

    return trace;

}

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

int triangleInGraph(int graph[][V])

{

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

    int aux2[V][V];

  

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

    int aux3[V][V];

  

    // Инициализация aux

    // матрицы с 0

    for (int i = 0; i < V; ++i)

        for (int j = 0; j < V; ++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;

}

  
// код драйвера

int main()

{

  

    int graph[V][V] = {{0, 1, 1, 0},

                       {1, 0, 1, 1},

                       {1, 1, 0, 1},

                       {0, 1, 1, 0}

                      };

  

    printf("Total number of Triangle in Graph : %d\n",

            triangleInGraph(graph));

    return 0;

}

Джава

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

import java.io.*;

  

class Directed

{

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

    // график

    int V = 4;

   

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

   // матричное умножение

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

                            int C[][])

   {

       for (int i = 0; i < V; i++)

       {

           for (int j = 0; j < V; j++)

           {

               C[i][j] = 0;

               for (int k = 0; k < V; 

                                   k++)

               {

                   C[i][j] += A[i][k]*

                              B[k][j];

               }

           }

       }

   }

   

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

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

   // диагностические элементы)

   int getTrace(int graph[][])

   {

       int trace = 0;

  

       for (int i = 0; i < V; i++)

       {

           trace += graph[i][i];

       }

       return trace;

   }

   

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

   // вычисляем количество

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

   int triangleInGraph(int graph[][])

   {

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

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

  

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

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

   

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

       // с 0

       for (int i = 0; i < V; ++i)

       {

           for (int j = 0; j < V; ++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;

   }

   

   // Код драйвера

   public static void main(String args[])

   {

       Directed obj = new Directed();

         

       int graph[][] = { {0, 1, 1, 0},

                         {1, 0, 1, 1},

                         {1, 1, 0, 1},

                         {0, 1, 1, 0}

                       };

  

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

              obj.triangleInGraph(graph));

   }

}

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

python3

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

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

def multiply(A, B, C):

    global V

    for i in range(V):

        for j in range(V):

            C[i][j] = 0

            for k in range(V):

                C[i][j] += A[i][k] * B[k][j]

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

def getTrace(graph):

    global V

    trace = 0

    for i in range(V):

        trace += graph[i][i] 

    return trace

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

def triangleInGraph(graph):

    global V

      

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

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

  

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

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

  

    # Инициализация aux

    # матрицы с 0

    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) 

  

    trace = getTrace(aux3) 

    return trace // 6

  
Код водителя

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

V = 4

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

         [1, 0, 1, 1], 

         [1, 1, 0, 1], 

         [0, 1, 1, 0]]

  

print("Total number of Triangle in Graph :",

                    triangleInGraph(graph))

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

C #

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

using System;

  

class GFG

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

int V = 4;

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

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

                        int [,]C)

{

    for (int i = 0; i < V; i++)

    {

        for (int j = 0; j < V; j++)

        {

            C[i, j] = 0;

            for (int k = 0; k < V; 

                              k++)

            {

                C[i, j] += A[i, k]*

                           B[k, j];

            }

        }

    }

}

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

int getTrace(int [,]graph)

{

    int trace = 0;

  

    for (int i = 0; i < V; i++)

    {

        trace += graph[i, i];

    }

    return trace;

}

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

int triangleInGraph(int [,]graph)

{

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

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

  

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

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

  

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

    // с 0

    for (int i = 0; i < V; ++i)

    {

        for (int j = 0; j < V; ++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;

}

  
// Код драйвера

public static void Main()

{

    GFG obj = new GFG();

          

    int [,]graph = {{0, 1, 1, 0},

                    {1, 0, 1, 1},

                    {1, 1, 0, 1},

                    {0, 1, 1, 0}};

  

    Console.WriteLine("Total number of "

                   "Triangle in Graph : "+

              obj.triangleInGraph(graph));

}
}

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

Выход:

Total number of Triangle in Graph : 2

Как это работает?
Если мы вычисляем 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 ), используя алгоритм умножения матриц Штрассена .

Ссылки:
http://www.d.umn.edu/math/Technical%20Reports/Technical%20Reports%202007-/TR%202012/yang.pdf
Количество треугольников в ориентированных и неориентированных графах

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes