Мультиграф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Мультиграф с кратными рёбрами (красные) и петлями (синие). Не все авторы разрешают мультиграфам иметь петли.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разметка[править | править вики-текст]

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

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

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

Формально: Помеченный мультиорграф G — это кортеж из 8 элементов G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A), в котором

  • V — множество вершин и A — множество дуг
  • \Sigma_V и \Sigma_A — конечный алфавит, доступный для разметки дуг и вершин,
  • s\colon A\rightarrow\ V и t\colon A\rightarrow\ V — два отображения, определяющие начальную и конечную вершины дуги,
  • \ell_V\colon V\rightarrow\Sigma_V и \ell_A\colon A\rightarrow\Sigma_A — два отображения, описывающие разметку вершин и дуг.

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

Смотрите также[править | править вики-текст]

Примечания[править | править вики-текст]

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

Ссылки[править | править вики-текст]

  • Béla Bollobás Modern Graph Theory. — Springer, 2002.
  • V. K. Balakrishnan Graph Theory. — McGraw-Hill, 1997.
  • Рейнгард Дистель Теория графов. — Новосибирск: Изд-во Ин-та математики, 3003.
  • Jonathan L Gross, Jay Yellen Graph Theory and Its Applications. — McGraw-Hill, 1998.
  • Jonathan L Gross, Jay Yellen Handbook of Graph Theory. — McGraw-Hill, 2003.
  • Ф.Харари Теория графов. — Москва: Едиториал УРСС, 2003.
  • Daniel Zwillinger CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002.
  • Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel The birth of the giant component // Random Structures and Algorithms. — 1993. — В. 3. — Т. 4. — С. 231–358. — DOI:10.1002/rsa.3240040303

Внешние ссылки[править | править вики-текст]

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