Кратні ребра

ребра, інцидентні одним і тим самим двом вершинам

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

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

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

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

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

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

Диполь[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.

ЛітератураРедагувати