На этом шаге мы рассмотрим отыскание контуров в ориентированных графах.

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

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

Алгоритм использует матрицу смежности 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.

Пример.

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

Текст этой программы можно взять здесь.

⁽¹⁾ Евстигнеев В.А. Применение теории графов в программировании. - М.: Hаука, 1985. - 352 с.

На следующем шаге мы начнем рассматривать вопросы связности графа.

Предыдущий шаг Содержание Следующий шаг