Часть 2. 1. Построить аналитически и графически объединение, пересечения, разность графов G и H, дополнение графа G по отображению до универсального

ДАНО: Два графа G (X, F) и H (Y, P).

НЕОБХОДИМО:

1. Построить аналитически и графически объединение, пересечения, разность графов G и H, дополнение графа G по отображению до универсального.

2. Для графа S = G U H построить матрицы смежности, инцидентности, достижимости; конденсацию и базу графа; минимальные и наименьшее доминирующие множества.

3. Для графа S = G U H построить Гамильтонов и Эйлеров путь (если они не существуют, то дополнить граф необходимыми дугами, обозначив их на графе). Гамильтонов путь построить с использованием алгоритма Робертса и Флореса [6].

Варианты заданий для курсовой работы приведены в Приложении.

ЛИТЕРАТУРА

1. Босин П.Л., Булыгии В.С., Кулешов К.Г. Лабораторные работы но курсу «Основы теории конечных динамических систем», — М.: МАИ, 1985.

2. Булыгин B.C. Логические основы теории дискретных устройств: учеб. пособие. - M.: МАИ, 1983.

3. Булыгин B.C. Основы проектирования дискретных устройств АСУ: учеб. пособие. - M.: МАИ, 1982.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. - М.: Энергия, 1968.

5. Просветов Г.И. Дискретная математика:задачи и решения: учебное пособие. – М.:БИНОМ. Лаборатория знаний,2008. – 222 с.

6. Кристофидес Н, Теория графов: Алгоритмический подход. - М.: Мир, 1978.

7. Булыгин B.C., Ескин В.И.. Модели дискретных устройств с памятью в АСУ: Учеб. пособие. - M.: Изд-во МАИ, 1993. - 72 с.: ил.

8. Мелихов A.H. Ориентированные графы и конечные автоматы. - M.: Наука, 1971.