Алгоритм получения дерева из графа
Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).
Если i = k, то дерево построено.
Если i k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из выбранных.
Счетчик увеличивается на единицу.(i= i+1).
Переход на пункт 2.
Задание №1.
Найти Эйлерову цепь в неориентированном графе.
|
|
|
а) |
б) |
в) |
Задание №2. Для графа G=(V,E), с заданными мощностями |V|=n, |E|=m составьте матрицы смежности и инцидентности, определите локальные степени вершин, а также постройте его подграф. Является ли граф, соответствующий Вашему варианту эйлеровым, и почему?
Технология работы
Задание №1
Проверь возможность наличия Эйлеровой цепи, используя теорему Эйлера.
Указать Эйлеровую цепь.(при помощи вершин)
Задание №2
Построить граф (форма, вид графа выбирается на усмотрение студента).
Составить матрица инцидентности и смежности. Используя данные матрицы определить степени и полустепени вершин. По теоремы Эйлера определить является ли он Эйлеровым.
Задание №3
Для этого задания использовать алгоритм фронта волны. Обратить внимание на порядок применения пунктов алфовита.
Задание №4н
Определить цикломатическое число для графа. Поэтапно применить алгоритм построения дерева.
Контрольные вопросы: Что называется графом? ориентированным графом?
Что называется вершинами графа? ребрами?
Какие ребра и какие вершины графа называются смежными?
Какой граф называется мультиграфом?
Какой граф называется полным? дополнением?
Что называется петлей? цепью? циклом? путем в графе?
Какой граф называется деревом?
Что называется суммой графов? пересечением? композицией?
Что называется транзитивным замыканием графа? декартовым произведением графов?
Что называется степенью графа? Что называется полустепенями исхода и захода графа? Что такое цикломатическое число графа?
Что называется хроматическим числом графа?
C помощью каких матриц можно задать граф?
Какой граф называется эйлеровым?
Список рекомендуемой литературы
Дискретная математика: Учебное пособие / С.А. Канцедал. - М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2014. - 224 c.
Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. — М.: Издательский центр «Академия», 2013. — 368 с.
Практическая работа №4 Количество часов, отводимых на выполнение практической работы 2ч
Тема: Решение задач по теме «Машины Тьюринга»
Цель: наработка навыка конструирования машин Тьюринга и применения машин к словам.
Общие теоретические сведения:
Машина Тьюринга включает в себя: