Медиана графа

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

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

Говорят, что ребро e = (u, v) соединяет вершины u и v. Ребро e  и вершина u (а также e и v) называются инцидентными, а вершины u и v смежными.  Ребра инцидентные одной и той же вершине также называются смежными.   

Расстояние между двумя вершинами – это длина кратчайшего пути, соединяющего эти вершины.

Обход графа – это некоторое систематическое прохождение его вершин (и/или ребер). Обходя граф, мы двигаемся по ребрам (дугам) и проходим все вершины. При этом можно получить  много информации, которая необходима для дальнейшей обработки графа, поэтому обход графа является основой многих алгоритмов исследования структуры графа.

Цель:

Найти медиану графа, т.е. такую его вершину, что сумма  его расстояний от неё до остальных  минимальна.

Данная цель достигается  решением следующих задач:

1. выбор алгоритма
2. выбор метода решения
3. разработка на языке программирования С
4. проектирование тестов

 

ВЫБОР АЛГОРИТМА

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

Разработанная программа  находит медиану в заданном графе  с количеством вершин n<= 10.

В программе используются следующие определения . Граф – это пара (V, E), где V – конечное непустое множество вершин, а E – множество неупорядоченных пар <u, v> вершин из V, называемых ребрами. Рассматривается класс графов без петель, т.е. ребер, в которых u = v.

Путь, соединяющий вершины u и v, - это последовательность вершин v₀,  v₁, . . . , v_k(k>= 0) такая, что v = u, v = v и для любого i (0 <= i<= k-1) вершины v_i и v_i+1 соединены ребром.

Длина пути v₀, v₁, … , v_k равна k (количеству ребер). Путь замкнут, если v₀ = v_k. Путь называется простым, если все вершины различны. Расстояние – это длина кратчайшего пути между вершинами. Граф связан, если для любых пар вершин <u, v> существует соединяющий их путь. Медианой графа называют такую вершину, что сумма расстояний от нее до остальных минимальна.

Решаемая задача иллюстрируется на рис. 2.1.

Рис. 2.1

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

Вызов программы происходит в программной среде MS-DOS, так как язык программирования, на котором написана программа (TURBO C) позволяет писать программы только под эту операционную систему. Файл, реализующий данную программу, называется zulka.exe.

 

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

Входные данные программы  представляют собой граф. Граф представляется в виде перечня ребер, перед которым  указывается количество вершин. Каждое ребро задается парой номеров  вершин. Вершины нумеруются от 0 до n-1, где n – количество вершин графа (n<=20). Ребра можно задавать в произвольном порядке. Все числа разделяются пробелами и/или переводом строки (клавиша <Enter>).

При вводе данных с  клавиатуры после ввода всех данных нажимается <Ctrl-Z> (обозначает конец файла) и <Enter>.

 Например, граф, показанный на рис. 2.1, можно ввести с клавиатуры следующим образом:

5

0 1

0 2

0 3

1 4

1 3

2 3

3 4

<Ctrl-Z><Enter>

Другой вариант ввода:

0 1 0 2 0 3 1 4 1 3 2 3 3 4<Ctrl-Z><Enter>

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

Результатом работы программы  является текст, содержащий матрицу смежности и матрицу весов входного графа, и последовательность сообщений, выводимых на экран дисплея. Возможные сообщения приведены в разделе 2.5.

Результаты обработки  графа, показанного на рис. 2.1, приведены  на рис. 2.2. Сделано предупреждение, т.к. ребро 1-4 введено дважды.

Введите граф (количество вершин от 1 до 20):

5

Введите последовательность ребер:

0 1

0 2

0 3

1 4

1 3

2 3

3 4

4 1  ^{^}Z

Матрица весов:

0	0	1	2	3	4
0	0	1	1	1	0
1	1	0	0	1	1
2	1	0	0	1	0
3	1	1	1	0	1
4	0	1	0	1	0

 

Предупреждение: было дублирование ребер (игнорировалось).

Медиана – 3, расстояние – 4.

Рис. 2.2. Пример результата работы программы

Сообщения

В угловых скобках  указаны названия вставляемых в  сообщения величин.

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

1. Медиана - <вершина>, расстояние - <длина>;
2. Введите граф (количество вершин от 1 до 20);
3. Введите последовательность ребер.

При вводе с клавиатуры необходимо ввести целое число, затем  вводить пары целых чисел –  номера вершин графа, по правилам, описанным  в 2.3.

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

1. Ошибка: нет входных данных;
2. Ошибка: количество вершин должно быть от 1 до 20.
3. Ошибка: ребро должно содержать две вершины.
4. Ошибка: недопустимое количество вершин (1<=n<=20)
5. Предупреждение: было дублирование ребер (игнорировалось).

 

РАЗРАБОТКА ПРОГРАММЫ  НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ C

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

У графа длина (вес) пути определяется как сумма длин его  ребер. Расстояние D[i][j] между вершинами i и j – длина кратчайшего пути между ними. Считают, что расстояние от вершины до нее самой равно нулю: D[i][i] = 0. У не взвешенного графа вес ребра равен 1; длина пути и расстояние измеряются числом ребер.

Кратчайший путь в  графе от заданной вершины до одной  или до всех вершин можно найти  методом обхода в ширину. Кратчайшие пути и расстояния между всеми  вершинами быстрее определяются через матрицу расстояний или алгоритм Флойда.

Обозначим D(k) [i][j] – длина кратчайшего пути от вершины I к вершине j через вершины из множества {1, … , k}.

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

D(-1)[i][j] = W[i][j]

где W – матрица весов с бесконечными весами отсутствующих ребер.

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

D(k)[i][j] = D(k-1)[i][j],

иначе его можно разделить на два пути, проходящих через {1, …, k-1}: от вершины i до вершины k и от вершины k до вершины j , причем:

D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j].

отсюда:

D(k)[i][j] = min (D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])

Расстояние между вершинами  i и j равно:

D[i][j] = D(n-1)[i][j].

Отсюда получен алгоритм Флойда (1) для вычисления расстояний D[i][j] между всеми парами вершин графа.

Алгоритм 1. Вычисления расстояний D[i][j] между всеми парами вершин графа

D = W;  /* Матрица весов (отсутствие ребра -0) */

for (i=0; i<n; i++)   D[i][i] = 0;     /*  если D[i][i] бесконечны  */

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

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

if (D[i][k] != 0)

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

D[i][j] = min (D[i][j], D[i][k] + D[k][j]);

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

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

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

Программа состоит из трех функционально-прочных модулей: glav – главная программа, vv_m_sm – ввод графа, obrab – вывод матрицы расстояний.

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

 

 

 

 

Таблица 1

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

№	Входные данные	Выходные данные
1	Количество  вершин.	матрица смежности, код ошибки.
2	Номер сообщения	-
3	Количество вершин, матрица  смежности.	Матрица расстояний

Все модули транслировались  отдельно. Модули obrab, vv_m_sm  помещены в проект zulka.prj, и для их использования требуется включить в программу созданный в курсовой работе файл заголовков graf.h командой

#include "graf.h"

Для записи алгоритмов использован псевдокод на базе языка Си.

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

1) glav– главный модуль

ОБРАЩЕНИЕ ИЗ MSDOS: zulka

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

ФУНКЦИЯ: Ввод графа, вычисление медианы графа, вывод результата.

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

ВЫХОДНЫЕ ДАННЫЕ:   z – медиана,  mdl - расстояние.

ЗНАЧЕНИЕ:   Нет.

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

g– матрица смежности графа;

n- количество вершин;

d – матрица расстояний;

i, j– номера вершин;

dl– сумма расстояний;

z – вычисляемая вершина;

mdl – признак не связанности;

kz- код завершения подпрограммы;

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

puts (“\n  Задача: Найти медиану графа , т. е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна \n”);

puts (“\nВведите граф (количество вершин от 1 до 20): \n”);

Ввод n;

if(n>NMAX || n< 1)

{puts (“\nОшибка: количество вершин должно быть от 1 до: \n”);

puts (“\nРешение прекращено \n”);

}

else

kz=vv_m_sm(n,g); /* ввод графа     */

if(kz>1)

{Вывод сообщения kz;

puts (“\nРешение прекращено \n”);

}

else

{if(kz==1)

puts (“\nПредупреждение: было дублирование ребер \n”);

obrab(n,g,d); /* Вызов матрицы расстояний */

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

{ dl=0;

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

{ if(d[i][j]!=0)

dl = dl + d[i][j];

}

if(dl < mdl)

{ mdl = dl;

z = i;

}

}

printf("\n Медиана - %d, расстояние- %d\n",z,mdl);  /* Вывод медианы */

printf (“\nРешение прекращено \n”);

}

getch();

}

2) vv_m_sm – ввод графа

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

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

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

ВЫХОДНЫЕ ДАННЫЕ:

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

g – матрица смежности графа.

ЗНАЧЕНИЕ:

- ввод завершен без  ошибок;

- ввод завершен, но  было повторение ребер (игнорировалось);

- ошибка: входной файл пуст (ввод прекращен);

- ошибка: недопустимый номер вершины (ввод прекращен);

- ошибка: только одна  вершина в ребре (ввод прекращен);

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

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

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

pr- было повторение ребер.

 Алгоритм модуля vv_m_sm

if (конец входного файла)

return 2; /* входной файл пуст */

pr=0;

puts ( “\nВведите последовательность графа, в конце <Ctrl+Z> \n”);

обнуление матрицы g;

while (не конец входного файла) ввод i;ввод j;

if (конец входного файла)return 5;  /* только одна вершина в ребре */

{if (i не допустимо) return 4; /*недопустимый номер вершины*/

if (было ребро i-j) pr = 1;  /* повторение ребер */

g[i][j]=g[j][i] = 1;

}

return pr;   /* 0 - успех или 1 - было повторение ребер */

 

3) obrab – вывод матрицы расстояний

ЗАГОЛОВОК: void obrab (int n, int g[][NMAX], int d[][NMAX])

ФУНКЦИЯ:  Вывод матрицы  расстояний d с количеством вершин n.

ВХОДНЫЕ ДАННЫЕ:

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

g – матрица смежности графа

ВЫХОДНЫЕ ДАННЫЕ:   матрицы  расстояний

ЗНАЧЕНИЕ:    Нет.

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

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

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

k – множество вершин.

Алгоритм модуля obrab

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

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

d[i][j] = g[i][j];

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

d[i][i] = 0;

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

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

if(d[i][k] != 0)

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

if(d[i][k] + d[k][j]< d[i][j])

d[i][j] = d[i][k] + d[k][j];

puts ("\nМатрица расстояний \n"); /* вывод матрицы расстояний*/

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

printf("%2.1d ",i);

printf("\n┌");

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

printf("─");

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

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

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

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

}

}

 

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

План  отладки

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

1. Тестирование модуля ввода графа, при этом создавалась специальная программа, которая выводила матрицу смежности.
2. Тестирование модуля обработки графа совместно с функцией ввода и главной функцией.
3. Совместное тестирование всех модулей программы.

 

ПРОЕКТИРОВАНИЕ ТЕСТОВ

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

Тестирование чёрного  ящика — стратегия (метод) тестирования функционального поведения объекта (программы, системы) с точки зрения внешнего мира, при котором не используется знание о внутреннем устройстве тестируемого объекта. Под стратегией понимаются систематические методы отбора и создания тестов для тестового набора.

Для проектирования тестов программы методами черного  ящика  с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 2, в скобках указаны их номера.

Таблица 2

Области входных/выходных данных тестов программы

Входное/выходное условие (значение)	«Правильные» классы эквивалентности	«Неправильные»  классы эквивалентности
Количество  вершин n	1… NMAX (1)	<1 (2) , >NMAX (3)
Количество  вершин в ребре	2 (4)	< 2 (5),> 2 (6)
Номер вершины	О..n-l (7)	<0 (8), >n-1 (9)
Сообщения программы	1 (10), 2 (11), 6 (12), 9(13)	3 (14), 4(15), 5(16), 7(17), 8 (18), 10(19)
Входные данные	существуют (20)	не существуют (21)
Выходные данные	существуют (22),	не существует (23)