Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки
Скачать 0.5 Mb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ «ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»  Методические указания и заданияк лабораторным работам по курсу “ОДМ часть 2 “ (для студентов, обучающихся по направлению подготовки “Программная инженерия”) Донецк – 2011УДК 518.551071Методические указания и задания к лабораторным работам по курсу “ ОДМ часть 2“ ” (для студентов специальности “Программная инженерия ”) / сост.: Назарова И.А. – Донецк: ДонНТУ, 2011. - 53с.Приведены теоретические сведения, методические рекомендации, контрольные вопросы и задания для выполнения лабораторных работ по разделу дискретной математики: теория графов. Составители: Назарова И. А., к.т.н., доц. Рецензент: Теплинский С. В., к.т.н., доц. Лабораторная работа № 1 Подграфы и изоморфизм Цель работы: изучение основных понятий теории графов и приобретение практических навыков определения изоморфизма и изоморфной вложимости графов, построение подграфов, независимых, доминирующих множеств и клик. ^ Пусть V – некоторое непустое множество (  ). – множество всех его двухэлементных подмножеств,  – неупорядоченная пара элементов множества  .  .^ – пара множеств (V,E),  , где V – множество вершин графа G, E – множество рёбер графа G. ^ Смежные вершины графа G – вершины, соединенные ребром. Смежные ребра графа G – ребра, имеющие общую вершину. Инцидентные ребро и вершина – вершина является одним из концов ребра. Конечный граф – множество вершин графа конечно. ^
 , .
 , .Н  апример:Задан граф G=(V, E), где V={a, b, c, d}, E={ab, bc, ac, ad, dc}. Матрица смежности  Матрица инцидентности 
^ Степень вершины deg(v) графа G – число инцидентных ей ребер. Максимальная степень всех вершин графа G – (G):  .^ всех вершин графа G – (G):  .Лемма о рукопожатиях  Изолированная вершина графа G – вершина, степень которой равна 0. Висячая вершина графа G – вершина, степень которой равна 1. Доминирующая вершина графа G – вершина, степень которой равна p-1, где p – количество вершин графа G. ^ Полный граф – любые две вершины смежны или каждая вершина графа является доминирующей. Обозначается,  . Пустой граф – не имеет ребер. Обозначается через  .Псевдограф – граф, содержащий петли и кратные ребра. Мультиграф – граф, не содержащий петель, но с кратными ребрами. ^ – конечный граф без петель и кратных ребер. Далее, если особо не оговорено, рассматриваем только простые графы. Нуль-граф – граф без вершин и без ребер. Тривиальный граф – граф с одной вершиной, (1,0)-граф,  ,  .Однородный или регулярный граф – все вершины имеют равную степень.  Например: Двудольный граф (биграф) – множество вершин графа V можно разбить на два непересекающиеся подмножества  и  таких, что каждое ребро графа имеет одну концевую вершину в V1, а вторую – в V2, причем  , а  .^ – двудольный граф, у которого любые две вершины, входящие в разные доли  и  , смежны. Обозначается  , Звезда – полный двудольный граф  . Звезда K1,3 Полный двудольный граф K3,3 Двудольный граф Подграфы^ – граф, у которого каждой вершине поставлена в соответствие некоторая уникальная отметка (символ, цифра), иначе – абстрактный. Дополнение графа G – граф  , такой, что  , а  (вершины смежные в  несмежны в G и наоборот).Подграф  графа  – граф, у которого все вершины и ребра удовлетворяют следующим соотношениям  .Остовный подграф графа G - подграф, содержащий все вершины графа G, множество ребер есть подмножество ребер графа G. Порожденный подграф (порожденный подмножеством вершин ) – подграф, множество вершин которого  , а множество ребер  содержит все ребра графа G, инцидентные выбранным вершинам .Например:   Изоморфизм графов Изоморфные графы – существует взаимно однозначное соответствие между множествами их вершин или биекция, сохраняющая отношение смежности. Изоморфизм графов G и H: G H. Например: Заданы два графа  . Определить изоморфизм .  Решение: Граф  изоморфен графу  , потому что существует биекция  , сохраняющая отношение смежности. 
Например: следующие графы изоморфны друг другу.  
Граф  изоморфно вложим в граф  , если граф является изоморфным некоторому порожденному подграфу графа G.Например: граф изоморфно вложим в граф G. Например: граф  изоморфно вложим в  . |
Добавить документ в свой блог или на сайт
Похожие:
 | Методические указания к лабораторным работам по дисциплине: «Системы автоматизированного проектирования» для студентов автомеханического... | | Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». Численные методы.... |
| Методические указания к лабораторным работам по Геотехнике І для студентов специальности 050729 «Строительство» г. Алматы, Казгаса,... | | Методические указания к лабораторным работам по курсу рспсит для специальности 080801. 65-Прикладная информатика в экономике |
| Брякина, А. В. Институциональная экономика Методические указания по выполнению контрольной работы для студентов, обучающихся по направлению... | | Методические указания для выполнения лабораторных работ./ Санкт-Петербургский горный ин-т. Сост.: В. В беляев, Г. Н. Журов, Т. Р... |
| Методические указания к лабораторным работам по физике. Физика атомов и молекул / Владимирский государственный университет: Сост.:... | | Методические указания предназначены для выполнения контрольных работ студентами-заочниками специальности 1-70 02 01. Изложено содержание... |
| Методическое пособие содержит правила оформления лабораторных работ, а также теоретические сведения по основным разделам курса «Химия».... | | ... |