Мультиграф и псевдограф , базовый орграф кратко

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

В теории графов мультиграф ом (или псевдограф ом) называется граф, в котором разрешается присутствие кратных ребер (их также называют "параллельными"), то есть ребра, имеющие те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром. (Тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две.)

В некоторых задачах возникает необходимость рассматривать мультиграфы, в которых одна и та же пара вершин может соединяться более чем одним ребром, и псевдографы, в которых наряду с кратными ребрами допускаются петли - ребра, соединяющие вершину саму с собой. Конечный граф без петель называется мультиграфом. Он отличается от элементарного графа тем, что может содержать параллельные ребра. Наиболее общий случай графа, когда допускаются петли и параллельные ребра, называется псевдографом

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Граф с кратными ребрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Рис. 1. Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)

Рис. 2 Мультиграф

Рис. 3 Псевдограф

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

Неориентированные мультиграфы (ребра без собственной идентификации)

Формально, мультиграфом G называется упорядоченная пара G:=(V, E), в которой

• V — множество вершин,
• E — мультимножество неупорядоченных пар вершин. Элементы этого множества называются ребрами.

Неориентированный граф

Мультиграфы можно использовать для представления возможных воздушных путей самолета. В этом случае мультиграф становится ориентированным, и пара ориентированных параллельных ребер, связывающая города, показывает, что можно лететь в обоих направлениях — из города, или в город.

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

Ориентированные мультиграфы (ребра без собственной идентификации)

Мультиорграф — это ориентированный граф, в котором разрешены кратные дуги, то есть дуги, имеющие те же начальные и конечные вершины. МультиорграфомG называется упорядоченная пара G:=(V,A), в которой

• V — множество вершин,
• A — мультимножество упорядоченных пар вершин. Элементы этого множества называются дугами.

Смешанный мультиграф G:=(V,E, A) можно определить тем же образом, что и смешанный граф .

Ориентированные мультиграфы (ребра с собственной идентификацией)

Мультиорграфом (или колчаном^[en]) G называется упорядоченный четверка G:=(V, A, s, t), в которой

• V — множество вершин,
• A — множество дуг,
• назначает каждой дуге начальную вершину,
• назначает каждой дуге конечную вершину,.

В теории категорий небольшие категории могут быть определены как мультиорграфы (с дугами, имеющими собственную идентификацию), оснащенные законом построения и петлями для каждой вершины, служащими левой и правой идентификацией для построения. По этим причинам в теории категорий под термином графобычно понимается "мультиорграф" и лежащий в основе мультиорграф категории называется базовым орграфом.

Разметка

Мультиграфы и мультиорграфы поддерживают понятие разметки тем же образом. Однако в этом случае нет единства терминологии.

Определения помеченные мультиграфы и помеченные мультиорграфы похожи, так что мы здесь дадим определение только для мультиорграфа.

Определение 1: Помеченный мультиорграф — это помеченный граф с метками на дугах и вершинах.

Формально: Помеченный мультиорграф G — это кортеж из 8 элементов , в котором

• V — множество вершин и A — множество дуг
• и — конечный алфавит, доступный для разметки дуг и вершин,
• и — два отображения, определяющие начальную и конечную вершины дуги,
• и — два отображения, описывающие разметку вершин и дуг.

Определение 2: Помеченный мультиорграф — помеченный орграф с кратными помеченными дугами, то есть дугами с теми же концами и теми же метками (заметьте, что это отличается от понятия, данного в статье «Разметка графа^[»).

Вау!! 😲 Ты еще не читал? Это зря!

• Глоссарий теории графов
• Теория графов
• Лемма о рукопожатиях
• Матрица смежности графа
• Связь степени матрицы смежности и количества путей

Надеюсь, эта статья про мультиграф, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое мультиграф, псевдограф, базовый орграф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.