WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Кратные рёбра, соединяющие две вершины.

Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.

В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):

  • Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1].
  • Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра[2].

Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов[3]. Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей[en].

Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность[4].

Диполь[en] — это граф с двумя вершинами, в котором все рёбра параллельны.

Примечания

  1. ↑ Например, см. Balakrishnan, 1997, стр. 1, Gross, Yellen, 2003, стр. 4, (Zwillinger 2002), стр. 220.
  2. ↑ Например, см. Bollobás стр. 7, Diestel стр. 28, Harary, p. 10.
  3. ↑ Bollobás стр. 39–;40.
  4. ↑ Gross, Yellen, 1998, стр. 308.

Литература

  • Balakrishnan V. K. Graph Theory. — McGraw-Hill, 1997. — ISBN 0-07-005489-4.
  • Béla Bollobás. Modern Graph Theory. — Springer, 2002. — ISBN 0-387-98488-7.
  • Reinhard Diestel. Graph Theory. — Springer, 2000. — ISBN 0-387-98976-5.
    • Рейнгард Дистель. Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X.
  • Jonathon L. Gross, Jay Yellen. Graph Theory and Its Applications. — CRC Press, 1998. — ISBN 0-8493-3982-0.
  • Handbook of Graph Theory / Jonathon L. Gross, Jay Yellen. — CRC Press, 2003. — ISBN 1-58488-090-2.
  • Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002. — ISBN 1-58488-291-3.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии