Вопросы к экзамену по курсу “Дискретная математика” (стр. 2 )

11) Выполнить топологическую сортировку универсума в соответствии с частичным порядком на нем.

Пример выполнения:

Дано упорядоченное множество , определенное на носителе и заданное своей диаграммой Хассе

1) Высоты элементов

	1	2	3	4	5	6
	1	2	3	1	2	1

2) Высота посет

3) Максимальные  и минимальные элементы  ,

4) Все максимальные цепи. Всякая максимальная цепь упорядоченного множества начинается в некотором минимальном элементе посет и заканчивается в некотором максимальном элементе. Множество таких цепей находится методом полного перебора путем анализа диаграммы Хассе данного упорядоченного множества. В данном примере получаем такие цепи:

,,,,.

5) Матрица отношения сравнимости . Элемент матрицы равен 1, если пара элементов универсума принадлежит  некоторой максимальной цепи упорядоченного множества и нулю в противном случае. Анализируя максимальные цепи, найденные в предыдущем пункте, получаем ответ :

.

Матрица отношения независимости находится как логическое дополнение , получаем:

6) Найти все левые полуинтервалы вида . Заметим, что элемент принадлежит полуинтервалу , если выполняется свойство , что выполняется, если элементы принадлежат некоторой максимальной цепи , причем расположен в этой цепи левее . Рассмотрим все максимальные цепи, найденные ранее: ,,,,.

Анализируя состав этих цепей, получаем ответ:

Аналогично находим правые полуинтервалы:

7) Интервалы вида состоят из всех элементов , проходимых по восходящим путям в диаграмме, ведущим из элемента в элемент . Рассматривая такие пути м все пары сравнимых элементов , получаем ответ:

.

8) Элемент. Элемент матрицы равен 1, если пара элементов связана в диаграмме Хассе ребром, причем элемент имеет меньшую высоту, чем элемент . Анализируя диаграмму Хассе, получаем следующий ответ:

.

9. Множество максимальных антицепей находим методом полного перебора. Получаем ответ:

10. Ширина упорядоченного множества находится как максимальная мощность его антицепей. Опираясь на решение предыдущего пункта, получаем:

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

Теория графов. BFS обход графа.

На множестве вершин граф задан матрицей смежности

Изобразить граф, расположив его вершины равномерно на некоторой окружности. Выполнить BFS обход графа из начальной вершины , построить BFS дерево этого обхода. По результатам BFS обхода из начальной вершины найти следующие характеристики графа при центре :

А) число слоев;

Б) состав слоев;

В) номер слоя каждой вершины или ее расстояние по графу от центра как функцию ;

Г) структуру BFS дерева как функцию .

Д) Изобразить BFS дерево.

Дан граф:

Списки смежности вершин упорядочены по возрастанию номеров смежных вершин, т. е.

Выполнить процедуру BFS поиска в данном графе из начальной вершины s=1, выписав алгоритмические действия по шагам.

Решение:

Для построения BFS дерева используем структуру данных очередь, т. е. структуру в которую новые элементы поступают справа, т. е. с хвоста, а обрабатываются слева, т. е. с головы. Обработка текущей вершины , т. е. вершины в голове очереди заключается в прохождении  списка смежности слева направо. При этом если вершина уже есть в дереве, она пропускается, если вершина новая, т. е. отсутствует в текущем дереве, выполняются следующие действия: