МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИСТЕТ
кафедра прикладной математики и информатики
Расчетно-графическая работа
по дисциплине «Объектно-ориентированное программирование»
Факультет: ПМИ
Группа: ПМ-92
Студент: Мульцын К.А.
Преподаватель: Лисицин
г. Новосибирск, 2000
1. Условие задачи
Определить, является ли данный граф автоморфным.
2. Анализ задачи
Дано: граф
Результат: логическое значение
Связь: ИСТИНА, если граф автоморфный, ЛОЖНО в обратном случае.
Граф называется автоморфным, если существует такая перестановка вершин,
которая сохранила бы отношения смежности. Другими словами, если граф
автоморфный, то мы можем найти такую перестановку вершин, что при
наложении на исходный граф все ребра совпадут.
Такая постановка задачи уже дает вариант ее решения. Граф мы будем
представлять матрицей смежности и вот по каким соображениям.
Перестановку i-ой и j-ой вершин и «наложение» можно осуществить путем
перестановки i-ых и j-ый строк и столбцов матрицы смежности и сравнением
ее с исходной. Если матрицы совпадут, то мы получили автоморфизм.
К сожалению, никакой другой идеи, кроме полного перебора, предложить
нельзя. Проанализируем затраты времени. Т.к. нам нужно получить все
перестановки из n вершин, то время мы на это потратим пропорциональное
n! Таким образом, для больших n задача будет решаться очень долго. Но
при n10 время решения удовлетворительно.
Теперь обсудим представление данных. Во-первых, пользователь должен
ввести исходный граф, и делает он это следующим образом: он вводит (с
клавиатуры, или из файла) пары натуральных чисел, a и b, которые
означают, что между вершинами a и b есть ребро. Далее граф для
наглядности рисуется на экране, а затем производится процесс вычислений.
Если граф получился автоморфным, то выводится автоморфизм, как
соответствие вершин.
В памяти граф представлен матрицей смежности. Матрица статическая, т.к.
мы не будем работать с большими значениями N. Реализованы классы графов
и матриц, между которыми установлено отношение использования. Причем
классы закрыты по отношению друг к другу.
3. Алгоритм решения задачи
НАЧАЛО
загружаем граф
выводим его на экран
создаем копию исходного графа
ПОКА
не перебрали все перестановки
ИЛИ не нашли автоморфизм
ДЕЛАЕМ
следующую перестановку
сравниваем перестановку с исходным графом
ЕСЛИ они равны ТО мы нашли автоморфизм
выводим сообщение о результате работы
КОНЕЦ
4. Текст программы
#include
#include
#include #include #include #define PI 3.1415926 class matrix // Используется для представления private: // графа. int p[30][30]; // Матрица представлена статическим int n,m; // массивом. N,M – размерность. public: matrix(int a=10, int b=10) // Конструктор // Обнуляет все эл-ты int i,j; n=a; m=b; for (i=1;i>a>>b; if (a>n) r.set_n(a); r.set_m(a); if (b>n) r.set_n(b); r.set_m(b); r.assign(a,b,1); r.assign(b,a,1); while (a!=0 && b!=0); int load(char * filename) // Загружает граф из файла. // Примечание: по возможности надо int i,j,n; // указывать вершины без пропусков. ifstream f; // Т.к. время вычислений в худшем f.open(filename); // случае будет n!, n – кол-во вершин. if (!f) return 1; // Ошибка открытия файла f>>i; do n=r.get_n(); f>>j; if (f.eof()) return 2; // Ошибка в данных if (i>n) r.set_n(i); r.set_m(i); if (j>n) r.set_n(j); r.set_m(j); r.assign(i,j,1); r.assign(j,i,1); f>>i; while (!f.eof()); return 0; // Все нормально int get_vert_number() // Возвращает количество вершин, // ВКЛЮЧАЯ пропущенные. return r.get_n(); void viewmatrix() r.print(); // Выводит матрицу смежности. void swap_matrix(int i, int j) // Меняет местами i-ые и j-ые // строки и столбцы. Иными словами, matrix c; // строится новый граф из int n,k,l; // имеющегося перенумерацией вершин n=get_vert_number(); // Если матрицы совпадут, то c.set_n(n); // имеющийся граф автоморфный. c.set_m(n); for (k=1;k0 && X[i]>X[i+1]) i–; if (i>0) j=i+1; while (j swap(X[i],X[j]); h.swap_matrix(i,j); for (j=i+1; j
Нашли опечатку? Выделите и нажмите CTRL+Enter
