Несколько ребер

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

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

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

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

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

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

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

Ссылки

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