Практическая работа 12. Алгоритм отыскания множества вершин, принадлежащих контуру заданной длины

Практическая работа 12. Алгоритм отыскания множества вершин, принадлежащих контуру заданной длины

Алгоритм использует матрицу смежности A(G) и матрицу A^k, если длина контура равна k. Выберем некоторое i, такое, что a_ii^(k)=1. Это означает, что вершина v_i принадлежит контуру длины k.

Тогда вершина v_j принадлежит тому же контуру, если выполняются следующие три условия:

a_jj^(k)=1;
для любого n a_ij⁽ⁿ⁾=1, т.е. существует путь длины n из v_i в v_j;
a_ji^(k-n)=1, т.е. существует путь длины k-n из v_j в v_i.

Таким образом, для каждой вершины i графа можно построить множество вершин, каждый элемент которого принадлежит некоторому контуру длины k.

1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.

2. Откомпилируйте предложенную программу отыскания множества вершин, принадлежащих контуру заданной длины

#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();}