WikiDer > Множественные края

Multiple edges
Несколько ребер, соединяющих две вершины.

В теория графов, несколько краев (также называемый параллельные края или многогранный), в неориентированном графе два или более края которые инцидент к тем же двум вершины, или в ориентированный граф, два или более ребра с одинаковой хвостовой вершиной и одинаковой головной вершиной. А простой график не имеет нескольких ребер.

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

  • Где графики определены так, чтобы позволять кратных ребер и петель, граф без петель часто называют мультиграф.[1]
  • Где графики определены так, чтобы запретить несколько ребер и петель, мультиграф или псевдограф часто определяется как "график", может иметь петли и несколько краев.[2]

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

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

А дипольный график - граф с двумя вершинами, в котором все ребра параллельны друг другу.

Примечания

  1. ^ Например, см. Балакришнан, с. 1, и Гросс (2003), стр. 4, Zwillinger, p. 220.
  2. ^ Например, см. Bollobás, п. 7; Дистель, п. 28; Харари, стр. 10.
  3. ^ Боллобаш, стр. 39–40.
  4. ^ Валовой (1998), п. 308.

Рекомендации

  • Балакришнан, В.К .; Теория графов, Макгроу-Хилл; 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.