Количество компонент связности в дополнении заданного графа

    Тогда без промежуточных вершин:

С (-1) [ i , j ] = A [ i , j ]                   (A – матрица дополнения графа).

    Если  через две вершины из множества  {1 , … , k - 1} есть путь от i до j или есть два пути : от i до k и от k до j , то есть путь от i к j через вершины из множества {1, … , k}. Отсюда:

    C(k)[ i , j ] = C(k-1)[ i , j ]  | |  C(k-1)[ i , k ] & C(k-1)[ k, j ].

    По  полученной матрице связности определим  количество компонент связности.

  3.2. Структура программы

      Структуру программы изобразим на  рис. 3.1. 

   Рис. 3.1. Модульная структура программы

    Программа состоит из 6 модулей: main () – главная программа, vvod -функция ввода рёбер графа, vivod-функция вывода матриц, void matrica_dopolnenii – построение дополнения графа, void matrica_sviaznosti-  построение матрицы связности, void comp_sv- подсчет количества компонент связности.

    Сопряжение  модулей описаны в таблице 3.1. Все данные между модулями передаются в виде параметров, глобальных переменных в программе нет.

    Каждый  модуль транслировался отдельно. Их имена перечислены вместе с разработанной для данной программы библиотек graf.lib в файле проекта TROFIMOVA.prj. Модули  функции vvod, vivod, void matrica_dopolnenii void matrica_sviaznosti, void comp_sv помещены в библиотеку объектных модулей  graf.lib, и для их использования требуется включить в программу созданный в курсовой работе файл заголовков graf.h командой

    #include “graf.h”

Таблица 3.1.

Сопряжение  модулей 

 

3.3. Описание модулей 

    3.3.1. Главный модуль – main 

    ОБРАЩЕНИЕ ИЗ MS DOC: TROFIMOVA 

    ЗАГОЛОВОК: void main()

    ФУНКЦИЯ: ввод количества вершин, ввод списка ребер, вывод матрицы смежности, вывод дополнения графа, построение матрицы связности, подсчёт количества компонент связности, вывод результата и сообщений об ошибках. 

    ВХОДНЫЕ ДАННЫЕ: n-количество вершин.

    ВЫХОДНЫЕ  ДАННЫЕ: Нет. 

    РАБОЧИЕ ДАННЫЕ:

    gr[NMAX][NMAX]– граф.

    mtrsv[NMAX][NMAX] - матрица связности.

    i – номер вершины, с которой  начинается ребро.

    j – номер вершины,  которой заканчивается  ребро.

    n – количество вершин.

    kol – количество компонент связности.

    vp – вектор посещения. 

    АЛГОРИТМ: см. алгоритм 3.2. 

        Алгоритм 3.2. Алгоритм модуля main  

    void main () 

    {

         объявление;

          вывод сообщения №1;

          вывод сообщения №2;

       do

         {

          scanf("%d",&n);        /*ввод количества вершины*/

               if (n<=1)

                     вывод сообщение №7 об ошибке;

              if (n>NMAX)

                     вывод сообщение №7 об ошибке;

         }

      while (n<=1||n>NMAX);

      вывод сообщения №3;

      вызов vvod (n, gr);                             /* ввод графа смежности        */

      вывод сообщения №4;

      вызов vivod(n, gr);                            /* вывод матрицы смежности*/

      вызов matrica_dopolnenii(n, gr);     /* матрица дополнения графа */

      вывод сообщения №5;                         

      вызов vivod(n, gr);                             /* вывод матрицы дополнения*/

      вызов matrica_sviaznosti(n, gr, mtrsv); /* матрица связности*/

      вызов kol=comp_sv(n,mtrsv);       /* подсчет компонент связности*/

      вывод сообщения №6;

    }

    3.3.2. Модуль ввода графа – vvod. 

    ЗАГОЛОВОК: vvod(int n, int gr[NMAX][NMAX]) 

    ФУНКЦИЯ: Ввод графа в виде перечня ребер, перед которым указывается количество вершин n, и его преобразование в матрицу смежности gr. NMAX –  максимальное количество вершин.

    ВХОДНЫЕ ДАННЫЕ:   n-количество вершин в графе, граф.

    ВЫХОДНЫЕ ДАННЫЕ: матрица смежности графа (первые n строк и n столбцов матрицы NMAX*NMAX ).

    РАБОЧИЕ ДАННЫЕ:

         i – номер вершины, с которой начинается вводимое ребро;

         j – номер вершины,  которой заканчивается вводимое ребро.

      

    АЛГОРИТМ: см. алгоритм 3.3. 

    Алгоритм 3.3. Алгоритм модуля  vvod. 

    vvod (int n,int gr[][NMAX])

    {  int i,j;

         for (i=0;i<n;i++)

         for (j=0;j<n;j++)

            gr[i][j]=0;

           while (scanf("%d%d",&i,&j)==2)

           {                if (i==j)

                                        Вывод сообщения  об ошибке №8;  

                         if (i>=n||i<0||j>=n||j<0)

                                       Вывод сообщения об ошибке №8;

                                  if (gr[i][j]==1)

                                        Вывод сообщения об ошибке №9;

               else

                {gr[i][j]=1; gr[j][i]=1;  }

           }

    } 

3.3.3. Модуль вывода матрицы смежности/дополнения графа- vivod. 

    ЗАГОЛОВОК: vivod(int n, int gr[NMAX][NMAX]) 

    ФУНКЦИЯ: Вывод матрицы.

    ВХОДНЫЕ ДАННЫЕ:    n-количество вершин в графе, матрица смежности/дополнения графа.

    ВЫХОДНЫЕ  ДАННЫЕ: Нет.

    РАБОЧИЕ ДАННЫЕ:

    i – номер вершины, с которой  начинается ребро.

    j – номер вершины,  которой заканчивается  ребро.

    АЛГОРИТМ: см. алгоритм 3.4. 

    Алгоритм 3.4. Алгоритм модуля  vivod. 

    vivod (int n,int gr[][NMAX])

    {  объявление переменных  i и j;

          {/* Таблица матрицы смежности/ дополнения*/

                for(i=0;i<n;i++)                

                   printf(" %d",i);                              

                     printf("\n |");

                    for(i=0; i<n; i++)

                        printf("-");

                  /* Вывод матрицы смежности/ дополнения */

                  for(j=0;j<n;j++)

                       {   printf("\n%d",j);    

                          for(i=0;i<n;i++)

                          printf("%d ", gr[i][j]); }

       }                                                              

    } 

    3.3.4. Функция построения дополнения графа - void matrica_dopolnenii.

     

    ЗАГОЛОВОК: void matrica_dopolnenii(int n,int gr[NMAX][NMAX]) 

    ФУНКЦИЯ: построения дополнения графа.

    ВХОДНЫЕ ДАННЫЕ: n-количество вершин в графе, матрица смежности графа.

    ВЫХОДНЫЕ  ДАННЫЕ: матрица дополнения графа.

    РАБОЧИЕ ДАННЫЕ:

    i – номер вершины, с которой  начинается ребро.

    j – номер вершины,  которой заканчивается  ребро. 

    АЛГОРИТМ: см. алгоритм 3.5. 

    Алгоритм 3.5. Алгоритм модуля  void matrica_dopolnenii. 

    void matrica_dopolnenii(int n,int gr[NMAX][NMAX])

    {объявление переменных цикла i и j;

          for(i=0;i<n;i++)

               {for(j=0;j<n;j++)

                      получение дополнения графа (замена 0 на 1, 1 на 0);

               }

         обнуление главной диагонали;}

    3.6. Функция построения матрицы связности void matrica_sviaznosti (применение алгоритма Уоршела). 

    ЗАГОЛОВОК: void matrica_sviaznosti(int n, int gr[NMAX][NMAX],int mtrsv[NMAX][NMAX])

    ФУНКЦИЯ: построение матрицы связности графа.

    ВХОДНЫЕ ДАННЫЕ:    n – количество вершин в графе, матрица дополнения графа.

    ВЫХОДНЫЕ  ДАННЫЕ: матрица связности.

    РАБОЧИЕ ДАННЫЕ:

    i – номер вершины, с которой  начинается ребро.

    j – номер вершины,  которой заканчивается  ребро

    k – некоторая переменная цикла. 

    АЛГОРИТМ: см. алгоритм 3.6. 

    Алгоритм 3.6. Алгоритм модуля  void matrica_sviaznosti(int n, int gr[NMAX][NMAX],int mtrsv[NMAX][NMAX])

/*применение  алгоритма Уоршела*/

void matrica_sviaznosti(int n, int gr[NMAX][NMAX],int mtrsv[NMAX][NMAX])

  {

   объявление переменных цикла i, j и k;

           присваивание матрице связности значений полученного графа;

   применение  алгоритма Уоршела;

  } 

    3.3.7. Функция подсчета количества компонент связности -comp_sv 

    ЗАГОЛОВОК: int  comp_sv(int n, int mtrsv[NMAX][NMAX]). 

    ФУНКЦИЯ: подсчет количества компонент связности графа.