Министерство образования и науки украины государственное высшее учебное заведение донецкий национальный технический университет

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

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

по курсу “Топология экономических структур“

(для студентов специальности “Экономическая кибернетика”)

Утверждено на заседании кафедры прикладной математики и информатики протокол № 4 от 19.12.2009

Донецк – 2009

УДК 518.551071

Методические указания и задания к лабораторным работам по курсу “Топология экономических структур” (для студентов специальности “Экономическая кибернетика”) / сост.: Назарова И.А. – Донецк: ДонНТУ, 2009. - 74с.

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

теория графов;
комбинаторика.

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

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

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

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

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

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

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

V⁽²⁾ – множество всех его двухэлементных подмножеств,

V⁽²⁾={(u,v)|u,vV,неупорядоченная пара}.

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

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

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

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

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

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

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

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

Способы задания графов

Явное перечисление множеств вершин V и ребер E.
Графический способ описания: прообраз вершины – точка, прообраз ребра – отрезок прямой или кривой.
Матричные способы описания.