Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

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

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

(Задание 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 Отладка программы.

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЯ

Системные файлы проекта.
Текст программы модуля main
Текст программы модуля vvod
Текст программы модуля vivod
Текст программы модуля matrica_dopolnenii
Текст программы модуля matrica_sviaznosti
Текст программы модуля comp_sv
Результаты тестирования программы
Трудоемкость курсовой работы

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> (обозначает конец файла).

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

<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).

<Enter>

Vvedite rebra grafa (ctrl+z).

0 1

1 2

3 2

3 0

<Ctrl+z>

Matrica smegnosti:

0 1 2 3

0 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

Matrica dopolnenia grafa:

0 1 2 3

0 0 1 0

0 0 0 1

1 0 0 0

0 1 0 0

Kol-vo component sviaznosti: 2.

2.5. Сообщения

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

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

Zadanie: Podchitat kol-vo component sviaznosti v dopolnenii zadannogo grafa.
Vvedite kol-vo verchin (ot 2 do 150).
Vvedite rebra grafa (Ctrl+z).
Matrica smegnosti.
Matrica dopolnenia grafa.
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. Метод решения задачи

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

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

a[ i , j ]= .

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

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

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

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

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

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

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

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.

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

№	Входные данные	Выходные данные
1	Количество вершин n, граф.	Матрица смежности.
2	Количество вершин n, матрица смежности.	-
3	Количество вершин n, матрица смежности.	Матрица дополнений
4	Количество вершин n, матрица дополнений.	-
5	Количество вершин n, матрица дополнений.	Матрица связности
6	Количество вершин n, матрица связности	Количество компонент связности графа.

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;

{

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]).

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

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