WikiDer > Множественные края
В теория графов, несколько краев (также называемый параллельные края или многогранный), в неориентированном графе два или более края которые инцидент к тем же двум вершины, или в ориентированный граф, два или более ребра с одинаковой хвостовой вершиной и одинаковой головной вершиной. А простой график не имеет нескольких ребер.
В зависимости от контекста график может быть определено так, чтобы разрешить или запретить наличие нескольких краев (часто вместе с разрешением или запрещением петли):
- Где графики определены так, чтобы позволять кратных ребер и петель, граф без петель часто называют мультиграф.[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.