Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки




НазваниеМетодические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки
страница1/9
Дата публикации28.07.2013
Размер0.5 Mb.
ТипМетодические указания
zadocs.ru > Астрономия > Методические указания
  1   2   3   4   5   6   7   8   9



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

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

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




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


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

по курсу “ОДМ часть 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 – ребра, имеющие общую вершину.

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

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

^

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


  1. Явное перечисление множеств вершин V и ребер E.

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

  3. Матричные способы описания.

  1. Матрица смежности

,

.

  1. Матрица инцидентности

,

.
Например:
Задан граф G=(V, E), где

V={a, b, c, d},

E={ab, bc, ac, ad, dc}.

Матрица смежности Матрица инцидентности





ab

bc

ac

ad

dc

a

1

0

1

1

0

b

1

1

0

0

0

c

0

1

1

0

1

d

0

0

0

1

1








a

b

c

d

a

0

1

1

1

b

1

0

1

0

c

1

1

0

1

d

1

0

1

0




^ Степени вершин графа

Степень вершины deg(v) графа G – число инцидентных ей ребер.

Максимальная степень всех вершин графа G – (G):

.

^ Минимальная степень всех вершин графа G – (G):

.
Лемма о рукопожатиях

frame3
Изолированная вершина графа 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.

Например:

Заданы два графа . Определить изоморфизм .





Решение:

Граф изоморфен графу , потому что существует биекция , сохраняющая отношение смежности.

frame7



a

b

c

d



2

1

4

3


Например: следующие графы изоморфны друг другу.


frame8



1

2

3

4

5

6



1

3

5

2

4

6


Граф изоморфно вложим в граф , если граф является изоморфным некоторому порожденному подграфу графа G.
Например: граф изоморфно вложим в граф G.



Например: граф изоморфно вложим в .

  1   2   3   4   5   6   7   8   9

Добавить документ в свой блог или на сайт

Похожие:

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным работам по дисциплине «Системы...
Методические указания к лабораторным работам по дисциплине: «Системы автоматизированного проектирования» для студентов автомеханического...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным и самостоятельным работам по...
Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». Численные методы....

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным работам по Геотехнике І для...
Методические указания к лабораторным работам по Геотехнике І для студентов специальности 050729 «Строительство» г. Алматы, Казгаса,...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным работам по курсу рспсит для...
Методические указания к лабораторным работам по курсу рспсит для специальности 080801. 65-Прикладная информатика в экономике

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания по выполнению контрольной работы Для студентов, обучающихся по направлению
Брякина, А. В. Институциональная экономика Методические указания по выполнению контрольной работы для студентов, обучающихся по направлению...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным работам для студентов специальностей...
Методические указания для выполнения лабораторных работ./ Санкт-Петербургский горный ин-т. Сост.: В. В беляев, Г. Н. Журов, Т. Р...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания к лабораторным работам по физике физика атомов и молекул, ядерная физика
Методические указания к лабораторным работам по физике. Физика атомов и молекул / Владимирский государственный университет: Сост.:...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconМетодические указания и задания по выполнению контрольной работы...
Методические указания предназначены для выполнения контрольных работ студентами-заочниками специальности 1-70 02 01. Изложено содержание...

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconРоссийской Федерации Тверской государственный технический университет...
Методическое пособие содержит правила оформления лабораторных работ, а также теоретические сведения по основным разделам курса «Химия»....

Методические указания и задания к лабораторным работам по курсу “одм часть 2 “ для студентов, обучающихся по направлению подготовки iconСанкт-петербургский государственный университет кино и телевидения
...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов