Мультиграф

Мультиграф с кратными рёбрами (красные) и петлями (синие). Не все авторы разрешают мультиграфам иметь петли.

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

1. Например, смотрите Balakrishnan, стр. 1.
2. Например, смотрите книги Болобаса (Bollobás), страница 7, или Дистеля (Diestel), страница 25.
3. Robert A. Wilson. Graphs, Colourings and the Four-Colour Theorem. — 2002. — С. 6. — ISBN 0-19-851062-4.

Ссылки

• 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:10.1002/rsa.3240040303.

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

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