Дискретная математика

Санкт-Петербургский государственный технологический институт (технический университет)

Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный технологический институт
(Технический университет)
Кафедра систем автоматизированного проектирования и управления
В.И. Халимон, А.Ю. Рогов, О.В. Проститенко
Дискретная математика
(Операции на графах, булева алгебра)
Учебное пособие для студентов заочного обучения специальности 220701
Санкт-Петербург
2009 год

Стоимость выполнения контрольных работ 1, 2 и 3 на заказ составляет ... руб

По данной методичке готовы варианты: 02, 04, 10, 24.

К.р. 1

Задание 1
Построить граф, состоящий из Z изолированных компонент мощностью N1, N2б,...,Nz и T изолированных вершин. Во всем графе должно быть I истоков, S стоков, V висячих вершин, R регулярных вершины, три из которых имеют степени r1, r2, r3. Максимальная степень кратности дуг графа должна быть K. В графе должно быть не менее, чем M пар противоположных дуг. В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины.
Задание 2
Построить ориентированный граф из 7 вершин и 14 дуг, содержащий один исток, один сток, одну изолированную вершину, одну регулярную вершину, одну петлю, пару одинаково направленных дуг, пару противоположно направленных дуг. С истоком и со стоком должно быть связано более двух дуг. Построить и проанализировать следующие способы представления графов: матрица смежности, матрица инцидентности, матрицы окрестностей вершин по входам и по выходам, список дуг. В отчете представить построенный граф и матричные представления графа с описанием.
Задание 3
Построить связанный граф из N вершин, не содержащих висячих и изолированных вершин, но содержащий T точкек сочленения так, чтобы они не были смежными. Рассчитать ранги вершин этого графа. В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины.
Задание 4
Построить связанный ориентированный граф, содержащий K сильных компонент связанности мощностью N1, N2,...,Nk. Свернуть граф по найденным компонентам. В отчете представить граф, раскрашенный по компонентам и граф-свертку.
Задание 5
Построить связанный ориентированный ациклический непоследовательный граф, состоящий из L порядковых уровней мощностью N1,N2,...,NL. Граф содержит N1 истоков и NL стоков. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку.
Задание 6
Построить связанный граф из P вершин и Q дуг. Используя метод, описанный в учебном пособии, перечислить все маршруты этого графа, длиной 1, 2, 3. В отчете привести граф и выкладки по вычислению матриц.
Задание 7
Построить связанный ориентированный граф из N вершин, содержащий один исток и один сток, не содержащий петель. Задать веса на дугах графа и пронумеровать все вершины. Между истоком и стоком построить не менее P путей через остальные вершины, длиной больше k-дуг.
Изменяя веса на дугах модифицировать граф так, чтобы кратчайшие пути по сумме весов и по количеству дуг между истоком и стоком не имели ни одной общей дуги. В отчете представить граф с выделенными путями, указать длину путей по весам и по количеству дуг.
На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей с корнем в стоке.
Задание 8
Построить связанный ориентированный граф, имеющий как минимум две центральные вершины, как минимум две периферийные вершины, как минимум две обычные вершины так, чтобы его радиус был не равен нулю и не равен диаметру. Начать построение с 6 вершин, добиться результата добавлением и удалением дуг и вершин. Построить максимальное покрывающее дерево кратчайших путей. В отчете представить построенные граф с выделенным деревом, центром и периферией, над вершинами надписать их эксцентриситеты, указать значения радиуса и диаметра графа.
Задание 9
Придумать Q свойств некой системы из N элементов. Построить ориентированный граф системы, задать в качестве вспомогательного веса вершин текстовые идентификаторы, а в качестве основного веса – бинарные цепочки (ширина равна количеству свойств). Проставить на вершинах основные веса в виде цепочки нулей и единиц в зависимости от того, обладает вершина соответствующим свойством (1) или нет (0). Используя метод «свертка по кодам» выполнить три свертки построенного графа при различных сочетаниях нулей и единиц в маске макросвойств. В отчете представить описание свойств, описание элементов системы, исходные граф системы с бинарными вершинами, три графа свертки по трем маскам макросвойств.

Дата выполнения: 26/02/2010