2. Постановка задачі

Використовуючи технологію спадного проектування, порівняти два неорієнтованих графа, представлених масивом послідовників (FI - подання), дізнатися діаметр графа після видалення в ньому висячих вершин. Вершин графа не більше 20, число ребер не більше 50. Передбачити введення даних з клавіатури і з текстового файлу.

3. Вхідні данні

Вхідні дані наведені в табл. 3.1, вхідні форми зображені на рис. 4.1, вхідний формат текстового файлу показаний на малюнку 5.1:

Таблица 3.1

Номер п/п	Наименование	Тип	Диапазон	Назначение
1	n1	Целый	1<=n1<=20	Количество вершин 1-го графа
2	m1	Целый	0<=m1<=50	Количество ребер 1-го графа
3	Fi1={ fi1[i]}	Массив целых чисел	0<=fi1[i]<=n1 1<=i<=2m1+n1	Fi-представление 1-го графа
4	n2	Целый	1<=n2<=20	Количество вершин 2-го графа
5	m2	Целый	0<=m2<=50	Количество ребер 2-го графа
6	Fi2={ fi2[i]}	Массив целых чисел	0<=fi2[i]<=n2 1<=i<=2m2+n2	Fi-представление 2-го графа

4. Вхідні форми

Вхідні форми представлення на мал. 2.

Малюнок 2 – Вхідна форма

5. Вхідний формат текстового файла

В текстовому файлі з росширенням *.txt буде зберігатися інформація про один граф в наступному виді:

Малюнок 3 – Складова текстового файла

6. Вихідні данні

Залежно від отриманого результату порівняння графів користувачеві буде видане текстове повідомлення. Якщо графи еквівалентні, то результатом буде повідомлення (малюнку 4): «Графи еквівалентні!».

В іншому випадку результатом роботи програми буде повідомлення: «Графи НЕ еквівалентні!».

7. Вихідні форми

Малюнок 4 – Вхідні форми

8. Метод вирішення

Алгоритм метода вирішення:

1. Задаем граф в FI представлении;

2. Преобразуем графа в матрицу инцидентности;

3. Формируем множество вершин;

4. Удаляем висящие вершины;

5. Определяем расстояние между вершинами (определяется как наименьшее число рёбер которые необходимо пройти, чтобы добраться из одной вершины в другую);

6. Получаем диаметр грфа;

7. Выполняем операцию для второго графа;

8. Проверяем на эквивалентность оба графы;