Що таке паралельні ребра у графі?

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

Граф – це геометрична фігура, яка складається з точок та ліній, що їх з'єднують. Крапки називають вершинами графа, а лінії – ребрами. Два ребра називаються суміжними, якщо вони мають загальна вершина. Два ребра називаються кратними, якщо вони з'єднують ту саму пару вершин.

Число ребер у повному графі n(n-1)/2. Графи рівні, якщо безліч вершин та інцидентних їм ребер збігаються. Графи, що відрізняються тільки нумерацією вершин і реберназиваються ізоморфними. Граф називається регулярним (однорідним), якщо ступеня всіх його вершин рівні.

Вага ребра — значення, поставлене у відповідність до цього ребру зваженого графа. Зазвичай вага — речове число, у такому разі його можна інтерпретувати як «довжину» ребра. Зважений граф — графкожному ребру якого поставлено у відповідність певне значення (вага ребра).