В зависимости от контекста граф может быть определен таким образом, чтобы разрешать или запрещать наличие нескольких ребер (часто совместно с разрешением или запрещением петель):
В тех случаях, когда графы определены таким образом, что допускают наличие множественных ребер и петель, граф без петель или множественных ребер часто отличают от других графов, называя его простым графом. [1]
В тех случаях, когда графы определяются таким образом, чтобы не допускать множественных ребер и петель, мультиграф или псевдограф часто определяется как «граф», который может иметь множественные ребра. [2]
Например, множественные ребра полезны при рассмотрении электрических сетей с точки зрения теории графов. [3] Кроме того, они представляют собой основную отличительную черту многомерных сетей .
Планарный граф остается планарным, если ребро добавляется между двумя вершинами, уже соединенными ребром; таким образом, добавление нескольких ребер сохраняет планарность. [4]
Дипольный граф — это граф с двумя вершинами, в котором все ребра параллельны друг другу.
Примечания
^ Например, см. Балакришнан, стр. 1, и Гросс (2003), стр. 4, Цвиллингер, стр. 220.
^ Например, см. Боллобас, с. 7; Дистель, с. 28; Харари, с. 10.
↑ Боллобас, стр. 39–40.
^ Гросс (1998), стр. 308.
Ссылки
Балакришнан, В.К.; Теория графов , McGraw-Hill; 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 .