Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

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

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

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

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

См. также

Примечания

  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.
Эта страница в последний раз была отредактирована 2 августа 2023 в 16:04.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).