Кратні ребра

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

Кратні ребра, що з'єднують дві вершини.

Залежно від контексту граф можна визначити з дозволом або забороною мати кратні ребра (часто разом з дозволом або забороною мати петлі):

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

Кратні ребра корисні, наприклад, під час розгляду електричних кіл з точки зору теорії графів. Крім того, вони становлять ядро диференціювальних властивостей ^[en].

Планарний граф залишається планарним, якщо додати ребро між двома вершинами, вже пов'язаними ребром. Тобто додавання ребра зберігає планарність.

^[en] — це граф з двома вершинами, в якому всі ребра паралельні.

Див. також

• Мультиграф

Примітки

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. — .
• ^[en]. Modern Graph Theory. — Springer, 2002. — .
• Reinhard Diestel. Graph Theory. — Springer, 2000. — .
  • Рейнгард Дистель. Теория графов. — Новосибирск : Издательство Института математики, 2002. — .
• Jonathon L. Gross, Jay Yellen. Graph Theory and Its Applications. — CRC Press, 1998. — .
• Handbook of Graph Theory / Jonathon L. Gross, Jay Yellen. — CRC Press, 2003. — .
• Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002. — .