Расчетно-графическая работа



Скачать 107.4 Kb.
Дата31.12.2012
Размер107.4 Kb.
ТипДокументы
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИСТЕТ

кафедра прикладной математики и информатики

Расчетно-графическая работа


по дисциплине «Объектно-ориентированное программирование»

Факультет: ПМИ

Группа: ПМ-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<=n;i++)

for (j=1;j<=m;j++) p[i][j]=0;

}
void assign(int a, int b, int el) // Метод записывает

{ // элемент в позицию [a,b]

if (a<=n && b<=m) p[a][b]=el;

}
int get(int a, int b) // Возвращает элемент

{ // из позиции [a,b]

if (a<=n && b<=m) return p[a][b];

}
int get_m() {return m;} // Получить размерность

int get_n() {return n;}

void set_n(int a) {n=a;} // Изменить размерность

void set_m(int b) {m=b;}
void print() // Выводит матрицу на экран

{

int i,j;

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

{

for (j=1;j<=m;j++)

cout<


cout<<"\n";

}

}
friend matrix operator*(matrix a, matrix b); // Оператор умножения

// матрицы на матрицу

friend int operator==(matrix a, matrix b); // Сравнение матриц
}; //end of matrix class
matrix operator*(matrix a, matrix b) // Реализация оператор умножения

{

int n1,n2,m1,m2;

int i,j,k,s;

n1 = a.get_n();

n2 = b.get_n();

m1 = a.get_m();

m2 = b.get_m();

matrix c;

if (m1 != n2) {c.n=n1; c.m=m1;}

else {

c.set_n(n1);

c.set_m(m2);

for (i=1;i<=n1;i++)

for (j=1;j<=m2;j++)

{

s=0;

for (k=1;k<=m1;k++) s=s+a.p[i][k]*b.p[k][j];

c.p[i][j]=s;

}

}

return c;

}
int operator==(matrix a, matrix b) // Реализация оператора сравнения

{

int n,m,i,j;

n=a.get_n();

m=a.get_m();

if (n!=b.get_n() || m!=b.get_m() ) return 0; //не совпадают размерности

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

for (j=1;j<=m;j++)

if (a.p[i][j]!=b.p[i][j]) return 0; //не совпадают элементы

return 1;

}
//-------------------------------------------------------------------------
class graph // класс описывает графы

{

private:

matrix r; // граф представлен матрицей смежности

public:

graph() // Конструктор

{ // изначально граф пуст

r.set_n(0);

r.set_m(0);

}
void load() // Загружается граф с клавиатуры

{ // Требуется ввести пару чисел,

int a,b,n; // которая описывает одно ребро и

// две вершины. Конец ввода: 0 0.

do

{

n=r.get_n();

cout<<"pair: ";

cin>>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;k<=n;k++)

for (l=1;l<=n;l++)

{

c.assign(k,l,0);

if (k==l && k!=i && k!=j) c.assign(k,l,1);

if (k==i && l==j || k==j && l==i) c.assign(k,l,1);

}

r=c*r*c;

}
void draw(int x=320, int y=240, int R=230)

{ // Выводит граф на экран.

double angle; // По умолчанию вершины графа

int vn,i,k,l,n; // расположены на окружности

char* s; // с центром в центре экрана

// и занимающей весь экран.

vn=get_vert_number();

n=r.get_n();
angle = 2*PI/vn;

i=0;

setcolor(11);
for (k=1; k<=n; k++)

{

for (l=1; l<=k; l++)

if (r.get(k,l)==1)

line(x+R*cos(angle*k),y-R*sin(angle*k),x+R*cos(angle*l),y-R*sin(angle*l));

}

setcolor(14);

s="0";

for (i=0; i
{

circle(x+R*cos(angle*i),y-R*sin(angle*i),1);

moveto(x+(R+15)*cos(angle*i),y-(R+15)*sin(angle*i));

s[0]++;

outtext(s);

}

}
friend operator==(graph a, graph b); // проверка графов на равенство

}; // end of graph class
operator==(graph a, graph b)

{

if (a.r==b.r) return 1;

else return 0;

}

// ----------------------------------------------------------------
int N,X[30];

graph g,h;

int Found=0;
void swap(int &a, int &b)

{

int c;

c=a;

a=b;

b=c;

}
int next() // Получение следующей перестановки в лексикограф. пор-ке

{

int i,j;

i=N-1;

while (i>0 && X[i]>X[i+1]) i--;

if (i>0)

{

j=i+1;

while (jX[i]) j++;

swap(X[i],X[j]);

h.swap_matrix(i,j);

for (j=i+1; j<=(N+i)/2; j++)

{

swap(X[j],X[N-j+i+1]);

h.swap_matrix(j,N-j+i+1);

}

if (h==g) Found=1;

return 1;

}

else return 0;

}

void main()

{

int driver=DETECT,mode=VGAHI;

int i,j;
if (!g.load("graph.txt"))

{

initgraph(&driver,&mode,""); // Покажем граф пользователю, чтобы он смог

g.draw(320,240,210); // оценить его автоморфность

getch(); // подождем его реакции.

closegraph();
N=g.get_vert_number();

h=g; // оформим новый граф, который будем примерять

// к старому.

for (i=1; i<=N; i++) X[i]=i; // Выполним все перестановки строк и столбцов

do {} while (next() && !Found); // пока не дойдем до конца, либо найдем

// автоморфность.
if (Found) // Если нашли автоморфность, то укажем ее

{

cout<<"Граф автоморфен. Если поставить исходному набору вершин\n";

for (i=1;i<=N;i++) cout<
for (i=1;i<=N;i++) cout<
}

else // если нет, то так и скажем

cout<<"Граф не автоморфен.";

}

}
5. Набор контрольных тестов

неавтоморфный

автоморфный

6

5

3

2

1

6

5

4

3

2

1

4

Для этой программы достаточно двух тестов. Первый граф зададим автоморфным, например с ребрами 1-2, 2-3, 3-4, 3-6, 4-5. Легко заметить, что этот граф автоморфный, причем набору вершин 123456 соответствует набор 543216. Если же мы добавим к этому графу ребро 4-6, то он перестанет быть автоморфным.
6. Результаты работы программы.

Результаты работы программы совпали с ожидаемыми. На наборе контрольных тестов программа работала правильно и без ошибок.

Похожие:

Расчетно-графическая работа iconРасчетно-графическая работа
Смоделировать выборку из равномерного закона распределения с параметрами a=-2,52 и b =0,51
Расчетно-графическая работа iconРасчётно-графическая работа №1 по дисциплине
Построить схемы расположения полей допусков для выбранных посадок по d, D, d1, d3
Расчетно-графическая работа iconРгр 2, часть 3 Расчетно-графическая работа
Самостоятельно написать в Web–редакторе html–коды согласно варианту задания (1). Номер варианта указывает
Расчетно-графическая работа iconРасчётно-графическая работа по курсу «Теория вероятностей»
В магазин поступило 30 новых телевизоров, среди которых 5 имеют скрытые дефекты. Наудачу отбирается один телевизор. Какова вероятность...
Расчетно-графическая работа iconРасчетно-графическая работа №1
Скорость и ускорение точки в проекциях на декартовы и естественные оси координат. Построение траектории точки, графиков скорости...
Расчетно-графическая работа iconРасчетно-графическая работа №2 Расчет линейной цепи синусоидального тока
Эдс рассчитать токи ветвей и составить баланс мощностей (активных и реактивных). Коэффициент связи k = 0 Взаимная индуктивность....
Расчетно-графическая работа iconРасчетно-графическая работа. Семестр 2
При освобождении памяти производится объединение соседних свободных областей. Структура данных, используемая в дрп. Необходимы также...
Расчетно-графическая работа iconПояснительная записка расчетно-графическая работе по дисциплине "Информатика" " Шейкер-cортировка" Группа: ам-216
...
Расчетно-графическая работа iconПояснительная записка расчетно-графическая работе по дисциплине "Информатика" Шейкер-сортировка двусвязного циклического списка
Шейкер сортировка двусвязного циклического списка. Используются указатели на границы отсортированных частей списка
Расчетно-графическая работа iconТаблично-графическая схема рабочей программы по химии (10 класс) часа Трудоемкость
Трудоемкость (количество часов): общее 3,аудиторных 2, внеаудиторных 1, самостоятельная работа 1
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org