МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”
Кафедра 603
Лабораторна робота № 3
ТЕОРИЯ ГРАФОВ.
ПОРЯДКОВАЯ ФУНКЦИЯ НА ГРАФЕ
з дисципліни “Дискретні структури”
ХАІ.603.622П.13В.050103.126332.ПЗ
Виконав студент гр. 622П Бровко В.К.
________________ (№ групи) (П.І.Б)
(підпис, дата)
Перевірив:_______ к.т.н. доц Труш Г.О.
(наукова ступінь, вчене звання)
_____________________________
(підпис, дата) (П.І.Б)
Цель работы: изучить понятие функции на графе; научиться находить порядковую функцию на графе методом Демукрона.
Задачи
1. Ознакомиться с приведенными теоретическими понятиями о порядковой функции на графе.
2. Изучить алгоритм метода Демукрона для поиска порядковой функции графа без контуров с помощью приведенных примеров.
3. Решить вручную задачу поиска порядковой функции графа без контуров для графа своего варианта.
4. Написать программу (в произвольно выбранной среде программирования), которая реализует метод Декмукрона.
Вариант 1
Ручные вычисления
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | |
| X1 | |||||||
| X2 | |||||||
| X3 | |||||||
| X4 | |||||||
| X5 | |||||||
| X6 | |||||||
| X7 | |||||||
| |||||||
| |||||||
| |||||||
|
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LR3
{
class Program
{
// Генерация массива
static private int[][] initArray()
{
int[][] mat = new int[7][];
mat[0] = new int[7] { 0, 1, 1, 0, 0, 0, 0 };
mat[1] = new int[7] { 0, 0, 0, 1, 0, 0, 0 };
mat[2] = new int[7] { 0, 1, 0, 1, 0, 1, 0 };
mat[3] = new int[7] { 0, 0, 0, 0, 1, 1, 1 };
mat[4] = new int[7] { 0, 0, 0, 0, 0, 0, 1 };
mat[5] = new int[7] { 0, 0, 0, 0, 0, 0, 0 };
mat[6] = new int[7] { 0, 0, 0, 0, 0, 1, 0 };
return mat;
}
// Вывод матрицы на экран
static private void outMatrix(int[][] x)
{
int i, j;
for (i = 0; i < x.Length; i++)
{
for (j = 0; j < x[i].Length; j++)
Console.Write(" " + x[i][j]);
Console.WriteLine();
}
Console.Write("\n");
}
// Вывод массива на экран
static void outArray(int[] x)
{
for (int i = 0; i < x.Length; i++)
if (x[i] >= 0)
Console.Write(x[i] + "\t");
else Console.Write("-\t");
}
// Сумма столбцов матрицы смежности
static int[] sumOfMatrix(int[][] a)
{
int[] x = new int[a[0].Length];
int i, j;
for (i = 0; i < a.Length; i++)
x[i] = 0;
for (i = 0; i < a.Length; i++)
for (j = 0; j < a[0].Length; j++)
x[i] += a[j][i];
return x;
}
static void Main(string[] args)
{
int[][] mat = initArray();
Console.WriteLine("Первоначальный граф (в виде матрицы смежности):");
outMatrix(mat);
//Console.WriteLine("Сумма строк матрицы:");
//outArray(layer);
int[] layer = sumOfMatrix(mat);
Console.Write("\n\nРасчитываем слои порядковой функции:\n");
int l = 0, n = 1;
List<string> res = new List<string>();
string r = "";
int i;
while (l < mat.Length)
{
r = "";
Console.Write("Шаг " + n++ + ": ");
outArray(layer);
Console.WriteLine();
for (i = 0; i < layer.Length; i++)
{
if (layer[i] == 0)
{
r += (i + 1) + " ";
layer[i]--;
l++;
}
else
layer[i]--;
}
res.Add(r);
}
Console.WriteLine("\nРезультат: порядковая функция выделенного графа имеет уровни:");
for (i = 0; i < res.Count; i++)
Console.WriteLine("Уровень: " + (i + 1) + "\t\t Вершины: " + res[i]);
Console.Read();
}
}
}
Результаты работы программы
Рис.1. Первый тестовый пример.
Выводы: Выполнив данную лабораторную работу, я изучил понятие функций на графе и научился находить порядковую функцию на графе методом Демукрона. После чего, реализовал программу на языке С# в программной среде Microsoft Visual Studio 2010.
