Компютерное представление графов. Перево из матрици смежности в матрицк инцидентности, список смежности, список ребер. лАБА5. Компютерна дискретна математика

• Название: Компютерна дискретна математика
• Анкор: Компютерное представление графов. Перево из матрици смежности в матрицк инцидентности, список смежности, список ребер
• Дата: 10.06.2020
• Размер: 154.78 Kb.
• Имя файла: лАБА5.docx
• Тип: Задача; #129452

Міністерство освіти та науки України

Харківський національний університет радіоелектроніки

Кафедра Прикладної математики

Звіт з лабораторної роботи № 7

з дисципліни «Комп’ютерна дискретна математика»

Виконав: Перевірила:

ст. гр. СТСА-18-1 доцент

Груздо І. В.

Харків 2020

Способи задання графів.

Мета лабораторної роботи: Набуття практичних вмінь і навичок при представленні заданих графів різними способами та можливістю їх комп’ютерної реалізації.

Хід виконання:

1. 
   Постановка задачі:
   
   1. 
      Вирішити задачі для графів згідно з варіантом.
      

Для варіанта 16 задано графи:



Позначимо a - 1, b - 2, c - 3, d – 4, e – 5, f – 6.

Задача 1

Створити програму, яка буде зберігати в комп’ютері заданий граф наступними способами:

а) матрицею суміжності

б) матрицею інцидентності

в) списком ребер

г) списком суміжності.

Передбачити вивід кожного представлення на екран.

Текст програми:

#include

#include

using namespace std;

void matr_sum(int** mass,int n)

{

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

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

std::cin>> mass[i][j];

}

void matr_inc(int** mass, int n, int m)

{

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

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

std::cin>> mass[i][j];

}

void spisok_reber(int** mass,int m)

{

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

{

std::cin >> mass[i][0];

std::cin >> mass[i][1];

}

}

void spisok_smej(vector* mass,int n)

{

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

{

int j;

std::cout << "Количество вершин, смежных " << i + 1 << ":";

std::cin >> j;

cout << endl;

int c;

std::cout << "Введите эти вершины" << ":";

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

{

std::cin >> c;

mass[i].push_back(c);

}

}

}

void vivod_matr_sum(int** mass, int n)

{

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

{

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

std::cout << mass[i][j] << " ";

std::cout << endl;

}

}

void vivod_matr_inc(int** mass, int n, int m)

{

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

{

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

std::cout << mass[i][j] << " ";

std::cout << endl;

}

}

void vivod_spisok_reber(int** mass, int m)

{

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

{

std::cout <<"[" <
std::cout << mass[i][1]<<"]"<
}

}

void vivod_spisok_smej(vector* mass, int n)

{

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

{

int j=mass[i].size();

cout <
for (int p = 0; p < j; p++)

{

std::cout << mass[i][p] << " ";

}

std::cout << endl;

}

}

int main()

{

setlocale(LC_ALL, "Russian");

int n,m;//n-кол. вершин,m-кол. рёбер

cout << "Введите количество вершин и рёбер:" << endl;

cin >> n >> m;

int** matr_smj=new int*[n], **matr_inc1 = new int* [n], ** spis_reber = new int*[m];

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

{

matr_smj[i] = new int[m];

matr_inc1[i] = new int[m];

}

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

{

spis_reber[i] = new int[2];

}

vector *spis_smj=new vector[n];

while (true)

{

std::cout << "[1]-ввести массив; [2]-вывести массив(выбирать если был введен); [3]-выход:"<
int c;

cin >> c;

if (c == 1)

{

std::cout << "[1]-матр. смежности; [2]-матр.инцидентности; [3]-список рёбер; [4]-список рёбер"<
int k;

cin >> k;

if (k == 1)

{

matr_sum(matr_smj, n);

}

else if (k == 2)

{

matr_inc(matr_inc1, n, m);

}

else if (k == 3)

{

spisok_reber(spis_reber, m);

}

else if (k == 4)

{

spisok_smej(spis_smj, n);

}

}

else if (c == 2)

{

std::cout << "[1]-матр. смежности; [2]-матр.инцидентности; [3]-список рёбер; [4]-список рёбер"<
int k;

cin >> k;

if (k == 1)

{

vivod_matr_sum(matr_smj, n);

}

else if (k == 2)

{

vivod_matr_inc(matr_inc1, n, m);

}

else if (k == 3)

{

vivod_spisok_reber(spis_reber, m);

}

else if (k == 4)

{

vivod_spisok_smej(spis_smj, n);

}

}

else break;

}

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

{

delete[] matr_smj[i];

delete[] matr_inc1[i];

}

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

{

delete spis_reber[i];

}

delete[] matr_smj, matr_inc1, spis_reber;

}

Тестування програми:





Як бачимо, програма працює правильно та виконує поставлену задачу як для орієнтованих, так і неорієнтованих графів.

Задача 2

Написати програму, яка виконуватиме наступні завдання:

• 
  за заданою матрицею суміжності побудувати матрицю інцидентності;
  
• 
  за заданою матрицею інцидентності побудувати список ребер;
  
• 
  за заданою матрицею суміжності побудувати список суміжності.
  
• 
  за заданою матрицею інцидентності побудувати матрицю суміжності;
  
• 
  за заданою матрицею суміжності побудувати список ребер;
  
• 
  за заданою матрицею інцидентності побудувати список суміжності.
  

Текст програми для неорієнтованих графів:

#include

#include

using namespace std;

void suminc(int** sum, int** inc, int n, int m)//за матрицею суміжності побудувати матрицю інцидентності

{

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

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

inc[i][j] = 0;

int k = 0;

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

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

if (sum[i][j] > 0&&i!=j)

{

for (int c = 0; c < sum[i][j]; ++c)

{

inc[i][k] = 1;

inc[j][k] = 1;

k++;

}

}

else if (sum[i][j] > 0)

{

inc[j][k] = 2;

k++;

}

}

void incspisreb(int** inc,int** spreb ,int n, int m)//за матрицею інцидентності побудувати список ребер;

{

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

{

int k = 0;

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

if (inc[i][j] > 0)

{

spreb[j][k] = i + 1;

k++;

if (inc[i][j]==2)

{

spreb[j][k] = i + 1;

break;

}

}

}

}

void matr_smjspissmj(int** sum, vector* spis_smj, int n, int m)//за заданою матрицею суміжності побудувати список суміжності.

{

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

{

spis_smj[i].clear();

}

for(int i=0;i
for(int j=0;j
if (sum[i][j] > 0)

{

spis_smj[i].push_back(j+1);

}

}

void matr_incmatr_smej(int** sum, int** inc, int n, int m)//за заданою матрицею інцидентності побудувати матрицю суміжності

{

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

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

sum[i][j] = 0;

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

{

int k = -1, c = -1;

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

{

if (inc[i][j] == 2)

sum[i][i] += 1;

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

{

if (k < 0)

k = i;

c = i;

}

}

if (c >= 0)

{

sum[c][k] += 1;

sum[k][c] += 1;

}

}

}

void matr_smjspis_reber(int** sum, int** spis_reber, int n, int m)//за матрицею суміжності побудувати список ребер;

{

int k = 0;

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

{

spis_reber[i][0] = 0;

spis_reber[i][1] = 0;

}

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

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

if (sum[i][j] > 0)

{

for (int c = 0; c < sum[i][j]; ++c)

{

spis_reber[k][0] = i + 1;

spis_reber[k][1] = j + 1;

k++;

}

}

}

void matr_incspis_sum(int** inc, vector* spis_smj, int n, int m)//за матрицею інцидентності побудувати список суміжності

{

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

{

spis_smj[i].clear();

}

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

{

int k = -1;

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

{

if (inc[i][j] == 2)

spis_smj[i].push_back(i+1);

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

{

if (k < 0)

k = i;

else

{

bool ch = true;

for (int c = 0; c < spis_smj[i].size(); c++)

if (spis_smj[i][c] == k + 1)

ch = false;

if (ch)

{

spis_smj[k].push_back(i + 1);

spis_smj[i].push_back(k + 1);

}

} }

}

}

}

void matr_sum(int** mass, int n)

{

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

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

std::cin >> mass[i][j];

}

void vivod_matr_sum(int** mass, int n)

{

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

{

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

std::cout << mass[i][j] << " ";

std::cout << endl;

}

}

void vivod_matr_inc(int** mass, int n, int m)

{

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

{

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

std::cout << mass[i][j] << " ";

std::cout << endl;

}

}

void vivod_spisok_reber(int** mass, int m)

{

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

{

std::cout << "[" << mass[i][0] << " ";

std::cout << mass[i][1] << "]" << endl;

}

}

void vivod_spisok_smej(vector* mass, int n)

{

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

{

int j = mass[i].size();

cout << i + 1 << ": ";

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

{

std::cout << mass[i][p] << " ";

}

std::cout << endl;

}

}

int main()

{

setlocale(LC_ALL, "russian");

int n, m;//n-кол. вершин,m-кол. рёбер

cout << "Введите количество вершин и рёбер:" << endl;

cin >> n >> m;

int** matr_smj = new int*[n], ** matr_inc1 = new int*[n], ** spis_reber = new int*[m];

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

{

matr_smj[i] = new int[n];

matr_inc1[i] = new int[m];

}

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

{

spis_reber[i] = new int[2];

}

vector* spis_smj = new vector[n];

cout << "Введите матрицу смежности:" << endl;

matr_sum(matr_smj, n);

cout << "Перевод из матрицы смежности в матрицу инцидентности:" << endl;

suminc(matr_smj, matr_inc1,n,m);

vivod_matr_inc(matr_inc1, n, m);

cout << "Перевод из матрицы инцидентности в список рёбер:" << endl;

incspisreb(matr_inc1, spis_reber, n, m);

vivod_spisok_reber(spis_reber, m);

cout << "Перевод из матрицы смежности в список смежности:" << endl;

matr_smjspissmj(matr_smj, spis_smj, n, m);

vivod_spisok_smej(spis_smj, n);

cout << "Перевод из матрицы инцидентности в матрицу смежности:" << endl;

matr_incmatr_smej(matr_smj, matr_inc1, n, m);

vivod_matr_sum(matr_smj, n);

cout << "Перевод из матрицы смежности в список рёбер:" << endl;

matr_smjspis_reber(matr_smj, spis_reber, n, m);

vivod_spisok_reber(spis_reber, m);

cout << "Перевод из матрицы инцидентности в список смежности:" << endl;

matr_incspis_sum(matr_inc1, spis_smj, n, m);

vivod_spisok_smej(spis_smj, n);

for (int i = 0; i
{

delete[] matr_smj[i];

}

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

{

delete[] matr_inc1[i];

}

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

{

delete spis_reber[i];

}

delete[] matr_smj, matr_inc1, spis_reber;

}

Тестування програми:



Текст програми для орієнтованих графів:

clude

#include

using namespace std;

void sumInc(int** sum, int** inc, int n, int m)//за матрицею суміжності побудувати матрицю інцидентності*

{

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

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

inc[i][j] = 0;

int k = 0;

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

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

if (sum[i][j] > 0 && i != j)

{

for (int c = 0; c < sum[i][j]; ++c)

{

inc[i][k] = 1;

if (sum[j][i] > c)

{

inc[j][k] = 1;

if (j > i)

{

inc[i][k] = 0;

inc[j][k] = 0;

k--;

}

}

else

inc[j][k] = -1;

k++;

}

}

else if (sum[i][j] > 0)

{

inc[j][k] = 2;

k++;

}

}

void incSpisReb(int** inc, int** spreb, int n, int m)//за матрицею інцидентності побудувати список ребер;*

{

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

{

int k = 0;

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

if (inc[i][j] > 0)

{

spreb[j][0] = i + 1;

if (inc[i][j] == 2)

{

spreb[j][1] = i + 1;

k++;

break;

}

}

else if (inc[i][j] < 0)

{

spreb[j][1] = i + 1;

k++;

}

if (k == 0)

{

for (int c = 0; c < m; ++c)

{

if (inc[c][j] > 0)

{

spreb[j][1] = c + 1;

break;

}

}

}

}

}

void matr_smjSpissmj(int** sum, vector* spis_smj, int n, int m)//за заданою матрицею суміжності побудувати список суміжності.*

{

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

{

spis_smj[i].clear();

}

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

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

if (sum[i][j] > 0)

{

spis_smj[i].push_back(j + 1);

}

}

void matr_incMatr_smej(int** sum, int** inc, int n, int m)//за заданою матрицею інцидентності побудувати матрицю суміжності*

{

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

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

sum[i][j] = 0;

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

{

bool fcheck = false;

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

{

if (inc[i][j] == 2)

sum[i][i] += 1;

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

{

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

{

if (p == i)continue;

if (inc[p][j] == -1)

{

sum[i][p] += 1;

break;

}

if (inc[p][j] == 1)

{

sum[i][p] += 1;

sum[p][i] += 1;

fcheck = true;

break;

}

}

}

if (fcheck)

break;

}

}

}

void matr_smjSpis_reber(int** sum, int** spis_reber, int n, int m)//за матрицею суміжності побудувати список ребер;*

{

int k = 0;

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

{

spis_reber[i][0] = 0;

spis_reber[i][1] = 0;

}

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

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

if (sum[i][j] > 0)

{

int p= sum[i][j];

if (j 0)

p = sum[i][j] - sum[j][i];

for (int c = 0; c < p; ++c)

{

spis_reber[k][0] = i + 1;

spis_reber[k][1] = j + 1;

k++;

}

}

}

void matr_incSpis_sum(int** inc, vector* spis_smj, int n, int m)//за матрицею інцидентності побудувати список суміжності*

{

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

{

spis_smj[i].clear();

}

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

{

bool check = false;

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

{

if (inc[i][j] == 2)

spis_smj[i].push_back(i + 1);

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

{

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

{

if (inc[c][j] == -1)

{

spis_smj[i].push_back(c + 1);

check = true;

break;

}

if (inc[c][j] == 1 && c != i)

{

spis_smj[i].push_back(c + 1);

spis_smj[c].push_back(i + 1);

check = true;

break;

}

}

}

if (check)

{

break;

}

}

}

}

void matr_sum(int** mass, int n)

{

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

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

std::cin >> mass[i][j];

}

void vivod_matr_sum(int** mass, int n)

{

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

{

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

std::cout << mass[i][j] << " ";

std::cout << endl;

}

}

void vivod_matr_inc(int** mass, int n, int m)

{

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

{

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

{

if (mass[i][j] < 0)

std::cout << mass[i][j] << " ";

else

std::cout << " " << mass[i][j] << " ";

}

std::cout << endl;

}

}

void vivod_spisok_reber(int** mass, int m)

{

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

{

std::cout << "[" << mass[i][0] << " ";

std::cout << mass[i][1] << "]" << endl;

}

}

void vivod_spisok_smej(vector* mass, int n)

{

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

{

int j = mass[i].size();

cout << i + 1 << ": ";

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

{

std::cout << mass[i][p] << " ";

}

std::cout << endl;

}

}

int main()

{

setlocale(LC_ALL, "Russian");

int n, m;//n-кол. вершин,m-кол. рёбер

cout << "Введите количество вершин и рёбер:" << endl;

cin >> n >> m;

int** matr_smj = new int* [n], ** matr_inc1 = new int* [n], ** spis_reber = new int* [m];

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

{

matr_smj[i] = new int[n];

matr_inc1[i] = new int[m];

}

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

{

spis_reber[i] = new int[2];

}

vector* spis_smj = new vector[n];

cout << "Введите матрицу смежности:" << endl;

matr_sum(matr_smj, n);

cout << "Перевод из матрицы смежности в матрицу инцидентности:" << endl;

sumInc(matr_smj, matr_inc1, n, m);

vivod_matr_inc(matr_inc1, n, m);

cout << "Перевод из матрицы инцидентности в список рёбер:" << endl;

incSpisReb(matr_inc1, spis_reber, n, m);

vivod_spisok_reber(spis_reber, m);

cout << "Перевод из матрицы смежности в список смежности:" << endl;

matr_smjSpissmj(matr_smj, spis_smj, n, m);

vivod_spisok_smej(spis_smj, n);

cout << "Перевод из матрицы инцидентности в матрицу смежности:" << endl;

matr_incMatr_smej(matr_smj, matr_inc1, n, m);

vivod_matr_sum(matr_smj, n);

cout << "Перевод из матрицы смежности в список рёбер:" << endl;

matr_smjSpis_reber(matr_smj, spis_reber, n, m);

vivod_spisok_reber(spis_reber, m);

cout << "Перевод из матрицы инцидентности в список смежности:" << endl;

matr_incSpis_sum(matr_inc1, spis_smj, n, m);

vivod_spisok_smej(spis_smj, n);

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

{

delete[] matr_smj[i];

}

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

{

delete[] matr_inc1[i];

}

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

{

delete spis_reber[i];

}

delete[] matr_smj, matr_inc1, spis_reber;

}

Тестування програми:



Висновок

Набули практичні вміння і навички про представлення заданих графів різними способами та можливістю їх комп’ютерної реалізації

Відповіді на контрольні питання

1. 
   
   Що таке «граф»?
   

Граф – це сукупність об'єктів із зв'язками між ними. Або або неорієнтований граф G — це впорядкована пара G:=(V,E), для якої виконуються наступні умови:

V — множина вершин або вузлів,

E — множина пар (у випадку неорієнтованого графу невпорядкованих) вершин з V, які називають ребрами.

2. 
   
   Які є способи представлення графів?
   

Графічний, матриці суміжності, інцидентності, списки ребер, суміжності,

3. 
   
   Які особливості комп’ютерної реалізації графів?
   

При комп’ютерній реалізації графів недоступний графічний спосіб, тому сам граф задають через матриці суміжності, інцидентності, списки ребер, суміжності, зберігаючи їх в підходящих структурах даних.

4. 
   
   Чим відрізняються матриця суміжності від матриці інцидентності?
   

Матриця суміжності має розмір n*n та передає інформацію про суміжність вершин, матриця інцидентності має розмір m*n та передає інформацію про інцидентність ребра та вершини (n - кількість вершин, m – кількість ребер)

5. 
   
   В яких випадках задання графа матрицею суміжності не є доцільним?
   

Якщо граф розріджений, то доцільнішим є використання списку суміжності. Також матриця суміжності неефективна для зберігання дерева.

6. 
   
   Які графи називають простими? мультиграфами? псевдографами? орієнтованими? навантаженими?
   

Простий граф – це граф без кратних дуг і петель.

Мультиграф – це граф, який містить кратні дуги і петлі.

Псевдограф – це інша назва мультиграфа в теорії графів.

Орієнтований граф – граф, ребрам якого задано направлення.

Навантажений граф – граф, у якого кожне ребро має свою вагу, тобто кожному ребру поставлено у відповідність певне число.

7. 
   Оцініть об’єм пам’яті, необхідний для збереження графів у вигляді: матриці суміжності, матриці інцидентності, списку ребер, списку суміжності.
   

Для зберігання у вигляді:

матриці суміжності – O(n^2);

матриці інцидентності – O(n*m);

списку ребер – O(m);

списку суміжності – O(n) (n - кількість вершин, m – кількість ребер).

Завдання на додатковий бал

Помилку допущено в прикладі матриці суміжності, вона виділена червоним.