Вы, вероятно, имеете представление о компьютерных сетях. Возможно, компьютеры в школьном кабинете информатики объединены в локальную сеть или вы работали в Интернете, или пользовались услугами электронной почты. Понятно, что сеть образуется только тогда, когда компьютеры каким-либо образом соединены между собой каналами передачи данных. Размещение абонентов сети (подключённых к ней компьютеров или других систем автоматической обработки данных) и способ их соединения друг с другом называется конфигурацией сети. Продемонстрировать различные типы конфигураций вычислительных сетей можно, например, с помощью таких информационных моделей, как графы. Граф -- совокупность точек, соединённых между собой линиями. Точки называют вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или рёбрами (если направленность двусторонняя, то есть направления равноправны). Две вершины, соединенные ребром (дугой) называются смежными. Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.
Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины какими рёбрами (дугами) соединены и, возможно, указаны веса вершин и рёбер (дуг). Определение всех этих элементов и составляет суть формализации в этом случае.
Пример
На рис.3 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:
* шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К) информация от абонента-источника распространяется по каналу в обе стороны;
* кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;
* звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;
* древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;
* полносвязная конфигурация обеспечивает выбор наиболее быстрого маршрута связи между абонентами и удобна там, где управление оказывается достаточно сложным.
Рис.3
Наиболее наглядно граф задаётся рисунком. Однако не все детали рисунка одинаково важны. В частности, несущественны геометрические свойства рёбер (длина, кривизна и так далее), форма вершин (точка, кружок, квадрат, овал и пр.) и взаимное расположение вершин на плоскости. Так, на рис.4 представлены два изображения одного и того же графа. Все вершины и ребра часто задаётся в виде сопровождающей надписи на вершине или линии, но, введя условные обозначения, их можно задать формой или цветом вершины, толщиной, типом или цветом линии и т. п.
Рис. 4
Информационную модель в форме графа можно использовать для наглядного представления взаимосвязей, существующих между элементами объекта моделирования. Таким образом, граф -- наиболее удобная форма для моделирования структуры объекта, хотя в такой форме можно моделировать и внешний вид, и поведение объекта.
Пример
На рис.5 представлены модели молекул бутана и изобутана, каждая из которых имеет формулу С4Н10, то есть состоит из 4 атомов углерода и 10 атомов водорода. Имея одну и ту же формулу, бутан и изобутан имеют различные химические свойства, так как способы соединения атомов (структура молекул) различны. Расположение атомов в молекуле при различных способах их соединения хорошо представимо графом.
Рис.5
Заметим, что в химии для обозначения таких веществ часто используются и структурные формулы. Порядок соединения атомов изображается в структурной формуле чёрточками (связь между водородом и остальными атомами обычно не указывается). Подумайте сами, можно ли считать структурную формулу одной из разновидностей графа. В форме графа удобно отображать взаимосвязи понятий, относящихся к одной области деятельности или познания.
Пример
Рассмотрите граф понятий темы «Четырёхугольники» из курса геометрии (рис.6). Не правда ли, хорошая «шпаргалка»?
Рис.6.
В практической деятельности модели в форме графов часто используются для представления видов и порядка выполнения работ. Возможно, вам знакомы такие термины, как «сетевой график работ», «сетевой график строительства». Часто наряду со словесным или табличным описанием сетевые графики сопровождаются и изображением в виде графа, вершинами которого являются конкретные виды работ, а дугами задаётся возможный порядок их выполнения.
Пример
Сетевые графики строительства хорошо демонстрируют, какие работы могут выполняться одновременно, а какие требуют обязательного завершения предыдущих этапов. Анализируя такие графы, можно рассчитать время, необходимое для завершения всей работы, спланировать, сколько, когда и на какие работы направить специалистов и технику, определить наиболее «узкие» участки и уделить им особое внимание.
Для машинной обработки более удобным является символическое представление графов в виде списка рёбер с указанием, какие вершины это ребро соединяет, а также табличное представление, где строки и столбцы -- названия вершин, а значения ячеек указывают на то, соединены данные вершины или нет.
Пример
Графы, представленные на рис.7 могут быть описаны, например, следующими способами. Символическая запись: а(1,2) b(l,4) c(2,4) d(3,5) e(4,5) ,(3,4)
Табличная запись:
Рис.7.
Представление данных в форме дерева
Особым видом графа является дерево. Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности.
Пример
Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде дерева.
Пример
Вам хорошо известно понятие «родословное дерево» и вы можете изобразить в такой форме ваши родственные отношения.
Пример
Каталог файлов на диске, также как и библиотечный каталог -- примеры информационных моделей в форме дерева. Дерево -- это граф, предназначенный для отображения таких связей между объектами, как вложенность, подчиненность, наследование и т. п.
Строится он следующим образом
Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной 1-го уровня. Далее добавляем вершины 2-го уровня. Их может быть сколько угодно, и все они обязательно связаны с корнем -- вершиной 1-го уровня, но не связаны между собой. На следующем шаге добавим вершины 3-го уровня. Каждая из них будет связана ровно с одной вершиной 2-го уровня (больше ни с одной другой вершиной). К любой вершине 2-го уровня может быть подсоединено сколько угодно вершин 3-го уровня (в том числе, ни одной). Следующий шаг -- добавка вершин 4-го уровня, каждая из которых будет связана ровно с одной вершиной 3-го уровня (и не связана больше ни с чем). И так далее. На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей. Полученный граф напоминает ветвящийся куст, который «растет сверху вниз»: верхние уровни имеют меньшие номера, нижние -- большие. Вообще говоря, дерево может быть и неориентированным графом, но чаще дерево ориентировано, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин, а нижние вершины -- потомками соответствующей верхней вершины. На любом дереве существует единственная вершина, не имеющая предка, -- корень -- и может быть сколько угодно вершин, не имеющих потомков, -- листьев. Все остальные вершины имеют ровно одного предка и сколько угодно потомков. Если не принимать во внимание направленность связей, то в дереве из любой вершины можно по линиям дойти до любой другой вершины, причем по одному единственному пути. В виде дерева удобно изображать системы, в которых нижние вершины в каком-то смысле «подчинены» верхним. Верхняя вершина может изображать начальника, нижние -- подчиненных; верхняя -- систему, нижние -- ее компоненты; верхняя -- множество объектов, нижние -- входящие в него подмножества; верхняя вершина -- предка, нижние -- потомков и т. д. Формализация в случае построения дерева (иерархического графа) сводится к выявлению основного (главного, центрального) элемента рассматриваемого объекта (вершина нулевого уровня, которую часто называют корнем), элементов, которые находятся в непосредственном подчинении от основного (вершины 1-го уровня). Затем определяются вершины, находящиеся в непосредственном «подчинении» от вершин 1-го уровня (вершины 2-го уровня) и так далее. Изображать построенное дерево отношений можно в любом направлении -- это уже дело эстетического вкуса разработчика модели. В научной и учебной деятельности с помощью деревьев часто представляют классификацию изучаемых объектов.
Классифицирование -- распределение объектов по классам в зависимости от их общих признаков, фиксирующее закономерные связи между классами объектов в единой системе данной отрасли знания.
Классификация (от лат. classis -- разряд + facere -- делать) -- система соподчиненных понятий (классов объектов, явлений) в какой-либо отрасли знания, составленная на основе учёта общих признаков объектов и закономерных связей между ними.
Классификация позволяет ориентироваться в многообразии объектов и является источником знания о них. Очень важен выбор основания классификации -- то есть признака, на основании которого объекты разбиваются на классы. Выбор разных оснований приводит к разным классификациям.
Пример
На рис.8 вы видите классификацию, предложенную Григорием Великим, которая призвана была показать, что человек имеет что-то общее со всеми видами существующих в мире вещей, и поэтому его справедливо называют «вселенной в миниатюре». Обратите внимание, что объекты здесь разбиваются всегда на два класса. Такая классификация носит название дихотомической.
Рис.8.
Пример
Представленная на рис.9 классификация принтеров построена с использованием различных оснований деления
Рис.9
Пример
Важным видом исторических классификаций является построение родословных или генеалогических деревьев. Они бывают самого разного вида: с указанием только прямых потомков (рис.10); с включением жён (мужей) и их родственников и др.
Рис.10 Родословное дерево великих и удельных князей Владимирских и Московских, XIII--XIV века (фрагмент)
В скобках приведены известные даты жизни; крест указывает на год смерти; двойным контуром обведены имена князей, занимавших московский престол. Рассмотренные выше реляционная (табличная), сетевая (графовая) и иерархическая (древовидная) модели являются основными для представления данных в базах данных, а программные комплексы, которые позволяют создавать, обновлять, сохранять базы данных и обслуживать запросы пользователей к ним, называются соответственно реляционной, сетевой, иерархической системами управления базами данных (СУБД). При описании сложных объектов, как правило, используется комбинация различных моделей данных.
Перед тем как начать изучение непосредственно алгоритмов, необходимо обладать базовыми знаниями касательно самих графов, понимать, как они представляются в компьютере. Здесь не будут подробно описаны все аспекты теории графов (этого и не требуется), но только те, незнание которых заметно усложнит усвоение данной области программирования.
Несколько примеров дадут немного поверхностного представления о графе. Так типичным графом является схема метро или какой-либо другой маршрут. В частности программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные серверы, а линии – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами (узлами ), а линии – ребрами (дугами ). Таким образом, граф – это совокупность вершин, соединённых ребрами.
Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее.
Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке ниже в качестве примера показана полносвязная топология.
Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.
Вот некоторые важные обозначения, используемые в теории графов:
- G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
- |V| – порядок (число вершин);
- |E| – размер графа (число рёбер).
В нашем случае (рис. 1) |V|=5, |E|=10;
Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).
В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.
В орграфе, в отличие от неориентированного графа, имеется возможность двигаться из вершины h в вершину s без промежуточных вершин, лишь тогда когда ребро выходит из h и входит в s, но не наоборот.
Ориентированные графы имеют следующую форму записи:
G=(V, A), где V – вершины, A – направленные ребра.
Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.
В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].
Два или более графов на первый взгляд могут показаться разными по своей структуре, что возникает вследствие различного их изображения. Но это не всегда так. Возьмем два графа (рис. 4).
Они эквивалентны друг другу, ведь не изменяя структуру одного графа можно построить другой. Такие графы называются изоморфными , т. е. обладающими тем свойством, что какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. На рисунке 4 изображены два изоморфных графа.
Когда каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра, тогда такой граф взвешенный . В разных задачах в качестве веса могут выступать различные виды измерений, например длины, цены маршруты и т. п. В графическом представлении графа весовые значения указываются, как правило, рядом с ребрами.
В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.
Определения
Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения - наиболее часто встречаемые.
Граф
Граф или неориентированный граф G - это упорядоченная пара G : = (V ,E )
- V это множество вершин или узлов ,
- E это множество пар (в случае неориентированного графа - неупорядоченных) различных вершин, называемых рёбрами .
V (а значит и E ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов . Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | - порядком , число рёбер | E | - размером графа.
Вершины u и v называются концевыми вершинами (или просто концами ) ребра e = {u ,v } . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними .
Два ребра называются смежными , если они имеют общую концевую вершину.
Два ребра называются кратными , если множества их концевых вершин совпадают.
Ребро называется петлёй , если его концы совпадают, то есть e = {v ,v } .
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной
, если она не является концом ни для одного ребра; висячей
(или листом
), если она является концом ровно одного ребра.
Ориентированный граф
Ориентированный граф (сокращённо орграф ) G - это упорядоченная пара G : = (V ,A ) , для которой выполнены следующие условия:
- V это множество вершин или узлов ,
- A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами .
Дуга - это упорядоченная пара вершин (v, w) , где вершину v называют началом, а w - концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w .
Смешанный граф
Смешанный граф G - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G : = (V ,E ,A ) , где V , E и A определены так же, как выше.
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Прочие связанные определения
Путём (или цепью ) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём
в орграфе называют конечную последовательность вершин v
i
, для которой все пары (v
i
,v
i
+ 1)
являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер . Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u ,v ,u ) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым , если ребра в нём не повторяются; элементарным , если он простой и вершины в нём не повторяются. Несложно видеть, что:
- Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
- Всякий простой неэлементарный путь содержит элементарный цикл .
- Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
Более абстрактно, граф можно задать как тройку , где V и E - некоторые множества (вершин и рёбер , соотв.), а - функция инцидентности (или инцидентор ), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов ). Частными случаями этого понятия являются:
Под данное выше определение не подходят некоторые другие обобщения:
- гиперграф - если ребро может соединять более двух вершин .
- ультраграф - если между элементами x i и u j существуют бинарные отношения инцидентности .
Литература
- Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
- Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
- Харари Ф. Теория графов. М.: Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
- Кормен Т. М.и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1
- Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. - М.: Физико-математическая литература, 1997. - ISBN 5-02-015033-9
- Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
- Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. - 168 c.
Сформулировано понятие «граф» и сети. Выделены его составные части: вершины и ребра. (Слайд 3)
Граф - это набор узлов (вершин) и связей между ними (ребер).
Сеть – граф, в котором вершины связаны между собой по принципу «многие ко многим»
Как представить информацию о графе в памяти компьютера? Хранить ее в виде рисунка (растрового или векторного) неэффективно, потому что рисунок предназначен для восприятия человеком, а не компьютером. Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B ; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности. На рисунке показаны схема дорог, соответствующий ей граф и его матрица смежности: (слайд 4)
Единица на главной диагонали (выделенной серым
цветом) показывает, что в графе есть петля
-ребро,
которое начинается и заканчивается в одной и той
же вершине.
Обратите внимание, что матрица смежности
симметрична относительно главной диагонали, то
есть если существует ребро из вершины A
в
вершину B
, то существует и ребро из B
в
A
. Такой граф называют неориентированным
- ребра не имеют направления и каждое из них
учтено в матрице смежности дважды. Матрица
смежности не дает никакой информации о том, как
именно расположены узлы друг относительно друга.
Для таблицы, приведенной выше, возможны,
например, такие варианты, как на рисунках. (слайд
5)
Если для каждого ребра указано направление, граф называют ориентированным (или орграфом). Ребра орграфа называют дугами. Его матрица смежности не всегда симметричная. Единица, стоящая на пересечении строки A и столбца B, говорит о том, что существует дуга из вершины A в вершину B: (слайд 6).
Часто с каждым ребром связывают некоторое число - вес ребра. Это может быть, например, расстояние между городами или стоимость проезда. Такой граф называется взвешенным. Информация о таком графе хранится в виде весовой матрицы, содержащей веса ребер: (слайд 7).
У взвешенного орграфа весовая матрица не всегда симметрична относительно главной диагонали: (слайд 8).
Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти компьютера записывать в нее условный код, например, 0, –1 или очень большое число (?), в зависимости от задачи.
Другим примером ориентированного графа являются блок-схемы алгоритмов. (слайд 9) Блок-схема алгоритма представляет собой граф процесса управления некоторым исполнителем. Блоки – вершины этого графа – обозначают отдельные команды, которые отдаются исполнителю, а дуги указывают на последовательность переходов от одной команды к другой.
Учебный проект: Его высочество граф математический/
Виды графов
Плоские графы
Граф называется плоским (планарным)
, если его можно уложить на плоскости так, чтобы его ребра нигде не пересекались, кроме как в вершинах. Имеется два основных непланарных графа - Г5 и Г3,3, изображение которых дано на рисунке. Оба графа Г5 и Г3,3 являются регулярными
, но последний относится еще и к так называемому двудольному
, который определяется здесь как многозначное отображение трех верхних вершин на три нижние вершины, или наоборот. В общем случае в двудольном графе Г3,3 число вершин в обоих рядах может быть любым.
Двудольный граф
Двудольный граф (или биграф, или чётный граф)
- это граф G(V,E), такой что множество вершин V разбито на два непересекающихся подмножества V1 и V2, причём всякое ребро E инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). То есть, правильная раскраска графа двумя цветами. Множества V1 и V2 называются «долями»
двудольного графа. Двудольный граф называется «полным»
, если любые две вершины из V1 и V2 являются смежными
. Если |V1|=a,|V2|=b , то полный двудольный граф обозначается Ka,b.
Изоморфный граф
Изоморфизм
- это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: Пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.). Биекция между ними называется изоморфизмом, если она сохраняет эту структуру. Такие множества со структурой называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких множеств со структурой.
Два графа G=(X,U) и L=(X",U") являются изоморфными
, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Пример: следующие графы, приведенные на рисунке, изоморфны:
Псевдограф
Псевдограф
– граф с кратными ребрами и петлями.
Пример: пусть D=(V,X) – ориентированный граф, V={V1,V2},X={x1={V1,V2},x2={V1,V2],x3={V1,V2},x4={V2,V2} .
Тогда D=(V,X) – ориентированный псевдограф
Мультиграф
Мультиграф
– граф, в котором имеются кратные (параллельные) ребра.
Мультиграф
– это псевдограф без петель.
Пример: пусть D=(V,X) – ориентированный граф,V={V1,V2} ,X={x1={V1,V2},x2={V1,V2}} . Тогда D=(V,X)– ориентированный мультиграф.