Архив2 / курсовая docx100 / kursovaya_30_var_Poloskov_Yury_IP-21

Федеральное агентство морского и речного транспорта Федеральное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет водных коммуникаций»

––––––––––––––––––––––––––––––––––––––––––––––––––––––––

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА «КОМПЛЕКСНОЕ ОБЕСПЕЧЕНИЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ»

КУРСОВАЯ РАБОТА

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

Вариант № 30

на тему:

Представление неориентированных графов в виде связанных списков смежности.

Выполнил: студент(ка) группы ИП–21

__ПОЛОСКОВ Юрий Сергеевич_________ _________________

(фамилия, имя, отчество) (подпись)

Руководитель:_доктор технических наук, профессор __________

(ученая степень, ученое звание)

__НЫРКОВ Анатолий Павлович_________ _________________

(фамилия, имя, отчество) (подпись)

Представлена на кафедру: « 14 » декабря 2012 г.

Санкт – Петербург

2012

Представление неориентированных графов в виде связанных списков смежности.

НЕОРИЕНТИРОВАННЫЕ ГРАФЫ.

Граф G(V, E) — совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам, v’ и v’’, которые оно соединяет. При этом вершина v’ и ребро e называются инцидентными друг другу, а вершины v’ и v’’ называются смежными. Часто пишут v’, v’’ из G и e из G. Принято обозначение n для числа вершин графа (мощность множества V): |V (G)| = n, и m для числа его ребер: |E(G)| = m. Говорят, что граф G есть (n, m) граф, где n — порядок графа, m — размер графа.

Если все ребра графа неориентированные, т.е. пары вершин,

определяющие элементы множества E, неупорядочены, то такой граф называется неориентированным графом, или неографом.

Две вершины, связанные между собой ребром, равноправны:

(v’, v’’) = (v’’, v’).

Примеры неориентированных графов в жизни.

Граф Вершины Ребра

Семья Люди Родственные связи

Город Перекрестки Улицы

Сеть Компьютеры Кабели

Домино Костяшки Возможность

Дом Квартиры Соседство

Лабиринт Развилки и тупики Переходы

Метро Станции Пересадки

Неориентированный граф.

G=(V, X): X - множество ребер Е.

V={v₁, v₂, v₃, v₄, v₅},

X={x₁={v₁,v₂}, x₂={v₂,v₃}, x₃={v₂,v₄}, x₄={v₃,v₄}}. (см. Рис. 1)

Рис. 1

СПИСКИ СМЕЖНОСТИ.

Во многих задачах граф создается динамически, т.е. в ходе решения задачи меняется множество вершин и множество ребер (или дуг). В этом случае эффективным способом машинного представления графа является список смежности.

Для задания множества вершин, непосредственно достижимых из вершины v, используют однонаправленный линейный список. Каждый элемент такого списка включает данные (например, некоторое число) и указатель на следующий элемент списка. Список в целом задается указателем на его первый элемент (голову списка). Последний элемент списка содержит «пустой» указатель: в соответствии с примером:

v₁ |→v₂→v₇→…→v₉→0.

Задать для вершины v ее список смежности означает в произвольном порядке поместить в данные элементов списка номер вершин u, для которых в неориентированном графе есть ребро между v и u (v - u).

Примеры списков смежности:

Список смежности для этого графа:

V₁| ->V₂

V₂| ->V₁->V₃->V₄

V₃| ->V₄->V₂

V₄| ->V₃->V₂

V₅|

Еще пример представления неориентированного графа в виде списка смежности:

1 | -> 2 -> 5

2 | -> 1 -> 3 -> 4 -> 5

3 | -> 2 -> 4

4 | -> 2 -> 3 -> 5

5 | -> 1 -> 2 -> 4

Для неориентированного графа сумма длин всех списков равна удвоенному числу ребер, так как  ребро (u, v) порождает элементы в списках вершины u  и вершины v. Количество памяти для представления графа оценивается как O(V + E).

Списки смежности удобны, когда наряду с номером вершины нужно хранить дополнительную информацию (например, вес ребра, родителя вершины, метку вершины).

Недостатком представлений является то, что для того, чтобы узнать есть ли ребро из вершины u и v приходится просматривать весь список.

Практическое задание.

Представить в виде списка смежности неориентированный граф:

G(V,E):

V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

E={{1,6},{1,19},{2,6},{2,19},{3,6},{3,10},{3,19},{4,11},{4,14},{4,19},{5,14},{5,15},{5,18},

{5,19},{6,7},{6,8},{6,9},{7,10},{8,10},{9,10},{11,12},{11,14},{12,13},{13,14},{15,16},{15,18},{16,17},

{17,18}}.

Для нахождения списка смежности при помощи программы на языке программирования C++, мы можем использовать 2 способа решения поставленной задачи.

1 способ:

Неориентированный граф задан ребрами.

В текстовой файл мы записываем все ребра нашего графа в формате:

1 6

1 19

2 6

2 19

3 6

3 10

…

Для получения списка смежности используем написанный нами код (С++):

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

int main()

{

cout << "G(V,E):"<< endl;

cout << "V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}"<< endl;

cout << "E={{1,6},{1,19},...,{17,18}}";

ifstream fin("graf.txt", ifstream::in);

if(!fin)

{

cout << "File graf.txt not found" << endl;

return 1;

}

cout << endl<< endl;

cout << "The list of ribs of graf from file: " <<endl;

int b[29][3];

for(int i=1;i<29;i++)

{

int j=1;

cout << setw(1) << "{" <<setw(2);

fin >> b[i][j];

cout << b[i][j] <<",";

fin >> b[i][j+1];

cout <<setw(2)<< b[i][j+1] <<"} ";

};

cout << endl;

cout << endl;

cout << "The list of adjacency: " <<endl;

for(int k=1;k<20;k++)

{

cout << setw(2) << k <<"|";

int j=1;

for(int i=1;i<29;i++)

{

if (b[i][j]==k) cout << "->" << b[i][j+1];

if (b[i][j+1]==k) cout << "->" << b[i][j];

}

cout << endl;

}

cout << endl;

fin.close();

system("pause");

return 0;

}

Суть алгоритма представленного в программе заключается в том, что мы заносим в матрицу В все ребра нашего графа и затем для каждой вершины графа ( V') пробегаем по матрице В и находим все смежные вершины для ( V') и выводим их. Так как ребра задаются только один раз (от V' к V'') то мы должны при выводе вершин (к которым уже произвели вывод) учесть и обратный порядок (от V'' к V').

Результат работы программы:

2 способ:

Неориентированный граф задан матрицей смежности.

В текстовой файл мы записываем матрицу смежности нашего графа:

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1

1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0

0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0

1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Матрица должна бать симметрична относительно главной диагонали.

Мы можем проверить верна ли наша матрица в Maple:

Матрица верна, следовательно мы можем приступить к запуску программы на C++:

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

void spisoc(int **a, int n)

{

int j;

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

{

cout <<setw(2)<< i+1 << "|";

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

{

if (a[i][j]==1) cout << "->" << j+1;

}

cout <<endl;

}

}

int main()

{

cout << "G(V,E):"<< endl;

cout << "V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}"<< endl;

cout << "E={{1,6},{1,19},{2,6},{2,19},{3,6},{3,10},{3,19},{4,11},{4,14},{4,19},{5,14},"<<endl<<" {5,15},{5,18},{5,19},{6,7},{6,8},{6,9},{7,10},{8,10},{9,10},{11,12},{11,14},"<<endl<<" {12,13},{13,14},{15,16},{15,18},{16,17},{17,18}}";

const int n=19;

ifstream fin("lab4.txt", ifstream::in);

if(!fin)

{

cout << "File lab4.txt not found" << endl;

return 1;

}

int **a = new int *[n];

cout << endl<< endl;

cout << "Adjacency matrix:" << endl;

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

{

a[i] = new int[n];

for(int j=0;j<n;j++)

{

fin >> a[i][j];

cout << a[i][j] <<" ";

}

cout << endl;

}

cout << endl;

cout << endl;

cout << "The list of adjacency: " <<endl;

spisoc(a,n);

cout << endl;

fin.close();

system("pause");

return 0;

}

Алгоритм этой программы очень схож с алгоритмом предыдущей программы, разница лишь в том что вы сначала заполняем матрицу А единицами и нулями (считываем из файла), а затем пробегаем по всем ее элементам и если мы «натыкаемся» на элемент А[i][j]=1, то выводим для вершины i вершину значение которой равно j. Здесь нам не нужно учитывать обратный путь (от V'' к V') так как в матрице смежности значения A[i][j] = A[j][i].

Результат работы программы:

Сравнивая результат 2 программ реализующие 2 способы мы видим что списки смежности у нас одинаковые, и если сверить их со списком смежности полученным ручным способом (пробегая по всем вершинам и записывая номера вершин, смежных с ними), то убеждаемся что результаты мы получили верные.

Список смежности заданного неориентированного графа:

1|->6->19

2|->6->19

3|->6->10->19

4|->11->14->19

5|->14->15->18->19

6|->1->2->3->7->8->9

7|->6->10

8|->6->10

9|->6->10

10|->3->7->8->9

11|->4->12->14

12|->11->13

13|->12->14

14|->4->5->11->13

15|->5->16->18

16|->15->17

17|->16->18

18|->5->15->17

19|->1->2->3->4->5

СПИСОК ЛИТЕРАТУРЫ.

1. М. Н. Кирсанов - ГРАФЫ В MAPLE, Задачи, алгоритмы, программы. (Пособие по дискретной математике для студентов университетов) МОСКВА, ФИЗМАТЛИТ, 2007.

2. http://otherreferats.allbest.ru/mathematics/d00120818.html

3. http://www.uchi-it.ru/9/7/11.html

4. http://edu.nstu.ru/courses/saod/graph.html

5. http://atomlex.narod.ru/discret/grafs.htm

6. http://algo.at.ua/publ/algoritmy/sposoby_predstavlenija_grafov/4-1-0-4