4. Изменить к-ю компоненту в наборе у: у_к:=1-у_к.

5. Выдать набор у как результат итерации.

Содержание отчета:

1. Текст программы на C₊₊ либо Visual Basic (допускается в среде

Delphi);

1. Найти все подмножества заданного множества одним из

предложенных способов.

Лабораторная работа N⁰3

Численная проверка комбинаторного принципа

включений и исключений

Цель работы: изучение комбинаторного принципа включений и

исключений на примере подмножеств и его численная проверка.

Содержание работы:

1. Разработка алгоритма для определения мощности объединения подмножеств исходного конечного множества.

2. Разработка и отладка программы для определения мощности объединения подмножеств.

3. Численная проверка комбинаторного принципа включений

и исключений на основе отлаженной программы.

Краткие теоретические сведения

Пусть даны подмножества A₁, …, A_n (необязательно различные) некоторого конечного множества X, и пусть требуется найти мощность их объединения

.

В первом “приближении” этой мощности можем принять

.

Но это число, очевидно, будет слишком велико, ибо, если имеет место

,

то принадлежащие пересечению

элементы будут посчитаны дважды.

В связи с этим имеет место следующая теорема, более известная как принцип включений и исключений:

Теорема (принцип включений и исключений).

. (*)

Один из возможных случаев принципа включений и исключений изображён на рис. 1. Для этого рисунка, в частности, указанный принцип (*) запишется в виде:

. (**)

Рис. 1. Частный случай принципа включений и исключений.

Методика выполнения работы

1. Разработать общий алгоритм определения мощности объединения подмножеств согласно выражению (**).

2. Составить подпрограмму вычисления .

3. Составить подпрограмму вычисления .

4. Составить подпрограмму вычисления .

5. Составить подпрограмму вычисления .

6. Составить подпрограмму вычисления .

7. Написать единую программу вычисления выражения (**).

8. Выполнить отладку программы, задавая различные данные.

9. Запустив отлаженную программу, по заданным подмножествам A, B, C заданного конечного множества X найти .

Примечание. Допускается не выполнять последовательность операций 2…6, т. е. обойтись без использования подпрограмм

(выполнив п. 1, сразу перейти к п. 7).

Содержание отчёта

1. Текст программы на C₊₊ либо Visual Basic (допускается в среде

Delphi);

2. Результаты выполнения программы для заданных значений

исходных данных.

Лабораторная работа №4

Представление графов в эвм

Цель работы: изучение различных форм представления графов в ЭВМ и разработка алгоритмов и программы перевода графа из одного представления в другие.

Содержание работы:

1. Разработка алгоритмов перевода графа из одного представления в другие.

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

3. Проверка программы на примере заданного графа.

Матричная форма представления графов

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

А = , где а_ij =

Матрица А задает граф с точностью до изоморфизма (по структуре однозначно строится матрица, а по матрице структура).

Два графа эквивалентны, если равны их матрицы смежности.

Два графа эквивалентны, если их матрицы смежности можно получить одинаковыми путем одновременной перестановки строк и столбцов в одной из них.

A_{6 6} =

Задание 1: Нарисуйте граф.

Для мультиграфа и псевдографа:

a_ij=

m(x_i, x_j) – кратность ребер между вершинами х_i и х_j.

Если на вершинах графа заданы веса, то вводится дополнительный массив V длины n, в котором элемент V(i) задает значение веса вершины графа.

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

Для мультиграфа, псевдографа с весами на ребрах и дугах используется трехмерная матрица, где 3-я размерность используется для записи веса ребра, дуги, петли.

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

Для неорграфа

S= , где s_ij =

S_6x7 =

Задание 2: Нарисуйте граф.

Для орграфа учитывается ориентация:

s_ij =

Каждый столбец содержит один элемент, равный 1, и один элемент, равный –1, либо все элементы равны 0 или константе.

Два графа эквивалентны, если равны их матрицы инцидентности.

Для псевдографа, показанного на рисунке, получим такую матрицу:

S_{6 9} =

Если заданы веса, то используются дополнительные матрицы весов вершин и ребер (дуг).

Матрица S задает граф с точностью до изоморфизма, основное преимущество матрицы А перед матрицей S в том, что за один шаг алгоритма можно получить ответ на вопрос, есть ли ребро из вершины х_i в х_j. Основной недостаток матрицы А – большой объем памяти независимо от числа ребер: n².

Векторная форма представления графов

Задание графа массивом преемников вершин

Матрица смежности отображается по строкам одномерным массивом FO, в котором для каждой вершины, начиная с первой, указываются вершины приемники. Списки приемников отдельных вершин разделяются символом Ø:

22

55

Ø

11

33

66

Ø

Ю…

…

Для неорграфа и мультиграфа массив имеет длину 2m+n, для орграфа и псевдографа – m+n.

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

Задание графа массивом предшественников вершин

Здесь матрица смежности отображается по столбцам. Форма массива FI такая же, что и у FO.

Для неорграфов и мультиграфов FO и FI совпадают.

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

Лабораторная работа №5

Внутренняя и внешняя устойчивость множества вершин графа

Цель работы:

1. Нахождение максимально внутренне устойчивого множества и минимально внешне устойчивого множества.

2. Определение чисел внутренней и внешней устойчивости графа

Множество SX вершин орграфа называется внутренне устойчивым, если никакие две вершины не смежны, т.е. S Г(S)=.

Теоретические основы:

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

Число вершин наибольшего по мощности из всех внутренне устойчивых множеств графа называется числом внутренней устойчивости и обозначается (G).

Рассмотрим функцию

(Х1,Х2,…,Хn)=(xixj),

где конъюнкция берется по всем i,j1..n, а Хi - булевы переменные.

Тогда дизъюнктивная форма для функции будет иметь вид:

(Х1,Х2,…,Хn)=(хi1 xi2 …xik)

Теорема 1.

Выражение (хi1xi2…xik) является элементарной конъюнкцией тогда и только тогда, когда множество S={xj1,xj2,…,xjn-k}-максимальное внутренне устойчивое множество. Причем (j1,j2,…,jn-k)(i1,i2,…,ik)={1,2,…,n}.

Множество ТX вершин орграфа G=(X,Г) называется внешне устойчивым, если для любой вершины х выполняется:

Из хТ следует, что Т Г(S).

Число вершин наименьшего по мощности из всех внешне устойчивых множеств графа называется числом внешней устойчивости и обозначается (G)

Теорема 2.

Выражение (хi1 xi2 …xik) является элементарной конъюнкцией дизъюнктивного представления функции (Х1,Х2,…,Хn)=(хi1 xi2 …xik) тогда и только тогда, когда Т={xi1,xi2,…,xik}-минимальное внешне устойчивое множество.

Пример.

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

=(х1 х2) (х2 х3) (х3 х4) (х4 х1)= (х2 х1х3) (х4 х1х3)= (х4 х2) (х1 х3)

Первая конъюнкция дает максимальное внутренне устойчивое множество S1={x1,x3}, а вторая- S2={x2,x4} Число внутренней устойчивости (G)=2.

Определим все минимальные внешне устойчивые множества орграфа:

=(х1 х2) (х2 х3) (х3 х4) (х4 х1)= (х2 х1х3) (х4 х1х3)= (х4 х2) (х1 х3)

Первая конъюнкция дает минимальное внешне устойчивое множество Т1={x1,x3}, а вторая- Т2={x2,x4}. Число внешней устойчивости (G)=2

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

Лабораторная работа №6

Операции над графами

Цель работы: изучение операций, выполняемых над графами.

Содержание работы:

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

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