Курсовая работа на тему Диаметр графа после удаления в нем висячих вершин

Оглавление

Вступление

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки
Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это непустое множество вершин или узлов, E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами. V (а значит и E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) рёбра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф
Основная статья: Ориентированный граф
Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
V это непустое множество вершин или узлов, A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w.
Смешанный граф
Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного.
В данной курсовой роботе используется модифицированное FO ориентированный граф.
модифицированное FO представление: В MFO-представлении графа вместо разделителей 0 используется дополнительный массив P длинной N, в котором указываются верхние границы окончания списков номеров вершин в массиве G, смежных с заданной вершиной по выходящим дугам. Для не орграфов и мульти графов длина массива G равна 2xq, а массива P – N. Для орграфов и псевдо графов длина массива G равна q, а массива P – N.
Для хранения весов вершин и ребер (дуг) применяются дополнительные массивы V и W, где элементы vi и wj содержат значения весов для вершин vi и ребра (дуги) lj. Для не орграфов и мульти графов MFO и FI представления совпадают.
Пример задания векторов G и P для графа изображённого ниже:
P = {5 1 6 6 4 3}; G = {1 3 5 5 6 6};
2

1
6
4
3
5

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

Используя технологию нисходящего проектирования написать программу для сравнения на эквивалентность двух ориентированных графов с числом вершин n<20 и числом дуг m<50 по диаметру графа после удаления в нём висячих вершин. Ввод графа задаётся в модифицированном FO представлении в виде 2-х векторов (Вектор ограничителей и вектор списков выходных дуг). Предусмотреть ввод графа с файла и экрана.

Входные данные Входные формы:

Входные данные представлены в следующей таблице:

Наименование
Тип
Диапазон
Назначение

1

n1

Целый

1<n1<=20

Кол-во вершин 1-го графа

2

m1

Целый

1<m1<=50

Кол-во дуг 1-го графа

3

G1i

Массив целых чисел

0<=G11<=n1-1
1<=i<=m1
G1i-1<=G1i<=2m1
G1n1 = m1

Вектор ограничителей 1-го графа

4

P1i

Массив целых чисел

0<=P1i<=n1
1<=i<=m1

Вектор списков дуг 1-го графа

5

n2

Целый

0<n2<=20

Кол-во вершин 2-го графа

6

m2

Целый

1<m2<=50

Кол-во дуг 2-го графа
G2i

Массив целых чисел

0<=G11<=n1-1
1<=i<=m1
G1i-1<=G1i<=2m1
G1n1 = m1

Вектор ограничителей 2-го графа

7

P2i

Массив целых чисел

0<=P1i<=n2
1<=i<=m2

Вектор списков дуг 2-го графа
2.1. Входные формы:
2.2. Входной формат текстового файла:

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

В зависимости от полученного результата сравнения графов пользователю будет выдано текстовое сообщение. Если графы эквивалентны, то результатом будет сообщение:
«Графы эквивалентны»
В противном случае результатом работы программы будет сообщение:
«Графы не эквивалентны»
Выходные формы:
Метод решения:

В зависимости от значения переключателя на форме осуществляется ввод данных с клавиатуры или из текстового файла, с контролем корректности ввода данных. При вводе графов удаляются висячие вершины и строятся матрицы смежности(MS). Для получения диаметра графа необходимо в начале вычислить матрицу расстояний графа(MR).Максимальное значение в этой матрице и будет диаметром графа. Ниже представлен алгоритм получения матрицы MR.
Пусть r вычисленные значения расстояний в матрице MR. Используем две вспомогательные матрицы В1 и В2.
п1. r=1, В1= MS , MR= MS
п2. В2=В1* MS, r=r+1; // умножение матриц
п3. если (MR[I,j]=0 и B2[I,j] <>0) то MR[I,j]= r
п4. если в п3 матрица расстояний не изменялась ,то конец вычислений, иначе
В1=В2 и повторить п2.
Аномалии:

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

Наименование

Условия возникновения

Реакция

1

Некорректный ввод кол-ва вершин 1-го графа (при вводе с файла)

(n1>20) или (n1<0)
или !n1

Вывод сообщения: ”Ошибка ввода кол-ва вершин 1-го графа! “ (Образец 1)

22

Некорректный ввод кол-ва ребер 1-го графа (при вводе с файла)

(m1>50) или ( m1<0)
или !m1

Вывод сообщения: ”Ошибка ввода кол-ва ребер 1-го графа!” (Образец 2)

33

Элемент массива G1 1-го графа недопустим (ввода с экрана)

!G1 или G1i<G1i-1
или G1i >2m1

Вывод сообщения: ”Элемент G1 1-го графа, недопустим!“ (Образец 3)

44

Количество элементов массива G1 1-го графа неверно (ввод с экрана)

(i<1) или (i>m1)
или !m1

Вывод сообщения: ” Количество элементов мас сива G1 1-го графа неверно!“ (Образец 4)

55

Элемент массива P1 1-го графа недопустим (ввода с экрана)

!P1 или P1i<0)
или (P1i>n1)

Вывод сообщения: ”Элемент P1 1-го графа, недопустим!“ (Образец 5)

66

Количество элементов массива P1 1-го графа неверно (ввод с экрана)

(i<1) или (i>m1)

Вывод сообщения: ” Количество элементов массива P1 1-го графа неверно!“ (Образец 6)

77

Некорректный ввод кол-ва вершин графа (при вводе с файла)

(n >20) или (n <0)
или !n2

Вывод сообщения: ”Ошибка ввода кол-ва вершин графа!” (Образец 7)

8

Некорректный ввод кол-ва ребер графа (при вводе с файла)

(m>50) или (m<0)
или !m2

Вывод сообщения: ”Ошибка ввода кол-ва ребер графа! “ (Образец 8)

99

Элемент массива G2 2-го графа недопустим (ввода с экрана)

!G2 или G2i<G2i-1
или G2i >2m2

Вывод сообщения: ”Элемент G2 2-го графа, недопустим!“ (Образец 9)

110

Количество элементов массива G2 2-го графа неверно (ввод с экрана)

(i<1) или (i>m2)

Вывод сообщения: ” Количество элементов массива G2 2-го графа неверно!“ (Образец 10)

111

Элемент массива P2 2-го графа недопустим (ввода с экрана)

!P2 или
(P2i<0) или (P2i>n2)

Вывод сообщения: ”Элемент P2 2-го графа, недопустим!“ (Образец 11)

112

Количество элементов массива P2 2-го графа неверно (ввод с экрана)

(i<1) или (i>m2)

Вывод сообщения: ” Количество элементов массива P2 2-го графа неверно!“ (Образец 12)
Функциональные тесты:

Функциональные тесты представлены в следующей таблице:

Назначение теста

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

Результат

1

Проверка аномалии 1

21 3
……

Вывод сообщения по образцу 1

2
Проверка аномалии 2

4 51
…….

Вывод сообщения по образцу 2

3

Проверка аномалии 3

n1 m1 n2 m2
6

4
G1 P1 G2 P2
2458

123e324

Вывод сообщения по образцу 5

4
Проверка аномалии 4

n1 m1 n2 m2
4

3
G1 P1 G2 P2
2486

12479
Вывод сообщения по образцу 6
5
55

Проверка аномалии 5

n1 m1 n2 m2
8

6
G1 P1 G2 P2
1 2 4 50 9

24863254
Вывод сообщения по образцу 3

6

Проверка аномалии 6

n1 m1 n2 m2
4

3
G1 P1 G2 P2
12543

124

Вывод сообщения по образцу 6

77

Проверка аномалии 7

21 3
……

Вывод сообщения по образцу 7

8

Проверка аномалии 8

4 51
…….

Вывод сообщения по образцу 8

99

Проверка аномалии 9

n1 m1 n2 m2
6
4
4

4

G1 P1 G2 P2
123e324
2458
2244

2424

Вывод сообщения по образцу 9

110

Проверка аномалии 10

n1 m1 n2 m2
4
3
4

4

G1 P1 G2 P2
12543
124
2244

2424

Вывод сообщения по образцу 10

111

Проверка аномалии 11

n1 m1 n2 m2
8
6
4

4

G1 P1 G2 P2
1 2 4 50 9
2
2
4
4

24863254
2424
Вывод сообщения по образцу 11

112

Проверка аномалии 12

n1 m1 n2 m2
4
3
4

4

G1 P1 G2 P2
2244

2424

124
12543
Вывод сообщения по образцу 12

13

Нормальная работа

n1 m1 n2 m2
4

3
4

3
G1 P1 G2 P2
4213

124
124

2431

Вывод сообщения
Графы эквивалентны

114

Нормальная работа

n1 m1 n2 m2
6

4
4

3
G1 P1 G2 P2
512463

1345

234

4321

Вывод сообщения
Графы не эквивалентны

Нисходящее проектирование:

АЛГОРИТМ Курсовой_проект
<Описание переменных> (см. спецификацию)
НАЧАЛО
ЕСЛИ (ввод с файла) ТО
Выбор файла и создание потока(1.1)
перепись 1-го графа с частичным контролем из файла на экран; (1.2)
ЕСЛИ (ошибка) ТО
вывод («В данных на файле в первом графе ошибка!»);
Выход;
КЕСЛИ
перепись 2-го графа с частичным контролем из файла на экран;
ЕСЛИ (ошибка) ТО
вывод («В данных на файле во втором графе ошибка!»);
Выход;
КЕСЛИ
Закрыть поток.
КЕСЛИ
Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности MS1 (1.3)
ЕСЛИ (ошибка) ТО
вывод («В данных на форме в первом графе ошибка»)
Выход;
КЕСЛИ
Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности MS2
ЕСЛИ (ошибка) ТО
вывод («В данных на форме во втором графе ошибка»)
Выход;
КЕСЛИ
Поиск и удаление висячих вершин 1-го графа (1.4)
ЕСЛИ ( n < 2 ) ТО
Вывод сообщения («Граф 1 вырожденный»)
Выход;
КЕСЛИ
Поиск и удаление висячих вершин 2-го графа;
ЕСЛИ ( n < 2 ) ТО
Вывод сообщения («Граф 2 вырожденный»)
Выход;
КЕСЛИ
Расчет диаметра 1-го графа d1(1.5)
Расчет диаметра 2-го графа d2;
ЕСЛИ (d1=dr2) ТО
вывод («Графы эквивалентны»);
ИНАЧЕ
вывод («Графы не эквивалентны»);
КЕСЛИ
КОНЕЦ

Из текста алгоритма видно, что в нем имеется 5 подзадачи (1.1-1.5).

Дальнейшее проектирование буду выполнять следующим способом:
Указанные подзадачи (1.1-1.5) реализуются «заглушками». Заглушка – это алгоритм (метод) написанный на языке программирования с правильным заголовком и с упрощенным либо пустым блоком. Указанные заглушки подставляются в основной алгоритм, и затем он в свою очередь записывается на языке программирования и вместе с «заглушками» отлаживаем программу. После отладки переходим к детализации отдельных подзадач таким же способом.
Проектирование будем выполнять вторым способом. Напомним, что при проектировании подзадач имеется три варианта: реализация подзадачи в виде блока, в виде метода без типа и виде метода с возвратом значения некоторого типа.
Реализация подзадачи 1.1. Выбор файла и создание потока (подзадачу реализуем в виде блока)
Программирование будем выполнять в Microsoft Visual Studio 2010 на языке Visual C# на платформе Windows 7 , NET Framework 4.0.

string filename;
if (openFileDialog1.ShowDialog ()== DialogResult.OK)
{
filename = openFileDialog1.FileName;
//создание потока и подсоединение к файлу
Streamreader Potok = new StreamReader(filename);
}
else
{
MessageBox.Show( “Файл не выбран!”);
return ;
}
Реализация подзадачи 1.2. Ввод графа с файла на экран с частичным контролем. Подзадачу реализуем в виде метода без типа.
Для размещения параметров графа n и m используем компоненты NumericUpDown, что позволит уменьшить количество проверок, а для размещения векторов P и G, компоненту TextBox1 и TextBox2.

public void Move_Gr_fileToEcran (StreamReader Potok, NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref bool error)
{
MessageBox.Show(“Выполняется перенос графа с файла на экран”);
if( CB1.Cheked )
error=true;
else
error=false;
}
Реализация подзадачи 1.3. Ввод данных с экрана с контролем и построением матрицы смежности. Подзадачу реализуем в виде метода без типа.

public void Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref int n, ref int m, ref int [,] MS, ref bool error)
{
MessageBox.Show (“Выполняется ввод графа с экрана и построение матрицы”);
if( CB2.Cheked )
error=true;
else
error=false;

}
Реализация подзадачи 1.4. Поиск и удаление висячих вершин. Подзадачу реализуем в виде метода без типа.

public void Poisc_ver(ref int [,]MS, ref int n)
{
MessageBox.Show(“Выполняется поиск и удаление висячих вершин”);
n=1;
}
Реализация заглушки 1.5. Расчет диаметра графа. Подзадачу реализуем в виде метода с типом результата (целое число)

public int Diametr( int[,]MS)
{
MessageBox.Show(“Находим диаметр графа”);
return 2;
}

Подставляем «заглушки» в основной алгоритм:

АЛГОРИТМ Курсовой_проект
int [,] MS1;// инициализация матрицы смежности
int [,] MS2;// инициализация матрицы смежности
string filename;
bool error;
НАЧАЛО
ЕСЛИ (ввод с файла) ТО
//Выбор файла и создание потока(1.1)
if (openFileDialog1.Show == DialogResult.OK)
{
filename = openFileDialog1.Filename;
//создание потока и подсоединение к файлу
StreamReader Potok = new StreamReader(filename);
}
else
{
MessageBox.Show( “Файл не выбран!”);
return;
}
//перепись 1-го графа с частичным контролем из файла на экран; (1.2)
public void Move_Gr_fileToEcran (Potok, nUDn, nUDm, tBG, tBP, ref error)
ЕСЛИ (error) ТО
вывод («В данных на файле ошибка!»);
Выход;
КЕСЛИ
//перепись 2-го графа с частичным контролем из файла на экран;
Move_Gr_fileToEcran ( Potok, nUDn1, nUDm1, tBG, tBP, ref error);
ЕСЛИ (error) ТО
вывод («В данных на файле ошибка!»);
Выход;
КЕСЛИ
Potok.Close();
КЕСЛИ
//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности MS1 (1.3)
Input_GrInEkran ( nUDn1, nUDm1, tBG1, tBP1, ref n1, ref m1, ref MS1, ref error);
ЕСЛИ (error) ТО
вывод («В данных на форме ошибка»)
Выход;
КЕСЛИ
//Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности MS2
Input_GrInEkran ( nUDn2, nUDm2, tBG2, tBP2, ref n2, ref m2, ref MS2, ref error);
ЕСЛИ (error)) ТО
вывод («В данных на форме ошибка»)
Выход;
КЕСЛИ
//поиск и удаление висячих вершин 1-го графа(1.4)
Poisc_ver(ref MS1, ref n1);
//поиск и удаление висячих вершин 2-го графа
Poisc_ver(ref MS2, ref n2);
ЕСЛИ /* Расчет диаметра 1-го и 2-го графа r1 (1.5) */
(Diametr( MS1) == Diametr( MS2)) ТО
вывод («Графы эквивалентны»);
ИНАЧЕ
вывод («Графы не эквивалентны»);
КЕСЛИ
КОНЕЦ

Записываем основной алгоритм на С# и вместе с заглушками отлаживаем его.
public void Kyrs_proekt()
{
int [,] MS1;// инициализация матрицы смежности
int [,] MS2;// инициализация матрицы смежности
string filename;
bool error;
if (/*ввод с файла*/radioGroup1.Checked)
{
//Выбор файла и создание потока(1.1)
if (openFileDialog1.Show == DialogResult.OK)
{
filename = openFileDialog1.Filename;
//создание потока и подсоединение к файлу
StreamReader Potok = new StreamReader(filename);
}
else
{
MessageBox.Show( “Файл не выбран!”);
return ;
}
//перепись 1-го графа с частичным контролем из файла на экран; (1.2)
Move_Gr_fileToEcran ( Potok, nUDn1, nUDm1, tBG1, tBP1, ref error);
if (error)
{
MessageBox.Show (“В данных на файле ошибка!”);
return;
}
//перепись 2-го графа с частичным контролем из файла на экран;
Move_Gr_fileToEcran ( Potok, nUDn2, nUDm2, tBG2, tBP2, ref error);
if (error)
{
MessageBox.Show (“В данных на файле ошибка!”);
return;
}
Potok.Close();
}
//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)
Input_GrInEkran ( nUDn1, nUDm1, tBG1, tBP1, ref n1, ref m1, ref MS1, ref error);
if (error)
{
MessageBox.Show (“В данных на форме ошибка”);
return;
}
//Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности MS2
Input_GrInEkran ( nUDn2, nUDm2, tBG2, tBP2, ref n2, ref m2, ref MS2, ref error);
if (error)
{
MessageBox.Show (“В данных на форме ошибка”);
return;
}
//Поиск и удаление висячих вершин 1-го графа (1.4)
//Поиск и удаление висячих вершин 1-го графа
if (/*d1= d2(1.5)*/ Diametr( MS1)== Diametr ( MS2))
MessageBox.Show (“Графы эквивалентны”);
else
MessageBox.Show (“Графы не эквивалентны”);
}
Полученный основной алгоритм и подзадачи записанные на языке C# отлаживаем. Ошибок не было.

Приступаем к проектированию подзадачи 1.2. Перепись графа с файла на экран с частичным контролем.
Move_Gr_fileToEcran (StreamReader Potok. NumericUpDown nUDn, NumericUpDown nUDm, TextBox tbG, tbP, ref bool error)
НАЧАЛО
Перенос чисел n и m на форму в компоненты nUDn, nUDm.
Считываем строку с файла и преобразуем ее в вектор строк (vect)
В vect[0] будет n, а в vect[1] будет m
Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm
Перенос вектора G на форму в компоненту tbG ;
Перенос вектора P на форму в компоненту tbP ;
Считываем P(может занимать несколько строк) с файла в строку S и преобразуем ее в вектор строк (vect), который переписываем в tbP без контроля.
КОНЕЦ
В данной подзадаче есть подзадачи, но они реализуются простыми средствами языка C#, без оформления их отдельными методами.
Реализуем данную подзадачу на C#.

public void Move_Gr_fileToEcran (StreamReader Potok. NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP , ref bool error)
{
//Перенос чисел n и m на форму в компоненты numericUpDown
//Считываем строку с файла и преобразуем ее в вектор строк (vekt)
//В vect[0] будет n, а в vect[1] будет m (см.в спецификации размещение данных)
char ch= ‘ ‘;
string str =Potok.ReadLine();
string [] vect=str.split();
n = int.Parse(vect[0]);
m = int.Parse(vect[1]);
//Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm
if((n < 1) || (n > 20))
{
MessageBox.Show («Ошибка ввода кол-ва вершин графа»);
error = true;
return;
}
nUDn.Value = n;
if ((m < 1) || (m > 50))
{
MessageBox.Show («Ошибка ввода кол-ва дуг графа»);
error = true;
return;
}
nUDm.Value = m;
//Перенос вектора G на форму в компоненту tbG
//Считываем вектор G (может занимать несколько строк) с файла в строку S и преобразуем //ее в вектор строк (vect), который переписываем в tbG без контроля.
string strp = «»;
strp = Potok.ReadLine();
vect = strp.Split(ch);
int k = vect.Length;
tBG.Clear();
for(int i = 0; i < k; i++)
{
tBG.Text += vect[i].ToString()+» «;
//Перенос вектора P на форму в компоненту tbP
//Считываем вектор P(может занимать несколько строк) с файла в строку S и преобразуем //ее в вектор строк (vect), который переписываем в tbP без контроля.
while ((strp = Potok.ReadLine()) != «»)
strp += str;
vect = strp.Split(ch);
int k = vect.Length;
tBP.Clear();
for(int i = 0; i < k; i++)
tBP.Text += vect[t].ToString() + » «;
}
}
Полученный метод вставляем в проект вместо заглушки (1.2).

Приступаем к проектированию подзадачи 1.3. Ввод данных с экрана с контролем и построением матрицы смежности
Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref int n, ref int m, ref [,] MS, ref bool error)
НАЧАЛО
Считываем с экрана n, m;
n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal
m = (int)nUDm.Value ;
Проверка количества элементов вектора G
int k = tBG.Text.Length/2;
ЕСЛИ ( k < 1 || k > n ) ТО
Вывод (“Количество элементов G неверно”);
error=true;
Выход;
КЕСЛИ
Проверка количества элементов вектора P
int k=tBP.Text.Length/2;
ЕСЛИ ( k < 1 || k > m ) ТО
Вывод (“Количество элементов P неверно”);
error=true;
Выход;
КЕСЛИ
Считываем G и P и строим матрицу смежности
ЕСЛИ ( error ) ТО
Вывод (“Элемент P вне диапазона”);
Выход;
КЕСЛИ
КОНЕЦ

В данном алгоритме есть одна подзадача (1.3.1 ). Реализуем ее в виде метода с типом.
bool CreatMS(TextBox tBG, TextBox tBP,ref int [,] MS, int n,ref error)
НАЧАЛО
int g1=0, gk=0;
error=false;
ДЛЯ i = 1 ДО n ЦИКЛ //по вершинам графа
ЕСЛИ (vect[i] != “”) TO
gk = int.Parse(vect[i]);
ДЛЯ k = g1 ДО gk ЦИКЛ
j = int.Parse(tBP.Lines [k]);
//контроль j
ЕСЛИ (j<0) или (j>n) ТО
Вывод («Элемент P — неверный»);
error=true;
Выход;
КЕСЛИ
MS[i,j]:=1;
КЦИКЛ
g1=gk;
КЕСЛИ
КЦИКЛ
КОНЕЦ

В подзадаче 1.3.1 нет других подзадач. Запишем ее на C# и подставим в подзадачу 1.3.
public void CreatMS(TextBox tBG, TextBox tBP,ref int [,] MS,ref error)
{
int n =(int)Math.Sqrt(MS.Length);
int g1=0, gk=0;
error=false;
for(int i=1;i<n;i++)//по вершинам графа
{
if (vect[i] != «»)
{
gk = int.Parse(vect[i]);
for (int k = g1; k < gk; k++)
{
if (vectp[k] != «»)
{
j = int.Parse(vectp[k]);
//контроль j
if ((j < 0) || (j > n))
{
MessageBox.Show(«Элемент P — неверный»);
error = true;
return;
}
MS[i, k] = 1;
}
}
g1 = gk;
}
}
}
public void Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref int n, ref int m, ref [,] MS, ref bool error)
{
//Считываем с экрана n, m;
n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal
m = (int)nUDm.Value ;
//Проверка количества элементов вектора G
int k = tBG.Text.Length/2;
if ( k < 1 || k > n )
{
MessageBox.Show(“Количество элементов G неверно”);
error=true;
return;
}
//Проверка количества элементов вектора P
int r = tBP.Text.Length/2;
if ( k < 1 || k > m )
{
MessageBox.Show (“Количество элементов P неверно”);
error=true;
return;
}
//Считываем G и P и строим матрицу смежности
public void CreatMS( tBG, tBP,ref [,] MS,n,ref error)
if ( error )
{
MessageBox.Show (“Элемент P вне диапазона”);
return;
}
}
Функцию 1.3 вместе с подзадачей 1.3.1 записываем в проект вместо заглушки 1.3 и отлаживаем.

Переходим к проектированию подзадачи 1.4. Поиск и удаление висячих вершин.
void Poisc_ver(ref int [,]MS, ref int n)
НАЧАЛО
int s = 0;
n =(int)Math.Sqrt(MS.Length) ;
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
s+=MS[i,j];
s+=MS[j,i];
ЕСЛИ (s==1)
//удаление вершины(1.41)
n=n-1
ЕСЛИ ( n < 2 ) ТО
Вывод «Граф сжался до 2-х вершин»
Выход;
КЕСЛИ
КЕСЛИ
КЦИКЛ
КЦИКЛ
КОНЕЦ

В этой подзадаче есть ещё одна подзадача (1.4.1) удаление заданой строки и столбца. Реализуем ее на псевдокоде.
void Del_ ver(ref int [,]MS, int c )
НАЧАЛО
ДЛЯ I = c ДО n — 1 ЦИКЛ
MS[i, c] = MS[i, c + 1];
MS[c, i] = MS[c + 1, i];
n — 1;
КЦИКЛ
КОНЕЦ

Реализуем подзадачу 1.4.1 на C#
public void Del_ver(ref int[,] MS, int c, ref int n)
{
for (int i = c; i < n; i++)
{
MS[i, c] = MS[i, c + 1];
MS[c, i] = MS[c + 1, i];
n—;
}
}

Подставляем подзадачу 1.4.1 в подзадачу 1.4

void Poisc_ver(ref int [,]MS, ref int n)
НАЧАЛО
int s = 0;
int n =(int)Math.Sqrt(MS.Length) ;
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
s+=MS[i,j];
s+=MS[j,i];
ЕСЛИ (s1==1)
//удаление вершины
Del_ ver(ref MS, i, ref n)
КЕСЛИ
КЦИКЛ
КЦИКЛ
КОНЕЦ

Реализуем подзадачу 1.4 на C#
public void Poisc_ver(ref int[,] MS, ref int n)
{
int s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
s += MS[i, j];
s += MS[j, i];
if (s == 1)
//удаление вершины
Del_ver(ref MS, i, ref n);
}
}
Полученую подзадачу подставляем в место подзадачи 1.4.

Переходим к проектированию подзадачи 1.5. Расчёт диаметра графа.
int Diametr( int[,]MS)
НАЧАЛО
int n =(int)Math.Sqrt(MS.Length) ;
int r=1 ;
int[,] MR=new int[n,n] ;
int[,] B1=new int[n,n];
int[,] B2=new int[n,n] ;
bool pr =true;
//копировать матрицу MS в MR=MS(1.4.1)
CopyMatr(MS ,ref MR)
// копировать матрицу MS в В1=MS
CopyMatr(MS ,ref B1 )
ПОКА pr ЦИКЛ
pr=false;
r=r+1 ;
// Умножение матриц В2=В1*MS(1.4.2)
MulMatr(B1 , MS, ref B2)
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
ЕСЛИ (MR[I,j]=0) и (B2[I,j]<>0 ) ТО
MR[I,j]=r;
Pr=true;
КЕСЛИ
КЦИКЛ
КЦИКЛ
//копировать матрицу B2 в В1=B2
CopyMatr(B2 ,ref B1)
КЦИКЛ
Возврат r-1 ;
КОНЕЦ

В данном алгоритме есть две подзадачи (1.5.1 и1.5.2). Реализуем их.
Подзадача 1.5.1 — копирование матрицы.
CopyMatr(int [,] A ,ref int [,] B)
НАЧАЛО
Int n =(int)Math.Sqrt(A.Length);
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
B[I,j]=A[I,j];
КЦИКЛ
КЦИКЛ
КОНЕЦ
Подзадача 1.4.2 — умножение матриц С=А*В
MulMatr(int [,] A , int [,] B,ref int[,]C)
НАЧАЛО
int n =(int)Math.Sqrt(A.Length);
int S;
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
S=0;
ДЛЯkj=1 ДО n ЦИКЛ
S=S+A[I,k]*B[k,j]
КЦИКЛ
C[I,j]=S;
КЦИКЛ
КЦИКЛ
КОНЕЦ
Обе подзадачи запишем на языке C# и подставим в алгоритм 1.5.
public void CopyMatr(int [,] A ,ref int [,] B)
{
iInt n =(int)Math.Sqrt(A.Length);
for(int i=0;i< n; i++)
for(intji=0;j< n; j++)
B[i,j]=A[i,j];
}

public void MulMatr(int [,] A , int [,] B,ref int[,]C)
{
int n =(int)Math.Sqrt(A.Length);
int S;
for(int i=0;i< n; i++)
for(int j=0;j< n; j++)
{
S=0;
for(int k=0;k< n; k++)
S=S+A[i,k]*B[k,j]
C[i,j]=S;
}
}
Запишем алгоритм на C# и подставим его вместо заглушки 1.5.
public int Diametr( int[,]MS)
{
int n =(int)Math.Sqrt(MS.Length) ;
int r=1 ;
int[,] MR=new int[n,n] ;
int[,] B1=new int[n,n];
int[,] B2=new int[n,n] ;
bool pr =true;
//копировать матрицу MS в MR=MS(1.5.1)
CopyMatr(MS ,ref MR)
// копировать матрицу MS в В1=MS
CopyMatr(MS ,ref B1 )
while ( pr)
{
pr=false;
r=r+1 ;
// Умножение матриц В2=В1*MS(1.5.2)
MulMatr(B1 , MS, ref B2)
For(int i=0; i< n; i++)
For(int j=0; j< n; j++)
if( (MR[i,j]=0) && (B2[i,j]<>0 ))
{
MR[i,j]=r;
pr=true;
}
//копировать матрицу B2 в В1=B2
CopyMatr(B2 ,ref B1)
}
return r-1
}
Окончательный проект:

Листинг программы:

Весь основной код находится в файле Form1.cs

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;

namespace WindowsFormsApplication2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
public void Kyrs_proekt()
{
int[,] MS1 = new int[10, 10];//матрица смежности с параметрами по умолчанию
int[,] MS2 = new int[10, 10];
int n1 = 0, n2 = 0, m1 = 0, m2 = 0;
bool error = false;
string filename;
if (rB1.Checked)
{
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
filename = openFileDialog1.FileName;
//создание потока и присоединение к фалу
StreamReader Potok = new StreamReader(filename);
//перепись 1-го графа с частичным контролем из файла на экран; (1.2)
Move_Gr_fileToEcran(Potok, nUDn1, nUDm1, tBG1, tBP1,ref error);
if (error)
{
MessageBox.Show(«В данных графа 1 на файле ошибка!»);
return;
}
//перепись 2-го графа с частичным контролем из файла на экран;
Move_Gr_fileToEcran(Potok, nUDn2, nUDm2, tBG2, tBP2, ref error);
if (error)
{
MessageBox.Show(«В данных графа 2 на файле ошибка!»);
return;
}
Potok.Close();
}
else
{
MessageBox.Show(«Файл не выбран!»);
return;
}
//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)
Input_GrInEkran(nUDn1, nUDm1, tBG1, tBP1, ref n1, ref m1, ref MS1, ref error);
if (error)
{
MessageBox.Show(«В данных 1-го на форме ошибка»);
return;
}
////Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)
Input_GrInEkran(nUDn2, nUDm2, tBG2, tBP2, ref n2, ref m2, ref MS2, ref error);
if (error)
{
MessageBox.Show(«В данных 2-го графа на форме ошибка»);
return;
}
////Поиск и удаление висячих вершин 1-го графа (1.4)
Poisc_ver(ref MS1, ref n1);
if (n1 < 2)
{
MessageBox.Show(«Первый граф выродился»);
return;
}
////Поиск и удаление висячих вершин 1-го графа
Poisc_ver(ref MS2, ref n2);
if (n2 < 2)
{
MessageBox.Show(«Второй граф выродился»);
return;
}
////Расчет диаметра 1-го графа r1 (1.5)
Diametr(MS1);
////Расчет диаметра 2-го графа r2;
Diametr(MS2);
if (Diametr(MS1) == Diametr(MS2))
{
MessageBox.Show(«Графы эквивалентны!»);
}
else MessageBox.Show(«Графы не эквивалентны»);
}
if (rB2.Checked)
{
//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)
Input_GrInEkran(nUDn1, nUDm1, tBG1, tBP1, ref n1, ref m1, ref MS1, ref error);
if (error)
{
MessageBox.Show(«В данных 1-го графа на форме ошибка»);
return;
}
////Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)
Input_GrInEkran(nUDn2, nUDm2, tBG2, tBP2, ref n2, ref m2, ref MS2, ref error);
if (error)
{
MessageBox.Show(«В данных 2-го графа на форме ошибка»);
return;
}
////Поиск и удаление висячих вершин 1-го графа (1.4)
Poisc_ver(ref MS1, ref n1);
////Поиск и удаление висячих вершин 1-го графа
Poisc_ver(ref MS2, ref n2);

if (Diametr(MS1) == Diametr(MS2))//сравнение диаметров первого и второго графов
{
MessageBox.Show(«Графы эквивалентны!»);
}
else MessageBox.Show(«Графы не эквивалентны»);
}
}

public void Move_Gr_fileToEcran(StreamReader Potok, NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref bool error)
{
//Перенос чисел n и m на форму в компоненты numericUpDown
//Считываем строку с файла и преобразуем ее в вектор строк (vekt)
//В vect[0] будет n, а в vect[1] будет m (см.в спецификации размещение данных)
char ch = ‘ ‘;
string str = Potok.ReadLine();
string[] vect = str.Split(ch);
int n = int.Parse(vect[0]);
int m = int.Parse(vect[1]);
//Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm
if ((n < 1) || (n > 20))
{
MessageBox.Show(«Ошибка ввода количества вершин!»);
error = true;
return;
}
nUDn.Value = n;
if ((m < 1) || (m > 50))
{
MessageBox.Show(«Ошибка ввода количества дуг графа»);
error = true;
return;
}
nUDm.Value = m;
//Перенос вектора G на форму в компоненту tbG
//Считываем вектор G (может занимать несколько строк) с файла в строку S и преобразуем
//ее в вектор строк (vect), который переписываем в tbG без контроля.
string strp = «»;
strp = Potok.ReadLine();
vect = strp.Split(ch);
int k = vect.Length;
tBG.Clear();
for (int i = 0; i < k; i++)
tBG.Text += vect[i].ToString()+» «;
while ((strp = Potok.ReadLine()) != «»)
{
vect = strp.Split(ch);
k = vect.Length;
tBP.Clear();
for (int t = 0; t < k; t++)
tBP.Text += vect[t].ToString() + » «;
}
}

public void Input_GrInEkran(NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBG, TextBox tBP, ref int n, ref int m, ref int[,] MS, ref bool error)
{
//Считываем с экрана n, m;
n = (int)nUDn.Value;//преобразуем в целое, так как Value типа decimal
m = (int)nUDm.Value;
//Проверка количества элементов вектора G
int k = tBG.Text.Length/2;
if (k < 1 || k > n)
{
MessageBox.Show(«Количество элементов G неверно»);
error = true;
return;
}
//Проверка количества элементов вектора P
int r = tBP.Text.Length/2;
if (r < 1 || r > m)
{
MessageBox.Show(«Количество элементов P неверно»);
error = true;
return;
}
MS = new int[n, n];
//Считываем G и P и строим матрицу смежности
CreatMS(tBG, tBP, ref MS, n, ref error);
if (error)
{
MessageBox.Show(«Элемент P вне диапазона»);
return;
}

}

// подзадача (1.3.1 )
public void CreatMS(TextBox tBG, TextBox tBP, ref int[,] MS, int n, ref bool error)
{
//int n = (int)Math.Sqrt(MS.Length);
int g1 = 0, gk = 0, j;
error = false;
string str = tBG.Text;
string strp = tBP.Text;
char ch = ‘ ‘;
string[] vect = str.Split(ch);
string[] vectp = strp.Split(ch);
for (int i = 0; i < vect.Length; i++)//по вершинам графа
{
if (vect[i] != «»)
{
try
{
gk = int.Parse(vect[i]);
}
catch (Exception) { error = true; return; }
for (int k = g1; k < gk; k++)
{
if (vectp[k] != «»)
{
j = int.Parse(vectp[k]);
//контроль j
if ((j < 0) || (j > n))
{
MessageBox.Show(«Элемент P — неверный»);
error = true;
return;
}
MS[i, k] = 1;
}
}
g1 = gk;
}
}
}

public void Poisc_ver(ref int[,] MS, ref int n)
{
int s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
s += MS[i, j];
s += MS[j, i];
if (s == 1)
//удаление вершины
Del_ver(ref MS, i, ref n);
}
}
public void Del_ver(ref int[,] MS, int c, ref int n)
{
for (int i = c; i < n; i++)
{
MS[i, c] = MS[i, c + 1];
MS[c, i] = MS[c + 1, i];
n—;
}
}

public int Diametr(int[,] MS)
{
int n = (int)Math.Sqrt(MS.Length);
int r = 1;
int[,] MR = new int[n, n];
int[,] B1 = new int[n, n];
int[,] B2 = new int[n, n];
bool pr = true;
//копировать матрицу MS в MR=MS(1.5.1)
CopyMatr(MS, ref MR);
// копировать матрицу MS в В1=MS
CopyMatr(MS, ref B1);
while (pr)
{
pr = false;
r = r + 1;
// Умножение матриц В2=В1*MS(1.5.2)
MulMatr(B1, MS, ref B2);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((MR[i, j] == 0) && (B2[i, j] != 0))
{
MR[i, j] = r;
pr = true;
}
//копировать матрицу B2 в В1=B2
CopyMatr(B2, ref B1);
}
return r — 1;
}

public void CopyMatr(int[,] A, ref int[,] B)
{
int n = (int)Math.Sqrt(A.Length);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
B[i, j] = A[i, j];
}

public void MulMatr(int[,] A, int[,] B, ref int[,] C)
{
int n = (int)Math.Sqrt(A.Length);
int S;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
S = 0;
for (int k = 0; k < n; k++)
S = S + A[i, k] * B[k, j];
C[i, j] = S;
}
}

private void button1_Click(object sender, EventArgs e)
{
Kyrs_proekt();
}

private void button2_Click(object sender, EventArgs e)
{
Application.Exit();
}

private void rB2_CheckedChanged(object sender, EventArgs e)
{
tBG1.ReadOnly = false;
tBG2.ReadOnly = false;
tBP1.ReadOnly = false;
tBP2.ReadOnly = false;
tBG1.Text = «»;
tBG2.Text = «»;
tBP1.Text = «»;
tBP2.Text = «»;
nUDm1.Value = 1;
nUDm2.Value = 1;
nUDn1.Value = 1;
nUDn2.Value = 1;
}

private void rB1_CheckedChanged(object sender, EventArgs e)
{
tBG1.ReadOnly = true;
tBG2.ReadOnly = true;
tBP1.ReadOnly = true;
tBP2.ReadOnly = true;
}

private void tBG1_KeyPress(object sender, KeyPressEventArgs e)
{
//проверяем символ нажатой клавиши
if (!(char.IsDigit(e.KeyChar)))
if(e.KeyChar != 8)
{
MessageBox.Show(«Для избежания ошибок при вычислении вводите только цифры!!!», «Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
e.KeyChar = ‘\0’;
}
}

private void tBP1_KeyPress(object sender, KeyPressEventArgs e)
{
//проверяем символ нажатой клавиши
if (!(char.IsDigit(e.KeyChar)))
if (e.KeyChar != 8)
{
MessageBox.Show(«Для избежания ошибок при вычислении вводите только цифры!!!», «Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
e.KeyChar = ‘\0’;
}
}

private void tBG2_KeyPress(object sender, KeyPressEventArgs e)
{
//проверяем символ нажатой клавиши
if (!(char.IsDigit(e.KeyChar)))
if (e.KeyChar != 8)
{
MessageBox.Show(«Для избежания ошибок при вычислении вводите только цифры!!!», «Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
e.KeyChar = ‘\0’;
}
}

private void tBP2_KeyPress(object sender, KeyPressEventArgs e)
{
//проверяем символ нажатой клавиши
if (!(char.IsDigit(e.KeyChar)))
if (e.KeyChar != 8)
{
MessageBox.Show(«Для избежания ошибок при вычислении вводите только цифры!!!», «Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
e.KeyChar = ‘\0’;
}
}
}
}

Проверим работу всего проекта на тестах, приведенных в спецификации в пункте 6. После тестирования выявлено, что программа работает нормально.
Ниже привожу пример теста (нормальная работа программы):
2

1

4

3

5

2011