Меню
Главная
Случайная статья
Настройки
|
Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.
В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):
- Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1].
- Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра[2].
Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов[3]. Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей[англ.].
Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность[4].
Диполь[англ.] — это граф с двумя вершинами, в котором все рёбра параллельны.
Примечания
- Например, см. Balakrishnan, 1997, стр. 1, Gross, Yellen, 2003, стр. 4, (Zwillinger 2002), стр. 220.
- Например, см. Bollobs стр. 7, Diestel стр. 28, Harary, p. 10.
- Bollobs стр. 39–;40.
- Gross, Yellen, 1998, стр. 308.
Литература
|
|