Теоретическая справка. Методические указания и задания

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

«ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Методические указания и задания

к лабораторным работам

по курсу “ОДМ часть 2 “

(для студентов, обучающихся по направлению подготовки

“Программная инженерия”)

Донецк – 2011

УДК 518.551071

Методические указания и задания к лабораторным работам по курсу “ ОДМ часть 2“ ” (для студентов специальности “Программная инженерия ”) / сост.: Назарова И.А. – Донецк: ДонНТУ, 2011. - 53с.

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

Составители: Назарова И. А., к.т.н., доц.

Рецензент: Теплинский С. В., к.т.н., доц.

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

Подграфы и изоморфизм

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

Теоретическая справка

Пусть V – некоторое непустое множество ().

– множество всех его двухэлементных подмножеств, – неупорядоченная пара элементов множества . .

Неориентированный граф G – пара множеств (V, E), , где

V – множество вершин графа G,

E – множество рёбер графа G.

Если |V|=p, а | E|=q, то обозначают граф G, как (p, q)- граф или p -граф.

Смежные вершины графа G – вершины, соединенные ребром.

Смежные ребра графа G – ребра, имеющие общую вершину.

Инцидентные ребро и вершина – вершина является одним из концов ребра.

Конечный граф – множество вершин графа конечно.