Язык издания: русский
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Графы
Автор: Афанасьева Лилия Николаевна
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Графы
Автор: Афанасьева Лилия Николаевна
УПРАВЛЕНИЕ ОБРАЗОВАНИЯ И НАУКИ ЛИПЕЦКОЙ ОБЛАСТИГОАПОУ «Липецкий металлургический колледж» дляспециальности (группы специальностей):Липецк-2021Методические указания по выполнению практических работ по учебной дисциплине ОП 08 «Дискретная математика»Составитель : Афанасьева Л.Н., преподаватель математических дисциплинМетодические указания по проведению практических работ предназначены для студентов ГОАПОУ «Липецкий металлургический колледж» специальности 09.02.01 Компьютерные системы и комплексы для подготовки к практическим работам с целью освоения практических умений и навыков и профессиональных компетенций. Методические указания по проведению практических работ составлены в соответствии с рабочей программой учебной дисциплины « Дискретная математика» (дисциплина входит в математический и общий естественнонаучный учебный цикл учебного плана специальности 09.02.01 Компьютерные системы и комплексы по программе базовой подготовки). Введение Методические указания по проведению практических работ составлены в соответствии с содержанием рабочей программы учебной дисциплины « Дискретная математика» (дисциплина входит в математический и общий естественнонаучный учебный цикл учебного плана специальности 09.02.01 Компьютерные системы и комплексы по программе базовой подготовки). Практические работы направлены на освоение следующих практических умений и знаний согласно требованиям ФГОС СПО специальности 09.02.01 Компьютерные системы и комплексы, рабочей программы дисциплины « Дискретная математика».уметь: - определять типы графов и давать их характеристики- строить ориентированные и неориентированные графы - строить плоски графы- находить диаметр, радиус, центр графа- находить Изоморфные и Гамильтоновы циклызнать: - основные понятия теории графов, - характеристики и виды графов Методические указания по проведению практических работ содержат теоретическую часть, который кратко представляет основной материал, необходимый для освоения коммуникативных умений и знаний; практические задания; контрольные вопросы для самопроверки. Методические указания по проведению практических работ могут быть использованы студентами для самостоятельной работы, преподавателями на учебных занятиях по математике. Практические работы следует проводить по мере прохождения студентами теоретического материала. Методические указания к выполнению практической работы для студентов 1. К выполнению практической работы необходимо подготовиться до начала учебного занятия. 2. При подготовке к практической работе используйте рекомендованную литературу, предложенную в данных методических указаниях, конспекты лекций. 3. К выполнению работы допускаются студенты, освоившие необходимый теоретический материал. 4. Студенты обязаны иметь при себе линейку, карандаш, калькулятор, тетрадь. 5. По окончании выполнения практической работы проверьте себя, ответив на контрольные вопросы для самопроверки. 6. Если практическая работа не сдана в указанные сроки (до выполнения следующей практической работы) по неуважительной причине, оценка снижается.Практическая работа №12Цель практического занятия: Корректировать знания, умения и навыки по теме: «Способы задания неориентированные графов ». Закрепить и систематизировать знания по теме. Порядок выполнения работы: 1. Усвоить теоретический материал по теме «Неориентированные графы Способы задания неориентированных графов».2. Ответить на контрольные вопросы для самопроверки. 3. Выполнить и записать задания практической работы в тетрадь по математике. 4. Сдать выполненную практическую работу на проверку преподавателю.Теоретическая часть: Граф G - совокупность двух множеств: вершин V и ребер R, между которыми опре-делено отношение инцидентности. Если |V(G)|=n, |R(G)|=m, то граф G есть (n,m) граф, где n - порядок графа, m - размер графа. 2Каждое ребро r из R инцидентно ровно двум вершинам v', v'', которые оно соединя-ет. При этом вершина v' и ребро r называются инцидентными друг другу, а вершины v' и v'' называются смежными. Ребро (v,v) называется петлей (концевые вершины совпадают). Граф, не содержащий ориентированные ребра (дуги), называется неографом. Ребра, инцидентные одной паре вершин, называются параллельными или кратными. Пустой граф - множество ребер пусто (число вершин может быть произвольным). Полный граф - граф без петель и кратных ребер, каждая пара вершин соединена ребром. Локальная степень вершины - число ребер ей инцидентных. В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях). Петля дает вклад, равный 2 в степень вершины. В орграфе сумма входящих ребер всех вершин равна сумме исходящих ребер всех вершин и равна числу ребер графа. Графы равны, если множества вершин и инцидентных им ребер совпадают. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.Способы задания графов:− алгебраический− графический − матрица смежности− матрица инцидентности Матрица инцидентности: По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Если ребро - петля, то aij=2. Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. аij= число ребер, соединяющее вершины i,j.Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую вершину. Маршрут, в котором начало и конец совпадают - циклический. Маршрут в неографе, в котором все ребра разные - цепь. Вершины связанные, если существует маршрут из одной вершины в другую. Связанный граф - если все его вершины связаны. Плоский граф - граф с вершинами, расположенными на плоскости и непересекающимися ребрами. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными. Пример №1Задать неограф, представленный множеством вершин и ребер, графически и матри-цами, преобразовать граф в плоский, вычислить степени его вершин. V = {1; 2; 3; 4; 5; 6}; E = {a; b; c; d; e} E = {(1; 4); (2; 5); (2; 6); (3; 4); (3; 5)} Решение: Контрольные вопросы для самопроверки: Дайте определение неориентированного графа. Способы задания графа. Дайте определение плоскому, пустому, полному графу. Задание для выполнения практических работПрактическая работа №13Цель практического занятия: Корректировать знания, умения и навыки по теме: «Нахождение расстояния между вершинами в графе. Диаметр, радиус и центр графа. Проверка пары граф на изоморфизм». Закрепить и систематизировать знания по теме. Порядок выполнения работы: 1. Усвоить теоретический материал по теме «Нахождение расстояния между вершинами в графе. Диаметр, радиус и центр графа. Проверка пары граф на изоморфизм».2. Ответить на контрольные вопросы для самопроверки. 3. Выполнить и записать задания практической работы в тетрадь по математике. 4. Сдать выполненную практическую работу на проверку преподавателюТеоретическая часть:Расстояния в графе, диаметр, центр, радиус графаУтверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w. Это расстояние удовлетворяет аксиомам метрики:d(v, w) і 0, причем d(v, w) = 0 тогда и только тогда, когда v=w; d(v, w) = d(w, v); d(v, w) Ј d(v, u) + d(u, w). Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.Определение. Центром графа называется такая вершина, что максимальное расстояние между ней и любой другой вершиной является наименьшим из всех возможных; это расстояние называется радиусом графа.Пример№1.Для графа G, изображенного на рисунке 34, найти радиус, диаметр и центры.Решение.Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами dij которой будут расстояния между вершинами vi и vj. Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали. С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5. В результате получаем: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v2, v3, v4Эквивалентные или изоморфные графы2 графа считаются эквивалентными или изоморфными, если, во-первых, у них одинаковые числа вершин и рёбер (дуг), а во-вторых, соответствующие, т.е. имеющие одинаковые номера рёбра (дуги) соединяют соответствующие вершины.Принцип изоморфизма. Для того, чтобы показать, что 2 графаизоморфны, изоморфизм из одного в другой должен быть найден. Для того, чтобы показать, что 2 графа неизоморфны, должны быть найдены такие свойства графа, которыми обладает один граф, но не обладаетдругой.Пример№2Контрольные вопросы для самопроверки: Дайте определение изоморфизм графа. Дайте определение диаметр, центр и радиус графа . Задание для выполнения практических работПрактическая работа №14Цель практического занятия: Корректировать знания, умения и навыки по теме: «Эйлеровы графы. Гамильтоновы графы». Закрепить и систематизировать знания по теме. Порядок выполнения работы: 1. Усвоить теоретический материал по теме «Эйлеровы графы. Гамильтоновы графы»2. Ответить на контрольные вопросы для самопроверки. 3. Выполнить и записать задания практической работы в тетрадь по математике. 4. Сдать выполненную практическую работу на проверку преподавателю.Теоретическая часть:Эйлеровым циклом графа называется цикл, который содержит все ребра графа только один раз. Эйлеровым путем графа называется путь, который содержит все ребра графа только один раз.Граф, обладающий эйлером циклом, называется эйлеровым. Плоские эйлеровы графы можно изобразить «одним росчерком пера», причем процесс изображения начинается и заканчивается в одной вершине.Теорема: Граф G является эйлеровым тогда и только тогда, когда G- связный граф, имеющий все четные вершины.Методика нахождения эйлерова цикла в эйлеровомграфе1. Убедимся в том, что граф является эйлеровым (степенивсех вершин четны).2. Начиная с произвольной вершины, строим цепь, удаляярёбра и запоминая вершины, пока не придём в ту же вершину, скоторой начали.3. Берём следующую вершину и продолжаем процесс, покане будут удалены все рёбра.4. Объединяем полученные последовательности в одну. Пример №1Гамильтоновым путем графа называется путь , проходящий через каждую его вершину только один раз. Гамильтоновым циклом графа называется цикл , проходящий через каждую его вершину только один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым.Пример №2Найдите циклы в графе G РешениеДва цикла длины 5: 132541; 125431 Три цикла длины 4: 12541; 12341; 25432 Два цикла длины 3: 1231; 1341 Гамильтонов цикл: 12543 Контрольные вопросы для самопроверки: Дайте определение эйлерову и гамильтонову графу. Способы нахождения эйлерова цикла. Дайте определение гамильтонов цикл и путь. Задание для выполнения практических работВариант №1Существует ли Эйлеров цикл в графе, если существует, найди его? 2 . Найдите гамильтоновы циклы в графеВариант №2Существует ли Эйлеров цикл в графе. Если существует, найдите его? Найдите гамильтоновы циклы в графе ? Вариант №3Существует ли Эйлеров цикл в графе. Если существует, найдите его? 2 . Найдите гамильтоновы циклы в графеПрактическая работа №15Цель практического занятия: Корректировать знания, умения и навыки по теме: «Способы задания ориентированных графов». Закрепить и систематизировать знания по теме. Порядок выполнения работы: 1. Усвоить теоретический материал по теме «Способы задания ориентированных графов».2. Ответить на контрольные вопросы для самопроверки. 3. Выполнить и записать задания практической работы в тетрадь по математике. 4. Сдать выполненную практическую работу на проверку преподавателю.Теоретическая часть:Ориентированным графом (или орграфом) называетсяграф, в котором элементами множества рёбер являются упорядоченные пары.В орграфе элементы множества V – узлы, а элементы множества E – дуги.Полустепень исхода d-(v) – число дуг, исходящих из вершины v.Полустепень захода d+(v) – число дуг, исходящих в вершины v.Источник – вершина, полустепень захода которой равна нулю.Сток – вершина, полустепень исхода которой равна нулю.Маршрут в орграфе, в котором все дуги разные - путь. В орграфе сумма входящих ребер всех вершин равна сумме исходящих ребер всех вершин и равна числу ребер графа. Способы задания графов:− явное задание графа как алгебраической системы; − геометрический; − матрица смежности; − матрица инцидентностиМатрица инцидентности: ориентированного графа называется матрица, для которой aij=1, если вершина является началом дуги , aij= – 1, если является концом дуги , в остальных случаях aij=0. Матрица смежности ориентированного графа называется матрица, для которой aij=1, если вершина является началом дуги, в остальных случаях aij=0.Пример№1 Задать граф, представленный матрицей инцидентности, алгебраически, графически и матрицей смежности, преобразовать граф в плоский, вычислить степени его вершин. Контрольные вопросы для самопроверки: Дайте определение ориентированного графа. Способы задания графа. Дайте определение матрицы смежности и инцидентно Задание для выполнения практических работ
