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

Министерство  образования Российской Федерации 

Казанский Государственный Технический Университет

имени А.Н. Туполева

      ---------------------------------------------------

Кафедра АСОИУ 
 
 
 
 

К У Р С О В  А Я   Р А  Б О Т А  

По  программированию на  языке высокого уровня 
 

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

(Задание  10) 
 
 
 
 

               ИСПОЛНИТЕЛЬ: студент группы 28203   С.Н. Трофимова

               РУКОВОДИТЕЛЬ: доцент кафедры АСОИУ З.Х. Захарова 

   Оценка_________________

   Подпись________________

   “___”_____________2007 г. 
 
 
 
 
 
 
 
 
 
 
 
 

ЛЕНИНОГОРСК 2007

 

СОДЕРЖАНИЕ 

1. ЗАДАНИЕ.

2. ОПИСАНИЕ ПРИМЕНЕНИЯ.

    2.1. Постановка задачи.

    2.2. Обращение к программе.

    2.3. Входные данные.

    2.4. Выходные данные.

    2.5. Сообщения.

       2.5.1. Информационные сообщения.

       2.5.2. Сообщения об ошибках.

3. ОПИСАНИЕ ПРОГРАММЫ.

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

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

   3.2.1. main – главный модуль.

      3.2.2. vvod – функция ввода данных.

      3.2.3.  vivod– функция вывода матрицы.

      3.2.4. matrica_dopolnenii– функция получения дополнения графа.

          3.2.5. matrica_sviaznosti – функция матрицы связности графа.

          3.2.6. comp_sv– функция  количества компонент связности.

4. ОТЛАДКА ПРОГРАММЫ.

    4.1. План отладки.

    4.2. Проектирование тестов программы.

          4.2.1. Тесты черного ящика.

          4.2.2. Тесты белого ящика.

    4.3 Отладочные средства.

    4.4 Отладка программы.

ЗАКЛЮЧЕНИЕ

СПИСОК  ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

1. Системные файлы проекта.
2. Текст программы модуля main
3. Текст программы модуля vvod
4. Текст программы модуля vivod
5. Текст программы модуля matrica_dopolnenii
6. Текст программы модуля matrica_sviaznosti
7. Текст программы модуля comp_sv
8. Результаты тестирования программы
9. Трудоемкость курсовой работы

 

    1. ЗАДАНИЕ

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

2. ОПИСАНИЕ ПРИМЕНЕНИЯ 

2.1. Постановка задачи 

          Разработанная программа  подсчитывает количество компонент  связности в дополнении заданного  графа с количеством вершин ≤ 150.

      В программе используются следующие  определения.

Граф  представляет собой множество точек (вершин, узлов) вместе с линиями,  соединяющими некоторые или все пары точек. Направленные  линии со стрелками называют дугами, не имеющие направления – ребрами.

    Вершины, соединенные ребром или дугой, называют смежными. Ребра, имеющие общую вершину, также называются смежными. Представление  квадратной булевой  матрицы, отражающей смежность вершин, называется матрицей смежности, где  

    a[ i , j ]= . 

    Дополнением графа является дополнение данного  графа до полного. В ограниченной решетке элемент называется дополнением элемента а , если и .

    Граф  связан тогда, когда его нельзя представит в виде объединения двух графов. Говорят, что две вершины связаны, если между ними существует их простая цепь.

    Матрица связности С размера n*n содержит элементы: 

     . 

    Матрица связности С получается :

    Обозначим С(k)[ i , j ] – есть путь от i к j через вершины множества {1, ... , k}.

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

    С (-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 ]. 

    Отношение связности вершин является эквивалентностью. Классы эквивалентности по отношению  к связности называют компонентом связности графа.

Справедливо равенство:

,

где p – число вершин;

      q – число ребер;

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

 

      Решаемая  задача иллюстрируется рис. 2.1. и 2.2. На рис. 2.1. изображен граф, для которого необходимо определить количество компонент связности в его дополнении. На рис. 2.2. изображено дополнение графа с 2 компонентами связности.  

2.2. Обращение к программе 

      Запуск  программы производится командой операционной системы MS DOS вида

            TROFIMOVA<входной файл >выходной файл

где TROFIMOVA – имя файла, содержащего исполняемый модуль программы, входной файл – имя входного файла, выходной файл – имя выходного файла. Файлы задаются в произвольном порядке. Если входной файл не указан, исходные данные вводятся с клавиатуры, если не указан выходной файл, результаты выводятся на экран дисплея. 

2.3. Входные данные 

    Входными  данными программы является граф. Выбор метода представления графа  зависит от конкретной задачи. В  данном случае граф представляется последовательностью (списком) рёбер, перед которой указывается количество вершин n (где n не должно быть меньше 1 и больше 150). Такой метод очень удобен для внешнего представления графа при вводе.

    Каждое  ребро задаётся парой номеров  вершин. Они нумеруются от 0 до n-1. Номера вершин разделяются пробелом. Ввод количества вершин заканчивается клавишей <Enter>. Ввод ребра также заканчивается клавишей <Enter>. а ввод списка ребер - <Ctrl+z>, <Enter> (обозначает конец файла).

    Ниже  приводится пример задания входных данных:

    4

    <Enter> 

    0 1

    0 3

    1 2

    2 3

    <Ctrl+z><Enter> 

2.4. Выходные данные 

    Результатом работы программы, то есть её выходными данными будут сообщения, последовательно выводимые на экран дисплея. При этом входные данные тоже можно увидеть на экране. Рассмотрим результаты обработки графа на следующем примере: 

    Zadanie: Podchitat kol-vo component sviaznosti v dopolnenii     zadannogo grafa.

           Vvedite kol-vo verchin (ot 2 do 150).

      4

    <Enter> 

    Vvedite rebra grafa (ctrl+z).

    0 1

    1 2

    3 2

    3 0

    <Ctrl+z>

    Matrica smegnosti:

                      0  1  2  3

    

               0

               1

               2

               3 

    Matrica  dopolnenia grafa:

                      0  1  2  3

    

               0

               1

               2

               3 

    Kol-vo  component sviaznosti: 2. 

    2.5. Сообщения 

    Программа может выдавать различные сообщения  в процессе работы, это зависит  от ситуаций возникающих при выполнении задачи. Приведем список имеющихся  сообщений: 

    2.5.1. Информационные сообщения 

1. Zadanie: Podchitat kol-vo component sviaznosti v dopolnenii     zadannogo grafa.
2. Vvedite kol-vo verchin (ot 2 do 150).
3. Vvedite rebra grafa (Ctrl+z).
4. Matrica smegnosti.
5. Matrica  dopolnenia grafa.
6. Kol-vo  component sviaznosti.

 

   2.5.2. Сообщения об ошибках. 

    7. Error!!! Vvedite kol-vo verchin ot 2 do 150.

    8. Error!!! Vvedeno nedopustimoe znachenie parametra.

    9. Error!!! Dublirovanie reber! 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   3.ОПИСАНИЕ ПРОГРАММЫ  

   3.1. Метод решения задачи 

    Разработанная программа подсчитывает количество компонент связности в дополнении заданного графа с количеством вершин ≤ 150.

    Решая данную задачу мы строим во-первых матрицу  смежности данного графа.

    Матрица смежности – квадратная матрица  n*n с элементами.

    a[ i , j ]= .

    Так как нам необходимо дополнение заданного  графа, опираясь на матрицу смежности строим дополнение графа. Дополнение графа находим,  преобразовав матрицу смежности, заменяя 0 на 1,  а 1 на 0 и обнуляя главную диагональ.

          Для определения  количества компонент связности  необходимо построить матрицу связности.

    Матрица связности С размера n*n содержит элементы:

     .

    Матрица связности С получаем, используя  алгоритм Уоршала :

    Обозначим С(k)[ i , j ] – есть путь от i к j через вершины множества {1, ... , k}.