Кратные рёбра

Кратные рёбра, соединяющие две вершины.

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

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

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

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

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

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

Примечания

1. Например, см. Balakrishnan, 1997, стр. 1, Gross, Yellen, 2003, стр. 4, (Zwillinger 2002), стр. 220.
2. Например, см. Bollobás стр. 7, Diestel стр. 28, Harary, p. 10.
3. Bollobás стр. 39–;40.
4. Gross, Yellen, 1998, стр. 308.

Литература

• Balakrishnan V. K. Graph Theory. — McGraw-Hill, 1997. — ISBN 0-07-005489-4.
• Béla Bollobás. Modern Graph Theory. — Springer, 2002. — ISBN 0-387-98488-7.
• Reinhard Diestel. Graph Theory. — Springer, 2000. — ISBN 0-387-98976-5.
  • Рейнгард Дистель. Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X.
• Jonathon L. Gross, Jay Yellen. Graph Theory and Its Applications. — CRC Press, 1998. — ISBN 0-8493-3982-0.
• Handbook of Graph Theory / Jonathon L. Gross, Jay Yellen. — CRC Press, 2003. — ISBN 1-58488-090-2.
• Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002. — ISBN 1-58488-291-3.