Одной из важнейших задач, связанных с контурами является задача нахождения множества всех контуров [1, с.105]. Трудность ее состоит прежде всего в том, что число контуров ориентированного графа может быть экспоненциально большим относительно числа вершин. Поэтому при разработке алгоритмов внимание обращается не на полную трудоемкость алгоритма, а на относительную, т.е. на трудоемкость, приходящуюся на один контур.
Алгоритм отыскания множества вершин, принадлежащих контуру заданной длины
Алгоритм использует матрицу смежности A(G) и матрицу Ak, если длина контура равна k. Выберем некоторое i, такое, что aii(k)=1. Это означает, что вершина vi принадлежит контуру длины k.
Тогда вершина vj принадлежит тому же контуру, если выполняются следующие три условия:
ajj(k)=1;
для любого n aij(n)=1, т.е. существует путь длины n из vi в vj;
aji(k-n)=1, т.е. существует путь длины k-n из vj в vi.
Таким образом, для каждой вершины i графа мы легко можем построить множество вершин, каждый элемент которого принадлежит некоторому контуру длины k.
Нашла реализацию нужного алгоритма на С++, а так как с этим языком знакома довольно поверхностно, то не совсем могу разобраться в коде.Помогите. чем можете...Скачала кучу инфы по С++ ,но там почти все для бывалых пользователей...вот текст программы, можно просто прокомментировать, буду очень благодарна, потому ка кнадо все переделать под паскаль...
#include <iostream.h>
#define MaxNodes 4
#define Stepen 10
class Warshall
{
private:
unsigned Adj[MaxNodes][MaxNodes]; //Матрица смежностей.
//Массив степеней матрицы смежностей.
unsigned AdjN[Stepen][MaxNodes][MaxNodes];
void Power(int);
public:
void Vvod();
void Step();
void Kontur();
};
void Warshall::Vvod()
{
//Ввод матрицы смежностей заданного графа.
cout <<"Вводите элементы матрицы смежностей по строкам:\n";
for (int i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++)
{
cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
cin >> Adj[i][j];
}
}
void Warshall::Step()
//Вычисление степеней матрицы смежностей.
{
for (int l=0;l<Stepen;l++)
{
Power(l);
}
}
void Warshall::Power(int n)
//Возвращает значение n-й степени матрицы A.
{
unsigned Z[MaxNodes][MaxNodes];
unsigned C[MaxNodes][MaxNodes];
unsigned Val;
for (int i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++) C[i][j]=Adj[i][j];
for (int m=0;m<n-1;m++)
{
for (int i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++)
{
Val = 0;
for (int k=0;k<MaxNodes;k++)
Val = Val || (Adj[i][k] && C[k][j]);
Z[i][j] = Val;
}
for (i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++) C[i][j]=Z[i][j];
}
for (i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++)
AdjN [n][i][j] = C[i][j];
}
void Warshall::Kontur()
//Отыскание контуров заданной длины.
{
unsigned n;
cout << "Вводите длину контура: ";
cin >> n;
for (int m=1;m<n;m++)
{
for (int i=0;i<MaxNodes;i++)
if ( AdjN [m][i][i]==1 )
//Вершина i+1 принадлежит контуру длины n.
{
cout << "Вершина " << (i+1) <<
" образует контуры длины " << (m+1) << " с вершинами из множества: {";
for (int j=0;j<MaxNodes;j++)
{
if ( AdjN[m][j][j]==1 )
//Вершина j принадлежит контуру длины m.
for (int l=0;l<m;l++)
if ( AdjN[l][i][j]==1 && m-l>0
&& AdjN[m-l][j][i]==1 )
{
cout << (j+1) << ' ';
goto Metka;
}
Metka:;
}
cout << '}' << endl;
}
cout << endl;
}
}
void main()
{
Warshall A;
A.Vvod();
A.Step();
A.Kontur();
}