Кратні ребра
Перейти до навігації
Перейти до пошуку
Кратні ребра (також звані паралельними ребрами або мультиребрами) — це два і більше ребер, інцидентних одним і тим самим двом вершинам. Простий граф кратних ребер не має.
Залежно від контексту граф можна визначити з дозволом або забороною мати кратні ребра (часто разом з дозволом або забороною мати петлі):
- Коли графи визначаються з дозволом кратних ребер та петель, графи без петель називають часто мультиграфами[1].
- Коли графи визначаються з забороною кратних ребер та петель, під мультиграфами або псевдографами часто розуміють «графи», які можуть мати петлі і кратні ребра[2].
Кратні ребра корисні, наприклад, під час розгляду електричних кіл з точки зору теорії графів[3]. Крім того, вони становлять ядро диференціювальних властивостей багатовимірних мереж[en].
Планарний граф залишається планарним, якщо додати ребро між двома вершинами, вже пов'язаними ребром. Тобто додавання ребра зберігає планарність[4].
Диполь[en] — це граф з двома вершинами, в якому всі ребра паралельні.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ Наприклад, див. (Balakrishnan, 1997), стор. 1, (Gross, Yellen, 2003), стор. 4, (Zwillinger, 2002), стр. 220.
- ↑ Наприклад, див. Bollobás стр. 7, Diestel стр. 28, Harary, p. 10.
- ↑ Bollobás стр. 39–;40.
- ↑ (Gross, Yellen, 1998), стр. 308.
Література[ред. | ред. код]
- Balakrishnan V. K. Graph Theory. — McGraw-Hill, 1997. — ISBN 0-07-005489-4.
- Béla Bollobás[en]. 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.