Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

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

Лекция



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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. Об этом говорит сайт https://intellect.icu . 4 Мультиграф с кратными ребрами (красные) и петлями (синие). Не все авторы разрешают мультиграфам иметь петли.

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

Формально, мультиграфом 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: Помеченный мультиорграф — помеченный орграф с кратными помеченными дугами, то есть дугами с теми же концами и теми же метками (заметьте, что это отличается от понятия, данного в статье «Разметка графа[»).

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

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

Из статьи мы узнали кратко, но содержательно про мультиграф
создано: 2015-01-07
обновлено: 2021-06-04
133151



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.