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

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

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

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

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

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

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

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

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

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

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

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

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

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

• V — множество вершин ,
• A — множество дуг ,
• ${\displaystyle s:A\rightarrow V}$ назначает каждой дуге начальную вершину,
• ${\displaystyle t:A\rightarrow V}$ назначает каждой дуге конечную вершину.

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

Разметка

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

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

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

Формально: Помеченный мультиорграф G — это кортеж из 8 элементов ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$ , в котором

• V — множество вершин и A — множество дуг,
• ${\displaystyle \Sigma _{V}}$ и ${\displaystyle \Sigma _{A}}$ — конечный алфавит, доступный для разметки дуг и вершин,
• ${\displaystyle s\colon A\rightarrow \ V}$ и ${\displaystyle t\colon A\rightarrow \ V}$ — два отображения, определяющие начальную и конечную вершины дуги,
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$ и ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$ — два отображения, описывающие разметку вершин и дуг.

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

См. также

• Глоссарий теории графов
• Теория графов

Примечания

Ссылки

• Béla Bollobás. Modern Graph Theory. — Springer, 2002. — ISBN 0-387-98488-7 .
• V. K. Balakrishnan. Graph Theory. — McGraw-Hill, 1997. — ISBN 0-07-005489-4 .
• Рейнгард Дистель. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-X .
• Jonathan L Gross, Jay Yellen. Graph Theory and Its Applications. — McGraw-Hill, 1998. — ISBN 0-8493-3982-0 .
• Jonathan L Gross, Jay Yellen. Handbook of Graph Theory. — McGraw-Hill, 2003. — ISBN 1-58488-090-2 .
• Ф.Харари. Теория графов. — Москва: Едиториал УРСС, 2003. — ISBN 5-354-00301-6 .
• Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002. — ISBN 1-58488-291-3 .
• Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel. The birth of the giant component // Random Structures and Algorithms. — 1993. — Т. 4 , вып. 3 . — С. 231—358 . — doi : .

Внешние ссылки

• Paul E. Black, Multigraph at the NIST Dictionary of Algorithms and Data Structures.