Можливості підключення графа

Поняття зв'язності графів відноситься до одного з найбільш важливих понять теорії графів.

Дві довільні вершини xi. xj X графа G = (X, U) називаються зв'язковими. якщо існує маршрут 5, в якому вершини xi. xj будуть кінцевими. Граф називається зв'язковим. якщо будь-які дві його вершини зв'язні, тобто 2 вершини об'єднані простий ланцюгом. В іншому випадку граф не пов'язаний, а кожен зі складових його зв'язкових подграфов G1. G2, ..., Ge називається компонентою зв'язності.

З визначення зв'язності слід:

в зв'язковому графі вершина xi пов'язана сама з собою (рефлексивність);

якщо вершина xi пов'язана з вершиною xj. то xj пов'язана з xi (симетричність);

з чого випливає, що відношення зв'язності є відношенням еквівалентності.

У цьому випадку безліч вершин графа G = (X, U), який моделює схему, можна розбити на непересічні класи Хi. причому ребра графа будуть з'єднувати тільки вершини всередині цих класів. Число компонент, з яких складається граф, називається ступенем зв'язності. Зв'язний граф складається з однієї компоненти зв'язності. Приклади графів складаються з декількох компонент зв'язності наведені на малюнку 7.15.

Однією з характеристик зв'язкових графів є число ребер в графі з n вершинами і заданим числом k компонент зв'язності. Число ребер задовольняє нерівності:

n - k  m  (n - k) (n - k - 1) / 2

Граф з n вершинами містить більш ніж (n-1) (n-2) / 2 ребер пов'язаний.