Що таке ребро у графі?

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

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

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