Курсовая работа - Выделение компонент сильной связности
.docУфимский государственный авиационный технический университет
Кафедра АПРиС
Курсовая работа
по дискретной математике
Выделение компонент сильной связности.
Выполнили:
САПР-130
Проверила:
Шерыхалина Н.М.
доц. каф. КМ
Уфа – 2007
Оглавление:
Введение 3
Алгоритм 4
Блок-схема. 7
Листинг программы 13
Заключение 19
Список использованной литературы: 20
Цель работы
Целью данной работы является создание алгоритма выделения компонент сильной связности и проектирование программы, применяющей этот алгоритм.
Введение
Теория графов это один из разделов дискретной математики, изучающий свойства графов. Теория графов имеет огромное практическое значение, к примеру, маршрутизация данных в Интернете была бы невозможна без ее применения.
В данной работе рассмотрена одна из классических задач теории графов – выделение компонент сильной связности.
Для выполнения этой работы необходимо хорошее знание всех определений связанных с данным проектом, а также правильное понимание самого алгоритма, так как упущение даже одного звена алгоритма повлечет неверный результат.
Собственно для программиста разработка программы для выполнения этого алгоритма означает работа с матрицами. Поэтому должен быть произведен ввод матрицы, а на выходе должны получиться компоненты сильной связности.
Алгоритм
1. Присваиваем p=1 (p− количество компонент связности), .
2. Включаем в множество вершин Vpкомпоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.
3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p+1 и переходим к п. 2.
Пример
Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин n=5.
Рис. 6.
Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом
.
Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:
, ,
,
Следовательно,
.
Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:
.
Присваиваем p=1 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .
Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине v1, чтобы получить матрицу S2(D):
.
Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D− в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:
.
Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:
и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .
Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:
D1: |
D2:
|
D3: |
Блок-схема.
Листинг программы
Программа была написана на C++.
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#define n 5
void main()
{
clrscr();
int i,j,k,s;
cout<<"\n";
int a[n][n],
a1[n][n],
a2[n][n],
a3[n][n],
a4[n][n],
t[n][n],
t_trans[n][n],
sd[n][n];
cout<<"Vvedite elementi matrici smezhnosti po strokam\n";
for (i=0; i<n; i++) //A(D)
{
for (j=0; j<n; j++)
{
cin>>a[i][j];
if(j==4)
{clrscr();
cout<<"Vvedite elementi matrici smezhnosti po strokam\n";}
}
}
for (i=0; i<n; i++) //A1(D)
{
for (j=0; j<n; j++)
{
a1[i][j]=a[i][j];
}
}
clrscr();
cout<<" \n\nElementi matrici:";
gotoxy(1,6);
for (i=0; i<n; i++) //A(D)
{
for (j=0; j<n; j++)
{
textcolor(2);
cprintf("%d",a[i][j]);
if(a[i][j]<10)
gotoxy(wherex()+2,wherey());
else cout<<" ";
if (i==n-1,j==n-1)
{
cout<<"\n\n";
}
}
}
for(i=0;i<n;i++) //A2(D)
{
for(j=0;j<n;j++)
{
s=0;
for(k=0;k<n;k++)
{
s=s+a[i][k]*a1[k][j];
a2[i][j]=s;
}
}
}
for(i=0;i<n;i++) //A3(D)
{
for(j=0;j<n;j++)
{
s=0;
for(k=0;k<n;k++)
{
s=s+a2[i][k]*a[k][j];
a3[i][j]=s;
}
}
}
for(i=0;i<n;i++) //A4(D)
{
for(j=0;j<n;j++)
{
s=0;
for(k=0;k<n;k++)
{
s=s+a3[i][k]*a[k][j];
a4[i][j]=s;
}
}
}
for(i=0;i<n;i++) //vse=1
{
for(j=0;j<n;j++)
{
if(a4[i][j]>1) a4[i][j]=1;
}
}
cout<<"\n\n";
for(i=0;i<n;i++) //T(D), T(D)_trans
{
for(j=0;j<n;j++)
{
if(i==j) t[i][j]=1;
else t[i][j]=a[i][j]+a2[i][j]+a3[i][j]+a4[i][j];
if(t[i][j]>1) t[i][j]=1;
t_trans[j][i]=t[i][j];
}
}
for(i=0;i<n;i++) //S(D)
{
for(j=0;j<n;j++)
{
sd[i][j]=t[i][j]*t_trans[i][j];
}
}
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
textcolor(2);
cprintf("%d",sd[i][j]);
if(sd[i][j]<10)
gotoxy(wherex()+2,wherey());
else cout<<" ";
if (i==n-1,j==n-1)
{
cout<<"\n\n";
}
}
}
cout<<"-----------------------------------\n";
cout<<"\nKomponenti silnoi sviaznosti:\n";
cout<<"{"; //1str
for(i=0; i<n; i++)
{
if(sd[0][i]==1) {
sd[0][i]=0;
cout<<"v"<<i+1<<",";
for(j=0; j<n; j++)
{
sd[j][i]=0;
}
}
}
cout<<"}\n\n\n";
cout<<"{";
for(i=0; i<n; i++) //2str
{
if(sd[1][i]==1) {
sd[1][i]=0;
cout<<"v"<<i+1<<",";
for(j=0; j<n; j++)
{
sd[j][i]=0;
}
}
}
cout<<"}\n\n\n";
cout<<"{";
for(i=0; i<n; i++) //3str
{
if(sd[2][i]==1) {
sd[2][i]=0;
cout<<"v"<<i+1<<",";
for(j=0; j<n; j++)
{
sd[j][i]=0;
}
}
}
cout<<"}\n\n\n";
cout<<"{";
for(i=0; i<n; i++) //4str
{
if(sd[3][i]==1) {
sd[3][i]=0;
cout<<"v"<<i+1<<",";
for(j=0; j<n; j++)
{
sd[j][i]=0;
}
}
}
cout<<"}\n\n\n";
cout<<"{";
for(i=0; i<n; i++) //5str
{
if(sd[4][i]==1) {
sd[4][i]=0;
cout<<"v"<<i+1<<",";
for(j=0; j<n; j++)
{
sd[j][i]=0;
}
}
}
cout<<"}\n\n\n";
gotoxy(16,10);
cout<<"=A(D) (Matrica smezhnosti.)";
gotoxy(16,22);
cout<<"=S(D) (Matrica silnoi sviaznosti.)";
getch();
}
Тестирование программы
Здесь приведены скриншоты работы программы:
Заключение
В курсовой работе был разработан простой алгоритм выделения компонент сильной связности. Программа четко следует алгоритму, тем самым обеспечивается точность решения и стабильность программы. По данному алгоритму была составлена программа, работа которой была продемонстрирована.
Список использованной литературы:
Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика». /Уфимск. гос. авиац. техн. ун-т.; Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -37 с.