Решение оптимизационных задач на графах и сетях

                       ВЯТСКИЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

Факультет Информационных технологий

Кафедра Информатики и вычислительной техники

 

 

Курсовая работа по теме

“Решение оптимизационных задач

на графах и сетях”

 

 

 

 

 

 

 

                       Дисциплина: Теория графов и сетей

           Группа: ИВТ- 31

           Разработал студент:

           Работа принята c оценкой________

           Руководитель проекта:

 

 

  Киров 2010

Объектом  исследования в данной курсовой работе являются графы и сети.

Цель работы состоит в решении оптимизационных  задач на графах и сетях.

В курсовой работе определяется, является ли граф антисимметрическим. Особенность этой задачи состоит в том, что граф задан матрицей инциденций. Для этого задания написана программа на языке С++.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание:

Определить является ли граф антисимметрическим или полным антисимметрическим.

Общие сведения:

Антисимметрическим  называется  такой  граф,  для  которого  справедливо

следующее условие:

 если дуга (xi, xj) ∈A, то во множестве A нет противоположно ориентированной дуги,  т.е.(xj, xi)  ∉A  (рис.1)

 

рис.1

 

 

•  Граф G =(X, A), имеющий для  каждой пары вершин (xi, xj)  только  одну дугу,  называется   полным  антисимметрическим. (Рис.2)

рис.2

 

 

 

Матрица инциденций для графа на (рис.2):

1	0	0	0	0	0	-1	0	0	0	0	1	0	0	-1	-1	0	0	0	1	0
-1	1	0	0	0	0	0	-1	-1	-1	-1	0	0	0	0	0	0	0	0	0	0
0	-1	1	0	0	0	0	0	0	0	0	-1	-1	-1	0	0	1	0	0	0	0
0	0	-1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	-1	-1	-1
0	0	0	-1	1	0	0	0	0	1	0	0	0	1	1	0	0	-1	0	0	0
0	0	0	0	-1	1	0	0	1	0	0	0	0	0	0	1	-1	0	0	0	1
0	0	0	0	0	-1	1	1	0	0	0	0	1	0	0	0	0	1	1	0	0

 

Очевидно, что в каждом столбце присутствует только одна 1 и одна -1.

Очевидно, что кол-во 1 и -1 в каждой строке =(кол-во строк – 1)

Алгоритм:

Нужно задать матрицу  N x M , состоящую из элементов [0,1,-1].

Т.к элементы вводятся вручную  нужно поставить проверку:

 - на корректность ввода

После заполнения матрицы  делаем проверку условий:

1)Если в каждом столбце есть одна 1 и одна -1,

2)Если нет одинаковых столбцов (расположение 1и -1 в каждом новом столбце должно быть отлично от предыдущих).Примечание: Столбцы различные только по знаку “-“ перед еденицей также считаются недопустимыми.

Если эти 2 условия выполняются:

 выводим сообщение  “Граф является антисимметрическим”, в противном случае выводим:  “Граф не является антисимметрическим”.

Далее если условие выполняется(граф антисимметрический), делаем проверку в каждой строке на суммарное количество  1 и -1 ,оно должно быть N-1 .

Если суммарное кол-во 1 и -1 равно N-1, выводим готовую матрицу и сообщение: “Граф является полным антисимметрическим”.Если суммарное кол-во 1и -1 не равно N-1, добавляем новый столбец по следующему алгоритму:

Проверяем первую строку. Если в ней кол-во 1 и -1 не равно N-1 ,добавляем 1.Идем во вторую строку, если в ней кол-во 1 и -1 равно N-1 то добавляем ноль и переходим к след. строке. Если в ней кол-во 1 и -1 не равно N-1 , добавляем -1 ,в остальных строках ставим нули. Полученный столбец сравниваем с предыдущими по условию 2).Если условие выполняется, сохраняем столбец. Если не выполняется, то перезаписываем последнюю еденицу в столбце т.е. вместо -1 ставим 0 и проверяем след. строку итд пока не получим столбец удовлетворяющий условию 2) … И.т.д. пока в каждой строке суммарное кол-во 1 и -1 не будет равно N-1.

 

 

Литература

 

 

Основная

1. Волченская Т.В.,  Князьков В.С. Компьютерная математика: ч.2. Теория графов: Учебн. пособие. - Пенза 2004. – 124 с.
2. Новиков Ф.А. Дискретная математика для программистов. – СПБ.: Питер, 2005.

 

 

Приложение:

#include<alloc.h>

#include<conio.h>

#include<stdio.h>

int main ()

{int i,j,q,w,n,m,cnt,mt[10][100];

printf("Input N: ");

scanf ("%i", &n);

printf("Input M: ");

scanf ("%i", &m);

for (i=0;i<n;i++)// vvod mt

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

{

printf("Input matrix: ");

scanf ("%i", mt[i][j]);

if (mt[i][j]!=1 && mt[i][j]!=-1 && mt[i][j]!=0)

i--;

}

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

{ q=0;w=0;

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

{if (mt[j][i]==-1)

q++;

if (mt[j][i]==1)

w++;

}

if (q!=1 && w!=1)

{ puts ("Graf ne antysimmetricheskiu");

getchar();

break;}}

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

{for (j=0;j<m;j++)

if (mt[j][i]==mt[j][i-1]&&(mt[j][i]==1||mt[j][i-1]==-1))

{puts ("Graf ne antysimmetricheskiu'");

getchar();

break;}

if (j!=m)

getchar();

break;

else puts ("Graf antysimmetricheskiu"); }

 

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

{

    if(cnt!=n-1)

puts ("Graf ne polnyi antysimmetricheskiu");

getchar();

 

       break;

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

    {

if(cnt!=n-1)

puts ("Graf ne polnyi antysimmetricheskiu");

           getchar();

           break;

           if(mt[i][j]!=0)

           cnt++;

    }

    cnt=0;

}

puts ("Graf polnyi antysimmetricheskiu");

 

getchar();

}