В теории графов , несколько ребер (также называемые параллельные кромки или мульти-края ), являются, в неориентированном графе, два или более ребер , которые падающие на одни и те же двух вершины , или в ориентированном графе , два или более ребер с обеими та же вершина хвоста и та же вершина головы. Простой граф не имеет кратных ребер и никаких петель .
В зависимости от контекста граф может быть определен так, чтобы разрешить или запретить наличие нескольких ребер (часто вместе с разрешением или запрещением циклов):
- В тех случаях, когда графы определены таким образом, чтобы допускать наличие нескольких ребер и петель, граф без петель или нескольких ребер часто отличается от других графов, называя его простым графом. [1]
- Если графы определены таким образом, чтобы не допускать множественных ребер и петель, мультиграф или псевдограф часто определяют как «граф», который может иметь петли и множественные ребра. [2]
Множественные ребра полезны, например, при рассмотрении электрических сетей с точки зрения теории графов. [3] Кроме того, они составляют основную отличительную черту многомерных сетей .
А плоский граф остаетс плоским , если ребро добавляется между двумя вершинами уже соединены ребром; таким образом, добавление нескольких краев сохраняет плоскостность. [4]
Дипольный график представляет собой график с двумя вершинами, в котором все ребра расположены параллельно друг другу.
Заметки [ править ]
Ссылки [ править ]
- Балакришнан, ВК; Теория графов , Макгроу-Хилл; 1 издание (1 февраля 1997 г.). ISBN 0-07-005489-4 .
- Боллобаш, Бела; Современная теория графов , Springer; 1-е издание (12 августа 2002 г.). ISBN 0-387-98488-7 .
- Дистель, Рейнхард; Теория графов , Springer; 2-е издание (18 февраля 2000 г.). ISBN 0-387-98976-5 .
- Гросс, Джонатон Л. и Йеллен, Джей; Теория графов и ее приложения , CRC Press (30 декабря 1998 г.). ISBN 0-8493-3982-0 .
- Гросс, Джонатон Л. и Йеллен, Джей; (ред.); Справочник по теории графов . CRC (29 декабря 2003 г.). ISBN 1-58488-090-2 .
- Цвиллинджер, Даниэль; Стандартные математические таблицы и формулы CRC, Chapman & Hall / CRC; 31-е издание (27 ноября 2002 г.). ISBN 1-58488-291-3 .