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

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

Искомый цикл состоит минимум из двух вершин и не имеет "лишних" рёбер, то есть, представляет собой кольцо вида 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 [8377 просмотров]