Мультиграф
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер[en] (их также называют «параллельными»[1]), то есть рёбра, имеющие те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Существует два различных способа обозначения рёбер мультиграфа. Некоторые говорят, что, как и в случае графов без кратных рёбер, ребро определяется вершинами, которые оно соединяет, но каждое ребро может повторяться несколько раз. Другие определяют рёбра равноправными с вершинами элементами графа и они должны иметь собственную идентификацию.
Содержание
Неориентированные мультиграфы (рёбра без собственной идентификации)
Формально, мультиграфом G называется упорядоченная пара G:=(V, E), в которой
- V — множество вершин,
- E — мультимножество неупорядоченных пар вершин. Элементы этого множества называются рёбрами.
Мультиграфы можно использовать для представления возможных воздушных путей самолёта. В этом случае мультиграф становится ориентированным и пара ориентированных параллельных рёбер, связывающая города, показывает, что можно лететь в обоих направлениях — из города или в город.
Некоторые авторы позволяю мультиграфам иметь петли, то есть рёбра, соединяющие вершину с ней же[2], в то время как другие называют такие графы псевдографами, оставляя термин мультиграф для графов без петель[3].
Ориентированные мультиграфы (рёбра без собственной идентификации)
Мультиорграф — это ориентированный граф, в котором разрешены кратные дуги, то есть дуги, имеющие те же начальные и конечные вершины.
Мультиорграфом G называется упорядоченная пара G:=(V,A), в которой
- V — множество вершин,
- A — мультимножество упорядоченных пар вершин. Элементы этого множества называются дугами.
Смешанный мультиграф G:=(V,E, A) можно определить тем же образом, что и смешанный граф[en].
Ориентированные мультиграфы (рёбра с собственной идентификацией)
Мультиорграфом (или колчаном[en]) G называется упорядоченная четвёрка G:=(V, A, s, t), в которой
- V — множество вершин,
- A — множество дуг,
- <math>s : A \rightarrow V</math> назначает каждой дуге начальную вершину,
- <math>t : A \rightarrow V</math> назначает каждой дуге конечную вершину.
В теории категорий небольшие категории могут быть определены как мультиорграфы (с дугами, имеющими собственную идентификацию), оснащённые законом построения и петлями для каждой вершины, служащими левой и правой идентификацией для построения. По этим причинам в теории категорий под термином граф обычно понимается «мультиорграф», и лежащий в основе мультиорграф категории называется базовым орграфом.
Разметка
Мультиграфы и мультиорграфы поддерживают понятие разметки[en] тем же образом, однако в этом случае нет единства терминологии.
Определения помеченные мультиграфы и помеченные мультиорграфы похожи, так что здесь укажем определение только для мультиорграфа.
Определение 1: Помеченный мультиорграф — это помеченный[en] граф с метками на дугах и вершинах.
Формально: Помеченный мультиорграф 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: Помеченный мультиорграф — помеченный[en] орграф с кратными помеченными дугами, то есть дугами с теми же концами и теми же метками (это отличается от понятия, данного в статье «Разметка графа[en]»).
Смотрите также
Напишите отзыв о статье "Мультиграф"
Примечания
- ↑ Например, смотрите 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.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Мультиграф
Княжна Марья, не предвидя этому конца, первая встала и, жалуясь на мигрень, стала прощаться.– Так вы завтра едете в Петербург? – сказала ока.
– Нет, я не еду, – с удивлением и как будто обидясь, поспешно сказал Пьер. – Да нет, в Петербург? Завтра; только я не прощаюсь. Я заеду за комиссиями, – сказал он, стоя перед княжной Марьей, краснея и не уходя.
Наташа подала ему руку и вышла. Княжна Марья, напротив, вместо того чтобы уйти, опустилась в кресло и своим лучистым, глубоким взглядом строго и внимательно посмотрела на Пьера. Усталость, которую она очевидно выказывала перед этим, теперь совсем прошла. Она тяжело и продолжительно вздохнула, как будто приготавливаясь к длинному разговору.
Все смущение и неловкость Пьера, при удалении Наташи, мгновенно исчезли и заменились взволнованным оживлением. Он быстро придвинул кресло совсем близко к княжне Марье.
– Да, я и хотел сказать вам, – сказал он, отвечая, как на слова, на ее взгляд. – Княжна, помогите мне. Что мне делать? Могу я надеяться? Княжна, друг мой, выслушайте меня. Я все знаю. Я знаю, что я не стою ее; я знаю, что теперь невозможно говорить об этом. Но я хочу быть братом ей. Нет, я не хочу.. я не могу…
Он остановился и потер себе лицо и глаза руками.
– Ну, вот, – продолжал он, видимо сделав усилие над собой, чтобы говорить связно. – Я не знаю, с каких пор я люблю ее. Но я одну только ее, одну любил во всю мою жизнь и люблю так, что без нее не могу себе представить жизни. Просить руки ее теперь я не решаюсь; но мысль о том, что, может быть, она могла бы быть моею и что я упущу эту возможность… возможность… ужасна. Скажите, могу я надеяться? Скажите, что мне делать? Милая княжна, – сказал он, помолчав немного и тронув ее за руку, так как она не отвечала.
– Я думаю о том, что вы мне сказали, – отвечала княжна Марья. – Вот что я скажу вам. Вы правы, что теперь говорить ей об любви… – Княжна остановилась. Она хотела сказать: говорить ей о любви теперь невозможно; но она остановилась, потому что она третий день видела по вдруг переменившейся Наташе, что не только Наташа не оскорбилась бы, если б ей Пьер высказал свою любовь, но что она одного только этого и желала.
– Говорить ей теперь… нельзя, – все таки сказала княжна Марья.
– Но что же мне делать?
– Поручите это мне, – сказала княжна Марья. – Я знаю…
Пьер смотрел в глаза княжне Марье.
– Ну, ну… – говорил он.
– Я знаю, что она любит… полюбит вас, – поправилась княжна Марья.
Не успела она сказать эти слова, как Пьер вскочил и с испуганным лицом схватил за руку княжну Марью.
– Отчего вы думаете? Вы думаете, что я могу надеяться? Вы думаете?!
– Да, думаю, – улыбаясь, сказала княжна Марья. – Напишите родителям. И поручите мне. Я скажу ей, когда будет можно. Я желаю этого. И сердце мое чувствует, что это будет.
– Нет, это не может быть! Как я счастлив! Но это не может быть… Как я счастлив! Нет, не может быть! – говорил Пьер, целуя руки княжны Марьи.
– Вы поезжайте в Петербург; это лучше. А я напишу вам, – сказала она.
– В Петербург? Ехать? Хорошо, да, ехать. Но завтра я могу приехать к вам?
На другой день Пьер приехал проститься. Наташа была менее оживлена, чем в прежние дни; но в этот день, иногда взглянув ей в глаза, Пьер чувствовал, что он исчезает, что ни его, ни ее нет больше, а есть одно чувство счастья. «Неужели? Нет, не может быть», – говорил он себе при каждом ее взгляде, жесте, слове, наполнявших его душу радостью.
Когда он, прощаясь с нею, взял ее тонкую, худую руку, он невольно несколько дольше удержал ее в своей.
«Неужели эта рука, это лицо, эти глаза, все это чуждое мне сокровище женской прелести, неужели это все будет вечно мое, привычное, такое же, каким я сам для себя? Нет, это невозможно!..»
– Прощайте, граф, – сказала она ему громко. – Я очень буду ждать вас, – прибавила она шепотом.
И эти простые слова, взгляд и выражение лица, сопровождавшие их, в продолжение двух месяцев составляли предмет неистощимых воспоминаний, объяснений и счастливых мечтаний Пьера. «Я очень буду ждать вас… Да, да, как она сказала? Да, я очень буду ждать вас. Ах, как я счастлив! Что ж это такое, как я счастлив!» – говорил себе Пьер.
В душе Пьера теперь не происходило ничего подобного тому, что происходило в ней в подобных же обстоятельствах во время его сватовства с Элен.
Он не повторял, как тогда, с болезненным стыдом слов, сказанных им, не говорил себе: «Ах, зачем я не сказал этого, и зачем, зачем я сказал тогда „je vous aime“?» [я люблю вас] Теперь, напротив, каждое слово ее, свое он повторял в своем воображении со всеми подробностями лица, улыбки и ничего не хотел ни убавить, ни прибавить: хотел только повторять. Сомнений в том, хорошо ли, или дурно то, что он предпринял, – теперь не было и тени. Одно только страшное сомнение иногда приходило ему в голову. Не во сне ли все это? Не ошиблась ли княжна Марья? Не слишком ли я горд и самонадеян? Я верю; а вдруг, что и должно случиться, княжна Марья скажет ей, а она улыбнется и ответит: «Как странно! Он, верно, ошибся. Разве он не знает, что он человек, просто человек, а я?.. Я совсем другое, высшее».
Только это сомнение часто приходило Пьеру. Планов он тоже не делал теперь никаких. Ему казалось так невероятно предстоящее счастье, что стоило этому совершиться, и уж дальше ничего не могло быть. Все кончалось.
Радостное, неожиданное сумасшествие, к которому Пьер считал себя неспособным, овладело им. Весь смысл жизни, не для него одного, но для всего мира, казался ему заключающимся только в его любви и в возможности ее любви к нему. Иногда все люди казались ему занятыми только одним – его будущим счастьем. Ему казалось иногда, что все они радуются так же, как и он сам, и только стараются скрыть эту радость, притворяясь занятыми другими интересами. В каждом слове и движении он видел намеки на свое счастие. Он часто удивлял людей, встречавшихся с ним, своими значительными, выражавшими тайное согласие, счастливыми взглядами и улыбками. Но когда он понимал, что люди могли не знать про его счастье, он от всей души жалел их и испытывал желание как нибудь объяснить им, что все то, чем они заняты, есть совершенный вздор и пустяки, не стоящие внимания.