Самостоятельная работа № 11

Построение орграфа данного отношения и описание его характеристик

Цель работы: Закрепить знания и умения в построение графов данного отношения.

Форма отчета: студенты оформляют выполненную работу в печатном виде и предоставляют материал для проверки.

Задания для выполнения работы:

Выполните следующие упражнения:

1) Построить орграфы по матрицам смежности и инцидентности и описать их характеристики:

а)

б)

в)

г)

2) Построить орграф данного отношения и описать его характеристики:

а) на множестве V = {1; 3; 5; 7; 9} задано отношение R = {(x; y) | x ³ y + 2};

б) на множестве V = {0; 1; 2; 3; 4} задано отношение R = {(x; y) | x > y + 1}.

в) на множестве V = {2; 4; 6; 8; 10} задано отношение R = {(x; y) | x < y – 1}.

г) на множестве V = {1; 4; 6; 7; 9} задано отношение R = {(x; y) | x £ y – 2}.

Список литературы:

1) Спирина М.С. Спирин В.В. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. 10-е издание. – М.: Издательский центр «Академия», 2014. – 368 с.

2) Мельников О.И. Теория графов в занимательных задачах. Изд. 3-е, испр. и доп. – М.: Книжный дом «Либроком», 2009. – 232 с.

3) Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 3-е издание – СПб.: Питер, 2009. – 384 с.

4) Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учебное пособие. – М.: ИНТУИТ, Бином. Лаборатория знаний, 2013. – 312 с.