Виды графов. Тема 4.2

Контрольные вопросы
Виды графов: простой, полный, псевдограф, мультиграф.
Эйлеров и гамильтонов графы.
Методика проверки графа на эйлеровость.
Деревья и их свойства.
Кодирование Пруффера для деревьев с пронумерованными вершинами

Неориентированный граф называется простым, если он не
имеет петель и любая пара вершин соединена не более чем
одним ребром.
Простой граф называется полным, если каждая пара вершин
соединена ребром
Простой граф
Полный граф
Виды графов

Псевдограф и мультиграф
Граф называется псевдографом, если в нем допускаются петли и кратные ребра, т.е. две вершины могут быть соединены более чем одним ребром.
Псевдограф без петель называется мультиграфом.

Путь, цепь, цикл
Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза.
Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью.
Приведите примеры цепи и цикла.

Эйлеровы графы
Бывший Кенигсберг, ныне Калининград, расположен на реке Прегель. А пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход, он начертил упрощённую схему мостов. Получился граф, вершины которого – части города, разделённые рекой, а рёбра – мосты.
В итоге он доказал общее утверждение: для того, чтобы можно было обойти всё рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнение двух условий:
Из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным);
Из каждой вершины должно выходить чётное количество рёбер.

Методика нахождения эйлерова цикла в эйлеровом графе

ПРИМЕР

Гамильтоновы графы
амильто́нов граф — граф, содержащий гамильтонов цикл[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа.
Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз[1]. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз[3]. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра[4].
Гамильто́нов граф — граф, содержащий гамильтонов цикл.
При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.
Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.

Гамильтоновы графы
амильто́нов граф — граф, содержащий гамильтонов цикл[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа.
Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз[1]. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз[3]. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра[4].
В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги.

Классификация компьютеров
Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Чемпион
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Укажите перечисленные объекты у дерева
Корень – главная вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.
Олимпийская система спортивных соревнований

Файловая структура
Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней

Самое главное
Граф - наглядное средство представления состава и структуры системы. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная – ребром.
Иерархия - расположение частей (элементов) целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях подчиненности, называются иерархическими системами.
Дерево - граф иерархической системы. Между любыми двумя вершинами дерева существует единственный путь.

Деревья и их свойства
Деревья являются простым, но очень важным видом графа. С их помощью описывается структура самых различных объектов: организации и учреждения, книг и документов, математических формул, компьютерных файловых систем, программ…
v11

Листом (висячей вершиной) называют вершину степень которой равна 1, если она не рассматривается как корень. В качестве корня в неориентированном дереве можно принять любую вершину
Основные свойства деревьев:
дерево – это связный граф без циклов
любая пара вершин в дереве связана единственной цепью
дерево – это связный граф, имеющий n-вершин и n-1 ребер
Естественным понятием расширения дерева является лес – несвязный граф, все компоненты которого деревья

Кодирование Пруффера для деревьев с пронумерованными вершинами
Каждое дерево может быть однозначно записано числовым кодом, содержащим n-2 элемента и называемым кодом Пруффера
Алгоритм получения кода
Пусть вершины дерева пронумерованы числами от 1 до n. Отыскиваем вершины степени 1 с наименьшим номером и включаем в ход номер смежный с ней вершиной, после чего удаляем найденную вершину вместе с ребром.
С получившимся подграфом выполняем ту же операцию повторяя её, пока только останется два ребра

пример:
3
2
7
6
5
1
4
3
4
1
7
6
5
Код - 1
Код - 4
4
1
7
6
5
Код - 1
1
7
6
5
Код - 6
7
6
5
Код - 6
14166

Восстановление дерева по коду
Антикод – упорядоченное по возрастанию последовательность номеров вершин не вошедших в код Пруффера
Для примера 2, 3, 5, 7
Дерево строится путем добавления ребер. Очередное добавляемое ребро начиная с первого образуется парой вершин номера которых стоят 1 в строке кода и в строке антикода. После этого использованные элементы строк вычеркиваются. Если номер вычеркнутый из строки кода не содержится среди оставшихся в ней элементов его следует добавить в строке антикода не нарушая её упорядоченность. Такие же действия повторяются с остатками строк кода и антикода. Пока они будут вычеркнуты все элементы первой из них

При этом строка антикода будет содержать 2 элемента образующих последнее ребро, которое следует добавить к формируемому дереву

Домашнее задание
1. Определите является ли граф эйлеровым?