Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
MET_UKAZ_Diskretnaja_matematika_230102_file__20...doc
Скачиваний:
1
Добавлен:
01.05.2025
Размер:
709 Кб
Скачать
☆

1.4. Задание на выполнение

Задать с клавиатуры мощность множества , элементы множества и мощность выборки . Реализовать алгоритм генерации сочетания

  1. в лексикографическом порядке;

  2. с помощью кодов Грея.

Задать с клавиатуры мощность множества n и элементы множества. Реализовать алгоритм генерации перестановок:

  1. в лексикографическом порядке;

  2. с помощью вложенных циклов;

  3. транспозицией соседних элементов.

Практическое занятие № 4. «Машинное представление графов»

1.1. Цель работы

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

1.2. Машинные способы представления графов

1.2.1. Матрица смежности

М

если вершина смежна вершине ;

атрицей смежности неориентированного графа G=(X,U), называется квадратная матрица , элементы которой задаются по правилу 1.4.

если вершина не смежна вершине ;

(1.4)

Матрицей смежности ориентированного графа G=(X,U), называется квадратная матрица , элементы которой задаются по правилу 1.5.

если вершина смежна вершине ;

если вершина смежна вершине ;

если вершина не смежна вершине ;

(1.5)

1.2.2. Матрица инцидентности

Матрицей инцидентности неориентированного графа G=(X,U), называется матрица , элементы которой задаются по правилу 1.6.

если вершина инцидентна ребру ;

если вершина не инцидентна ребру .

(1.6)

Матрицей инцидентности ориентированного графа G=(X,U), называется матрица , элементы которой задаются по правилу 1.7.

если вершина начало дуги ;

если вершина конец дуги ;

если вершина не инцидентна дугe .

если - петля при вершине ;

(1.7)

1.2.3. Список ребер

Списком ребер неориентированного графа G=(X,U), называются два массива и , элементы которых задаются по правилу 1.8:

(1.8)

вершина, являющаяся началом ребра с номером i.

вершина, являющаяся концом ребра с номером i.

С

(1.9)

писком ребер ориентированного графа G=(X,U), называются два массива и , элементы которых задаются по правилу 1.9:

вершина, являющаяся началом дуги с номером i.

вершина, являющаяся концом дуги с номером i.

1.2.4. Структура смежности

Структурой смежности графа G=(X,U), называется массив списков

, ,

где - все вершины, смежные вершине

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

#include <iostream.h>

#include <conio.h>

void main()

{

struct List {

int Number;

List *Next;

};

List *Smegn; // массив вершин

int n; // количество вершин графа

clrscr();

cout << "Введите количество вершин графа: ";

cin >> n;

// Выделение памяти под массив вершин

Smegn = new List [n];

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

{

Smegn[i].Number = i+1;

Smegn[i].Next = NULL;

}

// Ввод структуры смежности

cout << "Признак окончания ввода - 0" << endl;

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

{

cout << "Вводите вершины смежные вершине " << i+1 << " : ";

int d = 1;

List* Cur = &Smegn[i];

while (d!=0)

{

cout << "# вершины: ";

cin >> d;

if (d==0) continue;

Cur->Next = new List; // выделение памяти под новый элемент

Cur = Cur->Next;

Cur->Next = NULL;

Cur->Number = d;

}

}

// Печать структуры смежности

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

{

cout << Smegn[i].Number << ": "; // номер вершины

List *Cur = &Smegn[i];

if (Cur->Next == NULL) {cout << endl; continue;}; // Если смежных нет, то

//перейти на следующую

//вершину.

do // пока не пройдены все смежные вершины,

//выводить на экран номера вершин

{

if (Cur->Next->Next == NULL) continue;

Cur = Cur -> Next;

cout << Cur->Number << ",";

}

while (Cur->Next->Next != NULL);

Cur = Cur->Next;

cout << Cur->Number << "." << endl; // вывод последней вершины

}

cout << endl;

// удаление структуры смежности из памяти.

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

{

List *Top;

Top = &Smegn[i];

List* Cur = Top->Next;

delete Top;

Top = Cur;

while (Cur!=NULL)

{

Cur = Top->Next;

delete Top;

Top = Cur;

}

delete [] Smegn;

}

getch();

}

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]