Теорія графіків: властивості та складові частини графіків

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

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

Підграф — це частина (тобто деякі вибрані вершини та ребра) графа, яка сама також утворює граф. Отже, кожне ребро у підграфі мусить мати вершину на обох кінцях, яка також належить підграфу. Жовті вершини та ребра на малюнку утворюють підграф.

У повному графі кожна вершина з’єднана з іншими. Отже, цей граф має максимальну кількість ребер, яку він може мати.

Дерево — це безперервний граф, який не містить кола як підграфа. Дерева мають багато цікавих властивостей і часто використовуються в інформатиці, наприклад, для чіткого та ефективного зберігання даних.