Рубрики

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

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

Пример:

Input: digraph[V][V] = { {0, 0, 1, 0},
                        {1, 0, 0, 1},
                        {0, 1, 0, 0},
                        {0, 0, 1, 0}
                      };
Output: 2
Give adjacency matrix represents following 
directed graph.

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

Идея состоит в том, чтобы использовать три вложенных цикла, чтобы рассмотреть каждый триплет (i, j, k) и проверить наличие вышеуказанного условия (есть ребро от i до j, от j до k и от k до i)
Однако в неориентированном графе триплет (i, j, k) можно переставить, чтобы получить шесть комбинаций (подробности см. В предыдущем посте ). Следовательно, мы делим общее количество на 6, чтобы получить фактическое количество треугольников.
В случае ориентированного графа число перестановок будет равно 3 (поскольку порядок узлов становится релевантным). Следовательно, в этом случае общее количество треугольников будет получено путем деления общего количества на 3. Например, рассмотрим ориентированный граф, приведенный ниже.

Ниже приводится реализация.

C / C ++

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

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

  

using namespace std;

  
// функция для расчета
// количество треугольников в
// простой направленный / ненаправленный
// график. isDirected - это правда, если
// график направлен, его
// ложь в противном случае

int countTriangle(int graph[V][V], 

                  bool isDirected)

{

    // Инициализировать результат

    int count_Triangle = 0;

  

    // Рассмотрим все возможные

    // триплет ребер в графе

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

    {

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

        {

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

            {

               // проверяем триплет, если

               // удовлетворяет условию

               if (graph[i][j] && graph[j][k] 

                               && graph[k][i])

                  count_Triangle++;

             }

        }

    }

  

    // если граф направлен,

    // деление делается на 3,

    // иначе деление на 6 сделано

    isDirected? count_Triangle /= 3 :

                count_Triangle /= 6;

  

    return count_Triangle;

}

  
// функция драйвера для проверки программы

int main()

{

    // Создать матрицу смежности

    // неориентированного графа

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

                       {1, 0, 1, 1},

                       {1, 1, 0, 1},

                       {0, 1, 1, 0}

                     };

  

    // Создать матрицу смежности

    // ориентированного графа

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

                        {1, 0, 0, 1},

                        {0, 1, 0, 0},

                        {0, 0, 1, 0}

                       };

  

    cout << "The Number of triangles in undirected graph : "

         << countTriangle(graph, false);

    cout << "\n\nThe Number of triangles in directed graph : "

         << countTriangle(digraph, true);

  

    return 0;

}

Джава

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

import java.io.*;

  

class GFG {

  

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

    int V = 4;

  

    // функция для вычисления числа

    // треугольников в простом

    // направленный / неориентированный граф. направлено

    // верно, если граф направлен,

    // иначе ложно

    int countTriangle(int graph[][], 

                      boolean isDirected)

   {

       // Инициализировать результат

       int count_Triangle = 0;

  

       // Рассмотрим все возможные

       // триплет ребер в графе

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

       {

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

           {

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

               {

                  // проверяем триплет, если он

                  // удовлетворяет условию

                  if (graph[i][j] == 1 && 

                      graph[j][k] == 1 && 

                      graph[k][i] == 1)

                      count_Triangle++;

               }

           }

       }

   

       // если граф направлен, деление

       // выполняется 3-мя другими делениями

       // сделано 6

       if(isDirected == true)

       {

           count_Triangle /= 3;

       }

       else

       {

           count_Triangle /= 6;

       }

       return count_Triangle;

   }

   

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

    public static void main(String args[])

   {

         

       // Создать матрицу смежности

       // неориентированного графа

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

                        {1, 0, 1, 1},

                        {1, 1, 0, 1},

                        {0, 1, 1, 0}

                       };

      

       // Создать матрицу смежности

       // ориентированного графа

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

                           {1, 0, 0, 1},

                           {0, 1, 0, 0},

                           {0, 0, 1, 0}

                         };

   

    System.out.println("The Number of triangles "+

                       "in undirected graph : " +

                        countTriangle(graph, false));

  

    System.out.println("\n\nThe Number of triangles"+

                       " in directed graph : "

                       countTriangle(digraph, true));

  

   }

}

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

питон

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

  

  
# функция для вычисления количества треугольников в простом
# направленный / неориентированный граф.
# isDirected - true, если граф направлен, в противном случае - false

def countTriangle(g, isDirected):

    nodes = len(g)

    count_Triangle = 0 # Инициализировать результат

    # Рассмотрим каждый возможный триплет ребер в графе

    for i in range(nodes):

        for j in range(nodes):

            for k in range(nodes):

                # проверить триплет, если он удовлетворяет условию

                if( i!=j and i !=k and j !=k and 

                        g[i][j] and g[j][k] and g[k][i]):

                    count_Triangle += 1

    # если график направлен, деление делится на 3

    # еще деление на 6 сделано

    return count_Triangle/3 if isDirected else count_Triangle/6

  
# Создать матрицу смежности неориентированного графа

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

       [1, 0, 1, 1],

       [1, 1, 0, 1],

       [0, 1, 1, 0 ]]

# Создать матрицу смежности ориентированного графа

digraph = [[0, 0, 1, 0],

             [1, 0, 0, 1],

          [0, 1, 0, 0],

          [0, 0, 1, 0 ]]

  

print ("The Number of triangles in undirected graph : %d" %countTriangle(graph, False))

  

print ("The Number of triangles in directed graph : %d" %countTriangle(digraph, True))

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

C #

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

using System;

  

class GFG {

      

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

    const int V = 4;

      

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

    // количество треугольников в

    // простой направленный / ненаправленный

    // график. isDirected - это правда, если

    // график направлен, его

    // ложь в противном случае

    static int countTriangle(int[,] graph, 

                    bool isDirected)

    {

        // Инициализировать результат

        int count_Triangle = 0;

      

        // Рассмотрим все возможные

        // триплет ребер в графе

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

        {

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

            {

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

                {

                // проверяем триплет, если

                // удовлетворяет условию

                if (graph[i,j] != 0 &&

                    graph[j,k] != 0 && 

                     graph[k,i] != 0 )

                    count_Triangle++;

                }

            }

        }

      

        // если граф направлен,

        // деление делается на 3,

        // иначе деление на 6 сделано

        if(isDirected != false)

            count_Triangle = 

                        count_Triangle / 3 ;

        else

            count_Triangle = 

                         count_Triangle / 6;

      

        return count_Triangle;

    }

      

    // Функция драйвера для проверки программы

    static void Main()     

    {

          

        // Создать матрицу смежности

        // неориентированного графа

        int[,] graph = new int[4,4] { 

                            {0, 1, 1, 0},

                            {1, 0, 1, 1}, 

                            {1, 1, 0, 1}, 

                            {0, 1, 1, 0} 

                        };

      

        // Создать матрицу смежности

        // ориентированного графа

        int[,] digraph = new int [4,4] {

                            {0, 0, 1, 0},

                            {1, 0, 0, 1},

                            {0, 1, 0, 0},

                            {0, 0, 1, 0}

                        };

                          

                          

      

        Console.Write("The Number of triangles"

                    + " in undirected graph : "

                + countTriangle(graph, false));

                  

        Console.Write("\n\nThe Number of "

         + "triangles in directed graph : " 

           + countTriangle(digraph, true));

    }

}

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

PHP

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

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

$V = 4;

  
// функция для расчета
// количество треугольников в
// простой направленный / ненаправленный
// график. isDirected - это правда, если
// график направлен, его
// ложь в противном случае

function countTriangle($graph

                       $isDirected)

{

    global $V;

      

    // Инициализировать результат

    $count_Triangle = 0;

  

    // Рассмотрим все возможные

    // триплет ребер в графе

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

    {

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

        {

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

            {

                  

                // проверяем триплет, если

                // удовлетворяет условию

                if ($graph[$i][$j] and $graph[$j][$k

                                   and $graph[$k][$i])

                    $count_Triangle++;

            }

        }

    }

  

    // если граф направлен,

    // деление делается на 3,

    // иначе деление на 6 сделано

    $isDirected? $count_Triangle /= 3 :

                 $count_Triangle /= 6;

  

    return $count_Triangle;

}

  

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

    // Создать матрицу смежности

    // неориентированного графа

    $graph = array(array(0, 1, 1, 0),

                   array(1, 0, 1, 1),

                   array(1, 1, 0, 1),

                   array(0, 1, 1, 0));

  

    // Создать матрицу смежности

    // ориентированного графа

    $digraph = array(array(0, 0, 1, 0),

                     array(1, 0, 0, 1),

                     array(0, 1, 0, 0),

                     array(0, 0, 1, 0));

          

    echo "The Number of triangles in undirected graph : "

                        , countTriangle($graph, false);

    echo "\nThe Number of triangles in directed graph : "

                        , countTriangle($digraph, true);

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


Выход:

The Number of triangles in undirected graph : 2
The Number of triangles in directed graph : 2

Сравнение этого подхода с предыдущим подходом :
Преимущества:

  • Не нужно рассчитывать трассировку.
  • Матрица — умножение не требуется.
  • Вспомогательные матрицы не требуются, поэтому оптимизированы в пространстве.
  • Работает для ориентированных графов.

Недостатки:

  • Временная сложность составляет O (n 3 ) и не может быть уменьшена в дальнейшем.

Эта статья предоставлена Ашутошем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes