Как найти количество циклов в графе - Avtoru.top

Оценка количества простых циклов на графе

Уровень сложности
Средний

Время на прочтение
4 мин

Количество просмотров 3.6K

Введение

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

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

Формализация задачи

Итак, для определенности будем рассматривать граф G – ориентированный, без петель.

При этом порядок графа равен, очевидно, N, а количество рёбер – M.

Графу можно взаимно однозначно сопоставить матрицу смежности A.

Вследствие ориентированности графа G соответствующая матрица смежности в общем случае асимметрична:

Условие (4) отсутствия петель в графе приводит к тому, что на главной диагонали матрицы смежности допустимы только нулевые элементы

и матрица, таким образом, имеет вид

Под простым циклом L длины K на графе G будем понимать такую последовательность K неповторяющихся вершин графа, что каждые две последовательные вершины в последовательности, а также последняя и первая вершины в ней, смежны. Далее речь будет идти только о простых циклах; будем, для краткости, называть их просто циклами.

Будем далее обозначать

Оценка количества циклов

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

Были зафиксированы N вершин графа, т.е. множество V.
Матрица смежности размером N x N была заполнена нулевыми значениями.
В матрице смежности совершенно случайным образом были выбраны ровно M элементов, не лежащих на главной диагонали, и им были присвоены единичные значения.
На указанных вершинах в соответствии с матрицей смежности были построены ребра графа E.

С учётом изложенного и (11), вероятность того, что произвольный элемент матрицы смежности вне главной диагонали равен единице, очевидно, равна

Легко увидеть, что выражения (12), (13) определяют циклическое размещение без повторений длины K из генеральной совокупности V размером в N элементов; из комбинаторики известно, что количество различных размещений при этом составляет

Для того, чтобы циклическое размещение из (12), (13) соответствовало циклу на графе G, необходимо, чтобы выполнялись условия (14), (15), т.е. чтобы существовали соответствующие рёбра, или, другими словами, K соответствующих элементов матрицы смежности были равны единице. С учётом (18), вероятность этого составляет

Таким образом, исходя из выбранной модели формирования графа G, произвольное циклическое размещение без повторений, состоящее из K вершин графа, формирует цикл на этом графе с вероятностью (21).

Заметим, что теперь количество циклов длины K на графе можно рассматривать как случайную величину, математическое ожидание которой из (19) и (21) составляет

И, наконец, математическое ожидание количества циклов на графе G с учётом (17) равно

Это и есть искомая оценка.

Замечания и обсуждение

Прежде всего, заметим, что указанная оценка довольно неплохо согласуется с экспериментальными данными. В таблице 1 приведены данные о количестве циклов в графах, полученные переборным методом. Эксперимент охватывал 4 группы графов, в каждой группе содержалось по 10 графов с 50-ю вершинами каждый и количеством рёбер 90, 100, 110 и 120 для каждой из групп соответственно. Несмотря на то, что для каждого конкретного графа количество циклов может заметно отличаться от оценочного, среднее по группе значение достаточно близко к нему.

Далее, стоит отметить, что даже для сравнительно небольших графов оценка (23) предсказывает наличие весьма значительного количества циклов на них; ряд оценочных значений приведен в таблице 2. Это стоит учитывать при планировании вычислений, связанных с перебором циклов на графе: они могут занять несколько больше времени и ресурсов, чем кажется!

Ещё одним интересным моментом является то, что формула (23) позволяет легко построить функцию, которую можно интерпретировать как оценку плотности распределения циклов по длинам:

На рис. 1 изображены графики оценочной и экспериментальной плотности распределения циклов по длинам на графе с 60 вершинами и 140 рёбрами. Как видно, они довольно неплохо согласуются между собой. При этом под экспериментальной плотностью понимается

где количества циклов в отношении получены прямым подсчётом.

Таким образом, оценка (24) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.

Остаётся заметить, что хотя рассуждения в статье относятся к случаю простых циклов на ориентированных графах без петель, подобные результаты могут быть получены для прочих типов графов и циклов путём аналогичных рассуждений.

Заключение

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

Источник

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given an undirected unweighted graph of N vertices in the form of adjacency matrix adj[][], the task is to find the number of simple cycles in it.

Input: adj[][] = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, { 1, 1, 0, 1 }, { 1, 0, 1, 0 } }
Output: 2
Explanation: The graph is shown below as:

The given graph consists of two simple cycles as shown
Input: adj[][] = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } }
Output: 1

Approach: The given problem can be solved by using Dynamic Programming with Bitmasking, the dynamic programming state for the Hamiltonian paths is defined as the dp[mask][i] as the number of paths that cover the node-set mask and ends at i and iterate from 0 to N-1 and in each iteration, compute the number of loops containing the current node without the previous node and sum them up, Since there are two directions for a loop divide the result by 2. Follow the steps below to solve the problem:

Initialize a variable ans as 0 that stores the resultant count of cycles.
Initialize a 2-D array dp[][] array of dimensions 2^N and N and initialize it with 0.
Iterate over the range [0, 2^N – 1) using the variable mask and perform the following tasks:
- Initialize 2 variables nodeSet and firstSetBit as the number of set bits and the first set bit in mask.
- If nodeSet equals 1, then set the value of dp[mask][firstSetBit] as 1.
- Now, For each mask having set bits greater than 1, iterate over the range [firstSetBit + 1, N – 1) using the variable j and if the Bitwise AND of mask & 2^j is true, then initialize a variable newNodeSet as mask^2^j and iterate over the range [0, N) using the variable k and perform the following tasks:
  - Check if there is an edge between nodes k and j(k is not equal to j).
  - If there is an edge then add the number of loops in this mask that ends at k and does not contain j to the state for the node-set mask as follows dp[mask][j] = dp[mask][j]+ dp[mask XOR 2^j][k].
  - If adj[j][firstSetBit] is 1 and nodeSet is greater than 2, then add the value of dp[mask][j] to the variable ans.
After performing the above steps, print the value of ans as the answer.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void findNumberOfSimpleCycles(

int N, vector<vector<int> > adj)

{

int ans = 0;

int dp[(1 << N)][N];

memset(dp, 0, sizeof dp);

for (int mask = 0;

mask < (1 << N); mask++) {

int nodeSet

= __builtin_popcountll(mask);

int firstSetBit

= __builtin_ffsl(mask);

if (nodeSet == 1) {

dp[mask][firstSetBit] = 1;

}

else {

for (int j = firstSetBit + 1;

j < N; j++) {

if ((mask & (1 << j))) {

int newNodeSet = mask ^ (1 << j);

for (int k = 0; k < N; k++) {

if ((newNodeSet & (1 << k))

&& adj[k][j]) {

dp[mask][j]

+= dp[newNodeSet][k];

if (adj[j][firstSetBit]

&& nodeSet > 2)

ans += dp[mask][j];

}

cout << ans << endl;

}

int main()

{

vector<vector<int> > adj

= { { 0, 1, 1, 1 },

{ 1, 0, 1, 0 },

{ 1, 1, 0, 1 },

{ 1, 0, 1, 0 } };

int N = adj.size();

findNumberOfSimpleCycles(N, adj);

return 0;

}

Java

import java.util.*;

class GFG{

static int __builtin_popcountll(long x)

{

int setBits = 0;

while (x != 0) {

x = x & (x - 1);

setBits++;

}

return setBits;

}

static int getFirstSetBitPos(int n)

{

return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;

}

static void findNumberOfSimpleCycles(

int N, int[][] adj)

{

int ans = 1;

int [][]dp = new int[(1 << N)][N];

for (int mask = 0;

mask < (1 << N); mask++) {

int nodeSet

= __builtin_popcountll(mask);

int firstSetBit

= getFirstSetBitPos(mask);

if (nodeSet == 1) {

dp[mask][firstSetBit-1] = 1;

}

else {

for (int j = firstSetBit + 1;

j < N; j++) {

if ((mask & (1 << j))!=0) {

int newNodeSet = mask ^ (1 << j);

for (int k = 0; k < N; k++) {

if ((newNodeSet & (1 << k)) !=0

&& adj[k][j] !=0) {

dp[mask][j]

+= dp[newNodeSet][k];

if (adj[j][firstSetBit]!=0

&& nodeSet > 2)

ans += dp[mask][j];

}

System.out.print(ans +"n");

}

public static void main(String[] args)

{

int[][] adj

= { { 0, 1, 1, 1 },

{ 1, 0, 1, 0 },

{ 1, 1, 0, 1 },

{ 1, 0, 1, 0 } };

int N = adj.length;

findNumberOfSimpleCycles(N, adj);

}

Python3

import math

def __builtin_popcountll(num):

binary = bin(num)

setBits = [ones for ones in binary[2:] if ones=='1']

return len(setBits)

def __builtin_ffsl(n):

if n == 0:

return 0

return math.floor(math.log2(n & -n)) + 1

def findNumberOfSimpleCycles(N, adj):

ans = 1

dp = []

for i in range(0, (1 << N)):

dp.append([])

for j in range(0, N):

dp[i].append(0)

for i in range(0, (1 << N)):

for j in range(0, N):

if(dp[i][j] != 0):

print(dp[i][j], i, j)

for mask in range(0, (1 << N)):

nodeSet = __builtin_popcountll(mask)

firstSetBit = __builtin_ffsl(mask)

if (nodeSet == 1):

dp[mask][firstSetBit-1] = 1

else:

for j in range(firstSetBit + 1, N):

if (mask & (1 << j)) != 0:

newNodeSet = mask ^ (1 << j)

for k in range(0, N):

if (((newNodeSet & (1 << k)) > 0) and adj[k][j] > 0):

dp[mask][j] += dp[newNodeSet][k]

if ((adj[j][firstSetBit] > 0) and nodeSet > 2):

ans += dp[mask][j]

print(ans)

if __name__=='__main__':

adj = [ [ 0, 1, 1, 1 ],

[ 1, 0, 1, 0 ],

[ 1, 1, 0, 1 ],

[ 1, 0, 1, 0 ] ]

N = len(adj)

findNumberOfSimpleCycles(N, adj)

C#

using System;

public class GFG{

static int __builtin_popcountll(long x)

{

int setBits = 0;

while (x != 0) {

x = x & (x - 1);

setBits++;

}

return setBits;

}

static int getFirstSetBitPos(int n)

{

return (int)((Math.Log10(n & -n)) / Math.Log10(2)) + 1;

}

static void findNumberOfSimpleCycles(

int N, int[,] adj)

{

int ans = 1;

int [,]dp = new int[(1 << N),N];

for (int mask = 0;

mask < (1 << N); mask++) {

int nodeSet

= __builtin_popcountll(mask);

int firstSetBit

= getFirstSetBitPos(mask);

if (nodeSet == 1) {

dp[mask,firstSetBit-1] = 1;

}

else {

for (int j = firstSetBit + 1;

j < N; j++) {

if ((mask & (1 << j))!=0) {

int newNodeSet = mask ^ (1 << j);

for (int k = 0; k < N; k++) {

if ((newNodeSet & (1 << k)) !=0

&& adj[k,j] !=0) {

dp[mask,j]

+= dp[newNodeSet,k];

if (adj[j,firstSetBit]!=0

&& nodeSet > 2)

ans += dp[mask,j];

}

Console.Write(ans +"n");

}

public static void Main(String[] args)

{

int[,] adj

= { { 0, 1, 1, 1 },

{ 1, 0, 1, 0 },

{ 1, 1, 0, 1 },

{ 1, 0, 1, 0 } };

int N = adj.GetLength(0);

findNumberOfSimpleCycles(N, adj);

}

Javascript

<script>

function __builtin_popcountll(x)

{

var setBits = 0;

while (x != 0) {

x = x & (x - 1);

setBits++;

}

return setBits;

}

function getFirstSetBitPos(n)

{

return parseInt(((Math.log10(n & -n)) / Math.log10(2)) + 1);

}

function findNumberOfSimpleCycles(

N, adj)

{

var ans = 1;

var dp = Array(1 << N).fill().map(()=>Array(N).fill(0));

for (var mask = 0;

mask < (1 << N); mask++) {

var nodeSet

= __builtin_popcountll(mask);

var firstSetBit

= getFirstSetBitPos(mask);

if (nodeSet == 1) {

dp[mask][firstSetBit-1] = 1;

}

else {

for (j = firstSetBit + 1;

j < N; j++) {

if ((mask & (1 << j))!=0) {

var newNodeSet = mask ^ (1 << j);

for (k = 0; k < N; k++) {

if ((newNodeSet & (1 << k)) !=0

&& adj[k][j] !=0) {

dp[mask][j]

+= dp[newNodeSet][k];

if (adj[j][firstSetBit]!=0

&& nodeSet > 2)

ans += dp[mask][j];

}

document.write(ans +"n");

}

var adj

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

[ 1, 0, 1, 0 ],

[ 1, 1, 0, 1 ],

[ 1, 0, 1, 0 ] ];

var N = adj.length;

findNumberOfSimpleCycles(N, adj);

</script>

Time Complexity: O((2^N)N²)
Auxiliary Space: O(1)

Last Updated :
15 Jun, 2022

Like Article

Save Article

Источник

Ищем количество циклов в неориентированном графе

Задача — найти в произвольном неориентированном графе количество циклов, не связанных с другими частями графа.

Искомый цикл состоит минимум из двух вершин и не имеет «лишних» рёбер, то есть, представляет собой кольцо вида 1-2-1 или 1-2-3-1, и т.п.

Граф был взят из этой заметки, только к нему приписан не связанный с остальными вершинами цикл 8-9-10-8.

Само представление графа — максимально простое, с помощью векторов, расчёт проверен в консоли Visual Studio 2013, больше тут ничего нет под рукой

#include <iostream>
#include <vector>
using namespace std;

const int N = 100; //Предельное количество вершин
int degree[N]; //Степени вершин
bool found[N]; //Флажки для просмотренных вершин
vector <int> mygraph; //Текущий граф
vector<int> mylist[N]; //Список смежности

void DFS(int v) { //Обход графа для поиска вершин, связанных с v
 found[v] = true;
 mygraph.push_back(v);
 for (int it : mylist[v]) if (!found[it]) DFS(it);
}


void addEdge(vector<int> mylist[N], int src, int dest) { //Добавление ребра
 mylist[src].push_back(dest);
 mylist[dest].push_back(src);
 degree[src]++;
 degree[dest]++;
}

int countSingleCycles(int n, int m) { //Подсчёт количества циклов в графе
 int count = 0;
 for (int i = 0; i < n; ++i) {
  if (!found[i]) {
   mygraph.clear();
   DFS(i);
   int flag = 1;
   for (int v : mygraph) {
    if (degree[v] == 2)	continue;
    else {
     flag = 0; break;
    }
   }
   if (flag == 1) count++;
  }
 }
 return count;
}

int main() {
 int n = 11, m = 12; // n - количество вершин, m - рёбер
 addEdge(mylist, 0, 1); addEdge(mylist, 0, 2); 
 addEdge(mylist, 1, 4); addEdge(mylist, 2, 4);
 addEdge(mylist, 2, 3);
 addEdge(mylist, 4, 5); addEdge(mylist, 4, 7);
 addEdge(mylist, 5, 6); addEdge(mylist, 6, 7);
 //Добавляем цикл 8-9-10
 addEdge(mylist, 8, 9); addEdge(mylist, 9, 10); addEdge(mylist, 10, 8);
 cout << countSingleCycles(n, m);
 cin.get();	return 0;
}

Во второй задаче для двух положительных натуральных значений n и k задан неориентированный полный связный граф из n узлов, то есть, каждый узел связан с каждым.

Проблема состоит в том, чтобы вычислить количество способов, с помощью которых можно начинать с любого узла и возвращаться к нему, посетив всего k узлов.

Например, для кольца из 3 вершин и длины пути 3 таких способов 2 (1-2-3-1 и 1-3-2-1), если вершин становится 4, то есть 3 способа сделать путь для значения k=2 (1-2-1, 1-3-1, 1-4-1) — см. рисунок.

полные связные графы размерности 3 и 4

При увеличении размерности всё становится интереснее, например, для n=5 и k=3 возможные пути нарисованы на втором рисунке шестью цветами радуги, и каждый путь можно пройти в двух направлениях, то есть, всего возможных путей 12.

полный связный граф размерности 5 и пути с посещением 3 узлов

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

y(n,k) = [ (n-1)^k + (-1)^k * (n-1) ] / n

#include <iostream>
using namespace std;

int numOfways(int n, int k) {
 int p = 1;
 if (k % 2)	p = -1; 
 return (pow(n - 1, k) + p * (n - 1)) / n;
}


int main() {
 int n = 4, k = 2; // n - количество вершин, k - количество посещённых узлов
 int w = numOfways (n, k);
 if (w == -1) cout << "Error!";
 else cout << w;
 cin.get();	return 0;
}

Может, чего и напутал в спешке, но надеюсь, что нет

28.05.2018, 09:56 [6903 просмотра]

Источник

Я так и не понял, что у Вас не получается. DFS — правильная идея. Gassa уже сказал, что, чтобы пути не учитывались несколько раз, нужно поделить на 2k.

Запускать DFS нужно, конечно, от всех вершин по очереди. DFS должен перед выходом из рекурсии снимать пометку с вершины.

P.S. Задача коротко формулируется так: кол-во простых циклов длины k в неориентированном графе.

UPD1: О! В ссылке оказывается другое условие задачи Да, для 4-х все несколько проще. FOR FOR FOR FOR ?

UPD2: Видимо, хорошим тоном было бы с самого начала дать ссылку на условие задача. Например, оказывается, N < 300.

Источник

Как посчитать циклы в графе

БлогNot. Ищем количество циклов в неориентированном графе

Ищем количество циклов в неориентированном графе

Граф был взят из этой заметки, только к нему приписан не связанный с остальными вершинами цикл 8-9-10-8.

Само представление графа — максимально простое, с помощью векторов, расчёт проверен в консоли Visual Studio 2013, больше тут ничего нет под рукой 🙂

полные связные графы размерности 3 и 4

полный связный граф размерности 5 и пути с посещением 3 узлов

Нахождение цикла

Напомним, что циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф называют ацикличным, если в нем нет циклов.

Для нахождения цикла, рассмотрим такой альтернативные способ делать обход в глубину:

Здесь мы вместо массива used передаем в рекурсию параметр $p$, равный номеру вершины, откуда мы пришли, или $-1$, если мы начали обход в этой вершине.

Этот способ корректен только для деревьев — проверка u != p гарантирует, что мы не пойдем обратно по ребру, однако если в графе есть цикл, то мы в какой то момент вызовем dfs второй раз с одними и теми же параметрами и попадем в бесконечный цикл.

Если мы можем определять, попали ли мы в бесконечный цикл, то это ровно то, что нам нужно. Модифицируем dfs так, чтобы мы могли определять момент, когда мы входим в цикл. Для этого просто вернем массив used обратно, но будем использовать его для проверки, были ли мы когда-то в вершине, которую мы собираемся посетить — это будет означать, что цикл существует.

Если нужно восстанавливать сам цикл, то можно вместо завершения программы возвращаться из рекурсии несколько раз и выписывать вершины, пока не дойдем до той, в которой нашелся цикл.

Как и со всеми обходами, если в графе больше одной компоненты связности, или если граф ориентированный, то dfs нужно запускать несколько раз от вершин разных компонент.

Помогите с информатикой и количеством циклов в графе

Помогите. Как здесь найти количество циклов?

Задание 1.
Пусть у вершин этого квадрата будут названия A, B, C, D. В его центре вершины нету 🙂
1-й цикл: фигура ABCD — собственно, сам квадрат;
ещё циклы: это треугольники ABC, ABD, BCD, CDA;
ещё — в виде песочных часов: ABDC, ADBC;
Итого: 7 циклов

Во втором задании — те же циклы. В нём отличие только в том, что боковые грани квадрата разделили ещё одной вершиной. Ответ: 7 циклов.

Задание 3
Большой квадрат; маленький квадрат; 4 четырёхугольника между ними; 4 фигуры, образованные из предыдущих четырёхугольников, если у рядом расположенных убрать общую грань; ещё 4 фигуры, образованные из предыдущих, если у них убрать 2 грани, общих с внутренним квадратом. Дальше — сложнее. Пусть вершины большого квадрата будут носить названия A, B, C, D, маленького A1, B1, C1, D1. Тогда вот циклы: 4 фигуры, которые можно получить, если поочерёдно «вырезать» 4-хугольники, расположенные между внешним и внутренним квадратом, например ADCBB1A1; 4 фигуры, которые можно получить, если «вырезать» в 4-х предыдущих ещё и маленький квадрат, например: ADCBB1C1D1A1
Итог: 22
Устал 🙂 4-е задание не буду делать)))

Дмитрий Мыслитель (6233) Я нашёл вот эти циклы

Источник

Оценка количества простых циклов на графе

Введение

Формализация задачи

Оценка количества циклов

Замечания и обсуждение

Заключение

C++

Java

Python3

C#

Javascript

Ищем количество циклов в неориентированном графе

Как посчитать циклы в графе

Ищем количество циклов в неориентированном графе

Нахождение цикла

Помогите с информатикой и количеством циклов в графе

Не пропустите также: