Мультиграф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разметка

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

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

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

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

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

Определение 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:10.1002/rsa.3240040303.

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

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

Отрывок, характеризующий Мультиграф

Княжна Марья, не предвидя этому конца, первая встала и, жалуясь на мигрень, стала прощаться.
– Так вы завтра едете в Петербург? – сказала ока.
– Нет, я не еду, – с удивлением и как будто обидясь, поспешно сказал Пьер. – Да нет, в Петербург? Завтра; только я не прощаюсь. Я заеду за комиссиями, – сказал он, стоя перед княжной Марьей, краснея и не уходя.
Наташа подала ему руку и вышла. Княжна Марья, напротив, вместо того чтобы уйти, опустилась в кресло и своим лучистым, глубоким взглядом строго и внимательно посмотрела на Пьера. Усталость, которую она очевидно выказывала перед этим, теперь совсем прошла. Она тяжело и продолжительно вздохнула, как будто приготавливаясь к длинному разговору.
Все смущение и неловкость Пьера, при удалении Наташи, мгновенно исчезли и заменились взволнованным оживлением. Он быстро придвинул кресло совсем близко к княжне Марье.
– Да, я и хотел сказать вам, – сказал он, отвечая, как на слова, на ее взгляд. – Княжна, помогите мне. Что мне делать? Могу я надеяться? Княжна, друг мой, выслушайте меня. Я все знаю. Я знаю, что я не стою ее; я знаю, что теперь невозможно говорить об этом. Но я хочу быть братом ей. Нет, я не хочу.. я не могу…
Он остановился и потер себе лицо и глаза руками.
– Ну, вот, – продолжал он, видимо сделав усилие над собой, чтобы говорить связно. – Я не знаю, с каких пор я люблю ее. Но я одну только ее, одну любил во всю мою жизнь и люблю так, что без нее не могу себе представить жизни. Просить руки ее теперь я не решаюсь; но мысль о том, что, может быть, она могла бы быть моею и что я упущу эту возможность… возможность… ужасна. Скажите, могу я надеяться? Скажите, что мне делать? Милая княжна, – сказал он, помолчав немного и тронув ее за руку, так как она не отвечала.
– Я думаю о том, что вы мне сказали, – отвечала княжна Марья. – Вот что я скажу вам. Вы правы, что теперь говорить ей об любви… – Княжна остановилась. Она хотела сказать: говорить ей о любви теперь невозможно; но она остановилась, потому что она третий день видела по вдруг переменившейся Наташе, что не только Наташа не оскорбилась бы, если б ей Пьер высказал свою любовь, но что она одного только этого и желала.
– Говорить ей теперь… нельзя, – все таки сказала княжна Марья.
– Но что же мне делать?
– Поручите это мне, – сказала княжна Марья. – Я знаю…
Пьер смотрел в глаза княжне Марье.
– Ну, ну… – говорил он.
– Я знаю, что она любит… полюбит вас, – поправилась княжна Марья.
Не успела она сказать эти слова, как Пьер вскочил и с испуганным лицом схватил за руку княжну Марью.
– Отчего вы думаете? Вы думаете, что я могу надеяться? Вы думаете?!
– Да, думаю, – улыбаясь, сказала княжна Марья. – Напишите родителям. И поручите мне. Я скажу ей, когда будет можно. Я желаю этого. И сердце мое чувствует, что это будет.
– Нет, это не может быть! Как я счастлив! Но это не может быть… Как я счастлив! Нет, не может быть! – говорил Пьер, целуя руки княжны Марьи.
– Вы поезжайте в Петербург; это лучше. А я напишу вам, – сказала она.
– В Петербург? Ехать? Хорошо, да, ехать. Но завтра я могу приехать к вам?
На другой день Пьер приехал проститься. Наташа была менее оживлена, чем в прежние дни; но в этот день, иногда взглянув ей в глаза, Пьер чувствовал, что он исчезает, что ни его, ни ее нет больше, а есть одно чувство счастья. «Неужели? Нет, не может быть», – говорил он себе при каждом ее взгляде, жесте, слове, наполнявших его душу радостью.
Когда он, прощаясь с нею, взял ее тонкую, худую руку, он невольно несколько дольше удержал ее в своей.
«Неужели эта рука, это лицо, эти глаза, все это чуждое мне сокровище женской прелести, неужели это все будет вечно мое, привычное, такое же, каким я сам для себя? Нет, это невозможно!..»
– Прощайте, граф, – сказала она ему громко. – Я очень буду ждать вас, – прибавила она шепотом.
И эти простые слова, взгляд и выражение лица, сопровождавшие их, в продолжение двух месяцев составляли предмет неистощимых воспоминаний, объяснений и счастливых мечтаний Пьера. «Я очень буду ждать вас… Да, да, как она сказала? Да, я очень буду ждать вас. Ах, как я счастлив! Что ж это такое, как я счастлив!» – говорил себе Пьер.


В душе Пьера теперь не происходило ничего подобного тому, что происходило в ней в подобных же обстоятельствах во время его сватовства с Элен.
Он не повторял, как тогда, с болезненным стыдом слов, сказанных им, не говорил себе: «Ах, зачем я не сказал этого, и зачем, зачем я сказал тогда „je vous aime“?» [я люблю вас] Теперь, напротив, каждое слово ее, свое он повторял в своем воображении со всеми подробностями лица, улыбки и ничего не хотел ни убавить, ни прибавить: хотел только повторять. Сомнений в том, хорошо ли, или дурно то, что он предпринял, – теперь не было и тени. Одно только страшное сомнение иногда приходило ему в голову. Не во сне ли все это? Не ошиблась ли княжна Марья? Не слишком ли я горд и самонадеян? Я верю; а вдруг, что и должно случиться, княжна Марья скажет ей, а она улыбнется и ответит: «Как странно! Он, верно, ошибся. Разве он не знает, что он человек, просто человек, а я?.. Я совсем другое, высшее».
Только это сомнение часто приходило Пьеру. Планов он тоже не делал теперь никаких. Ему казалось так невероятно предстоящее счастье, что стоило этому совершиться, и уж дальше ничего не могло быть. Все кончалось.
Радостное, неожиданное сумасшествие, к которому Пьер считал себя неспособным, овладело им. Весь смысл жизни, не для него одного, но для всего мира, казался ему заключающимся только в его любви и в возможности ее любви к нему. Иногда все люди казались ему занятыми только одним – его будущим счастьем. Ему казалось иногда, что все они радуются так же, как и он сам, и только стараются скрыть эту радость, притворяясь занятыми другими интересами. В каждом слове и движении он видел намеки на свое счастие. Он часто удивлял людей, встречавшихся с ним, своими значительными, выражавшими тайное согласие, счастливыми взглядами и улыбками. Но когда он понимал, что люди могли не знать про его счастье, он от всей души жалел их и испытывал желание как нибудь объяснить им, что все то, чем они заняты, есть совершенный вздор и пустяки, не стоящие внимания.