В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»[1]), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Существует два различных способа обозначения рёбер мультиграфа. Некоторые говорят, что, как и в случае графов без кратных рёбер, ребро определяется вершинами, которые оно соединяет, но каждое ребро может повторяться несколько раз. Другие определяют рёбра равноправными с вершинами элементами графа и они должны иметь собственную идентификацию.
Формально, мультиграфом G называется упорядоченная пара G:=(V, E), в которой
Мультиграфы можно использовать для представления возможных воздушных путей самолёта. В этом случае мультиграф становится ориентированным и пара ориентированных параллельных рёбер, связывающая города, показывает, что можно лететь в обоих направлениях — из города или в город.
Некоторые авторы позволяют мультиграфам иметь петли, то есть рёбра, соединяющие вершину с ней же[2], в то время как другие называют такие графы псевдографами, оставляя термин мультиграф для графов без петель[3].
Мультиорграф — это ориентированный граф, в котором разрешены кратные дуги, то есть дуги, имеющие те же начальные и конечные вершины.
Мультиорграфом G называется упорядоченная пара G:=(V,A), в которой
Смешанный мультиграф G:=(V,E, A) можно определить тем же образом, что и смешанный граф[en].
Мультиорграфом (или колчаном[en]) G называется упорядоченная четвёрка G:=(V, A, s, t), в которой
В теории категорий небольшие категории могут быть определены как мультиорграфы (с дугами, имеющими собственную идентификацию), оснащённые законом построения и петлями для каждой вершины, служащими левой и правой идентификацией для построения. По этим причинам в теории категорий под термином граф обычно понимается «мультиорграф», и лежащий в основе мультиорграф категории называется базовым орграфом.
Мультиграфы и мультиорграфы поддерживают понятие разметки[en] тем же образом, однако в этом случае нет единства терминологии.
Определения помеченные мультиграфы и помеченные мультиорграфы похожи, так что здесь укажем определение только для мультиорграфа.
Определение 1: Помеченный мультиорграф — это помеченный[en] граф с метками на дугах и вершинах.
Формально: Помеченный мультиорграф G — это кортеж из 8 элементов , в котором
Определение 2: Помеченный мультиорграф — помеченный[en] орграф с кратными помеченными дугами, то есть дугами с теми же концами и теми же метками (это отличается от понятия, данного в статье «Разметка графа[en]»).
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .