Як дізнатися чи пов'язаний граф?

Граф називається однозв'язковим (зв'язковим), якщо:

1. У нього одна компонента зв'язності
2. Існує шлях з будь-якої вершини до будь-якої іншої вершини
3. Існує шлях із заданої вершини до будь-якої іншої вершини
4. Містить зв'язковий підграф, що включає всі вершини вихідного графа

Граф називається зв'язковимякщо між кожною парою вершин є шлях. Від кожної вершини до будь-якої іншої вершини має бути певний шлях для проходження. Це називається зв'язністю графа. Граф з кількома незв'язаними вершинами та ребрами називається незв'язним.

Повний граф – граф без петель і кратних ребер, кожна пара вершин з'єднана рубом.Для неографа G з n вершинами без петель такі умови еквівалентні:

1. G – дерево;
2. G – зв'язковий граф, Що містить n-1 ребро;
3. G – ациклічний граф, Що містить n-1 ребро;
4. Будь-які дві несхожі вершини графа G з'єднує єдиний ланцюг.