Из Википедии, бесплатной энциклопедии
  (Перенаправлено с нескольких ребер )
Перейти к навигации Перейти к поиску
Несколько ребер, соединяющих две вершины.

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

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

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

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

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

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

Заметки [ править ]

  1. ^ Например, см. Балакришнан, стр. 1, и Гросс (2003), стр. 4, Zwillinger, p. 220.
  2. ^ Например, см. Bollobás, p. 7 ; Дистель, стр. 28 ; Харари, стр. 10.
  3. ^ Bollobás, стр. 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 .