Мультиграф (Brl,mnijgs)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Multi-pseudograph.svg/220px-Multi-pseudograph.svg.png)
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»[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 — множество дуг,
- назначает каждой дуге начальную вершину,
- назначает каждой дуге конечную вершину.
В теории категорий небольшие категории могут быть определены как мультиорграфы (с дугами, имеющими собственную идентификацию), оснащённые законом построения и петлями для каждой вершины, служащими левой и правой идентификацией для построения. По этим причинам в теории категорий под термином граф обычно понимается «мультиорграф», и лежащий в основе мультиорграф категории называется базовым орграфом.
Разметка
[править | править код]Мультиграфы и мультиорграфы поддерживают понятие разметки тем же образом, однако в этом случае нет единства терминологии.
Определения помеченные мультиграфы и помеченные мультиорграфы похожи, так что здесь укажем определение только для мультиорграфа.
Определение 1: Помеченный мультиорграф — это помеченный граф с метками на дугах и вершинах.
Формально: Помеченный мультиорграф G — это кортеж из 8 элементов , в котором
- V — множество вершин и A — множество дуг,
- и — конечный алфавит, доступный для разметки дуг и вершин,
- и — два отображения, определяющие начальную и конечную вершины дуги,
- и — два отображения, описывающие разметку вершин и дуг.
Определение 2: Помеченный мультиорграф — помеченный орграф с кратными помеченными дугами, то есть дугами с теми же концами и теми же метками (это отличается от понятия, данного в статье «Разметка графа»).
См. также
[править | править код]Примечания
[править | править код]- ↑ Например, смотрите Balakrishnan, стр. 1.
- ↑ Например, смотрите книги Болобаса (Bollobás), страница 7, или Дистеля (Diestel), страница 25.
- ↑ 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.
Для улучшения этой статьи желательно:
|