metod_15.03.04_atppp_moas_tg_2016 (1016591), страница 2
Текст из файла (страница 2)
Для любого графа матрица смежности симметрична относительно главной диагонали.3. СВЯЗНОСТЬ, ПУТИ, ЦИКЛЫ В ГРАФАХГраф (орграф) называется связным (сильно связным), если для любыхдвух его вершин vi и vj существует путь из вершины vi в вершину vj.Орграф называется односторонне связным, если для любых двух еговершин, по крайней мере, одна достижима из другой.Псевдограф отличается от графа тем, что в нем, как и в мультиграфе, допускаются кратные ребра и, кроме того, допускаются петли, причем возможнодаже несколько петель при одной вершине.10Псевдографом, ассоциированным с ориентированным псевдографом,называется псевдограф, получающийся из ориентированного псевдографа,путем замены направленных дуг на дуги без стрелок.Орграф, не являющийся сильно связным, называется слабо связным,если связным является ассоциированный с ним граф.Граф (орграф), не являющийся связным (слабо связным), называетсянесвязным.Компонентой связности (сильной связности) графа (орграфа) называется связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа (орграфа).Пусть G – псевдограф.
Тогда цикл (цепь) в G называется эйлеровым(эйлеровой), если он (она) проходит по одному разу через каждую дугу G , апсевдограф, содержащий эйлеров цикл, называется эйлеровым.Примером эйлерова графа являются так называемые сабли Магомета.Рисунок 3.1 – Пример эйлерова графа (сабли Магомета).Как граф с эйлеровым циклом можно рассматривать, например, разумную схему обхода выставки так, чтобы увидеть каждый экспонат по одномуразу.Теорема (критерий эйлеровости графа). Для того чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы степени всех еговершин были четными числами.11Необходимость очевидна, так как двигаясь по эйлерову циклу, войдя ввершину по одной дуге, мы выходим из нее по другой дуге, то есть каждойдуге «входа» соответствует дуга «выхода».
Каждая такая пара дуг дает вклад,равный двум, в степень вершины, а поскольку эйлеров цикл содержит все дуги, то степень каждой вершины представлена суммой двоек, и значит четна.На рисунке 3.2. графы G1и G2являются эйлеровыми, а G3и G4 – нет.Рисунок 3.2 – Эйлеровы и неэйлеровы графы.Теорема. Пусть G – конечный связный орграф. Для того, чтобы существовал ориентированный цикл в G, содержащий все дуги (эйлеров цикл),необходимо и достаточно, чтобы в каждой вершине орграфа число входящихи выходящих дуг было одинаково.На рисунке 3.3 изображен орграф для которого выполняются условияэтой теоремы.Рисунок 3.3 – Пример эйлеровойцепи.12Связный граф называется квазиэйлеровым, если на нем существует эйлерова цепь.Теорема (критерий квазиэйлеровости). Для того чтобы конечный связный граф был квазиэйлеровым, необходимо и достаточно, чтобы степенивсех его вершин были четными числами или степени всех его вершин, за исключением ровно двух, были четными числами, причем в первом случае эйлерова цепь является эйлеровым циклом, а во втором случае эйлерова цепьначинается в одной из вершин нечетной степени, а заканчивается в другойвершине нечетной степени.Данная теорема является следствием предыдущей.
Случай двухвершин нечетной степени и построение эйлеровой цепи можно свести кэйлерову циклу на графе, полученному из данного добавлением дуги,соединяющей две вершины нечетной степениНа рисунке 3.2 связные графы G3 и G4- квазиэйлеровы, так как ониимеют эйлеровы цепи (у них ровно по две вершины нечетной степени).
Ранееотмечалось, что эти графы не имеют эйлеровых циклов.Цикл (цепь) в псевдографе называется гамильтоновым (гамильтоновой), если он (она) проходит через каждую вершину псевдографа ровноодинраз.Длина любой гамильтоновой цепи равна (n-1), а длина любого гамильтонового цикла равна n(число вершин псевдографа).С понятием гамильтоновых циклов связана так называемая задача окоммивояжере: в нагруженном (взвешенном) графе надо определить гамильтонов цикл минимальной длины.Иными словами, коммерсант должен совершить поездку по городам ивернуться обратно, побывав в каждом городе ровно один раз, и при этом стоимость поездки должна быть минимальной.Задача о коммивояжере имеет ряд приложений в исследовании операций, например в вопросах о наиболее эффективном использовании подвижного состава или оборудования.
Задача может быть решена перебором, а в13общем случае никакого эффективного алгоритма решения нет. Имеются некоторые частные схемы для отдельных случаев.Критерия для существования гамильтоновых циклов не известно. Болеетого, иногда даже для конкретных графов бывает трудно решить, можно линайти такой цикл.В полном графе всегда существует гамильтонов цикл, а также гамильтоновы цепи, соединяющие две произвольные вершины этого графа.Таким образом, простейшим достаточным условием существованиягамильтоновых цепей и циклов в графе является его полнота.Необходимым условием существования гамильтоновых цепей и цикловявляется связность графа.4.
ИЗОМОРФИЗМ ГРАФОВИзоморфизм графов –это отношение эквивалентности на множествеграфов. Изоморфным отображением одного неориентированного графа надругой называется взаимно однозначное отображение вершин и ребер одногографа соответственно на вершиныи ребра другого графа, при котором сохраняется отношение инцидентности. Два графа называются изоморфными, еслисуществует изоморфное отображение одного из этих графов на другой.
Графы G1 и G2, представленные на рисунке 3.1, не изоморфны, a G1 и G3 изоморфны.14Рисунок 3.1 – Изоморфизм графов.Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. Подобным образом можно определить изоморфизм ориентированных графов исетей.Проблема установления изоморфизма графов является важной проблемой теории графов. Для некоторых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно.Из определения следует, что изоморфные графы можно одинаковоизображать графически и отличаться они будут только метками вершин.Изоморфизм графов есть отношение эквивалентности.На рисунке 3.2 изображены три изоморфных графа.
На рисунке 3.3изображены два неизоморфных графа.Рисунок 3.2 – Изоморфные графы.Рисунок 3.3 – Неизоморфные графы.15Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.С точностью до изоморфизма существует ровно четыре простых графас тремя вершинами и одиннадцать с четырьмя вершинами. Постройте этиграфы.Рисунок 3.4 – Все изоморфные графы с тремя вершинами.Рисунок 3.5 – Все изоморфные графы с четырьмя вершинами.5. ОБЗОР ЗАДАЧ ТЕОРИИ ГРАФОВРазвитие теории графов в основном обязано большому числу всевозможных приложений.
По-видимому, из всех математических объектов графызанимают одно из первых мест в качестве формальных моделей реальных систем.Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые16модели используются при исследовании коммуникационных сетей, системинформатики, химических и генетических структур, электрических цепей идругих систем сетевой структуры.Далее перечислим некоторые типовые задачи теории графов и их приложения.Задача о кратчайшей цепи:* замена оборудования,* составление расписания движения транспортных средств,* размещение пунктов скорой помощи,* размещение телефонных станцийЗадача о максимальном потоке:* анализ пропускной способности коммуникационной сети,* организация движения в динамической сети,* оптимальный подбор интенсивностей выполнения работ,* синтез двухполюсной сети с заданной структурнойнадежностью,* задача о распределении работ.Задача об упаковках и покрытиях:* оптимизация структуры ПЗУ,* размещение диспетчерских пунктов городской транспортной сети.Раскраска в графах:* распределение памяти в компьютере,* проектирование сетей телевизионного вещания.Связность графов и сетей:* проектирование кратчайшей коммуникационной сети,* синтез структурно-надежной сети циркуляционной связи,* анализ надежности стохастических сетей связи.Изоморфизм графов и сетей:* структурный синтез линейных избирательных цепей,17* автоматизация контроля при проектировании.Изоморфное вхождение и пересечение графов:* локализация неисправности с помощью алгоритмов поиска,* покрытие схемы заданным набором типовых подсхем.Автоморфизм графов:* конструктивное перечисление структурных изомеров дляпроизводных органических соединений,* синтез тестов цифровых устройств.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
