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

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

• Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами .
• Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра .

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

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

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

Примечания

Литература