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

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

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. https://otherreferats.allbest.ru/mathematics/d00120818.html

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

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

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

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