Що означає стягування ребра?

Теоретично графів стягування ребра — це операція, яка видаляє ребро з графа, а до цього пов'язані ребром вершини зливаються в одну вершину. Стягування ребра є фундаментальною операцією в теорії про мінори графів.

Інцидентність – вершина та ребро називаються інцидентними, якщо вершина є для цього ребра кінцевий. Зверніть увагу, що термін “інцидентність” застосуємо тільки до вершини та ребру. Сумежність вершин – дві вершини називаються суміжними, якщо вони інцидентні одному ребру.

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

11.6). У відмінність від ребер, дуги з'єднують дві нерівноправні вершини: одна з них називається початком дуги ( дуга з неї виходить ), друга – кінцем дуги ( дуга до неї входить).