Скачать 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 можно разбить на два непересекающиеся подмножества ![]() ![]() ![]() ![]() ^ – двудольный граф, у которого любые две вершины, входящие в разные доли ![]() ![]() ![]() ![]() Звезда – полный двудольный граф ![]() ![]() Звезда K1,3 Полный двудольный граф K3,3 Двудольный граф Подграфы^ – граф, у которого каждой вершине поставлена в соответствие некоторая уникальная отметка (символ, цифра), иначе – абстрактный. Дополнение графа G – граф ![]() ![]() ![]() ![]() Подграф ![]() ![]() ![]() Остовный подграф графа G - подграф, содержащий все вершины графа G, множество ребер есть подмножество ребер графа G. Порожденный подграф (порожденный подмножеством вершин ![]() ![]() ![]() ![]() Например: ![]() ![]() Изоморфизм графов Изоморфные графы – существует взаимно однозначное соответствие между множествами их вершин или биекция, сохраняющая отношение смежности. Изоморфизм графов G и H: G H. Например: Заданы два графа ![]() ![]() ![]() ![]() Решение: Граф ![]() ![]() ![]() ![]()
Например: следующие графы изоморфны друг другу. ![]() ![]()
Граф ![]() ![]() ![]() Например: граф ![]() ![]() Например: граф ![]() ![]() ![]() |
![]() | Методические указания к лабораторным работам по дисциплине: «Системы автоматизированного проектирования» для студентов автомеханического... | ![]() | Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». Численные методы.... |
![]() | Методические указания к лабораторным работам по Геотехнике І для студентов специальности 050729 «Строительство» г. Алматы, Казгаса,... | ![]() | Методические указания к лабораторным работам по курсу рспсит для специальности 080801. 65-Прикладная информатика в экономике |
![]() | Брякина, А. В. Институциональная экономика Методические указания по выполнению контрольной работы для студентов, обучающихся по направлению... | ![]() | Методические указания для выполнения лабораторных работ./ Санкт-Петербургский горный ин-т. Сост.: В. В беляев, Г. Н. Журов, Т. Р... |
![]() | Методические указания к лабораторным работам по физике. Физика атомов и молекул / Владимирский государственный университет: Сост.:... | ![]() | Методические указания предназначены для выполнения контрольных работ студентами-заочниками специальности 1-70 02 01. Изложено содержание... |
![]() | Методическое пособие содержит правила оформления лабораторных работ, а также теоретические сведения по основным разделам курса «Химия».... | ![]() | ... |