1. Можливості підключення і компоненти Граф називається зв'язковим, якщо в ньому для будь-яких двох...

Можливості підключення і компоненти

Граф називається зв'язковим, якщо в ньому для будь-яких двох вершин є маршрут, який з'єднує ці вершини. Зауважимо, що з огляду на теореми 1 можна в цьому визначенні замінити слово "маршрут" словами "простий шлях".

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

У графа на Мал. 2.2 є чотири області зв'язності - , , , .

Вершина називається шарніром (або точкою зчленування), якщо при її видаленні число компонент зв'язності збільшується. У графа на Мал. 2.2 є чотири шарніри - це вершини , , , .

Ребро, при видаленні якого збільшується число компонент зв'язності, називається перешийком. Перешийками графа, зображеного на Мал. 2.2 , Є ребра , , , , .

Легко можна довести такі властивості шарнірів і перешийків:

Теорема 4. Ребро є перешийком в тому і тільки тому випадку, якщо в графі немає простого циклу, що містить це ребро.

Метричні характеристики графів

Відстанню між двома вершинами графа називається найменша довжина шляху, що з'єднує ці вершини. Відстань між вершинами і позначається через . Якщо в графі немає шляху, що з'єднує і , Тобто ці вершини належать різним компонентам зв'язності, то відстань між ними вважається нескінченним.

функція має такі властивості:

1. , причому тоді і тільки тоді, коли ;
2. ;
3. (Нерівність трикутника).

В математиці функцію двох змінних, певну на деякій множині і задовольняє умовам 1 - 3, називають метрикою, а безліч, на якому задана метрика, - метричних простором. Таким чином, безліч вершин будь-якого графа можна розглядати як метричний простір.

Відстань від даної вершини до найбільш віддаленої від неї вершини називається ексцентриситетом вершини і позначається через . Таким чином,

Вершину з найменшим ексцентриситетом називають центральної, а вершину з найбільшим ексцентриситетом - периферійної. Безліч всіх центральних вершин називається центром графа. Сама величина найменшого ексцентриситету називається радіусом графа і позначається через , А величина найбільшого - діаметром і позначається . Інакше кажучи,

Найменший діаметр має повний граф - його діаметр дорівнює 1. Серед зв'язкових графів з вершинами найбільший діаметр, рівний , Має ланцюг .

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

Для графа, зображеного на Мал. 2.3 , Ексцентриситети вершин наведені в наступній таблиці:

Центр цього графа становлять вершини , , ; периферійні вершини - , і ; радіус його дорівнює , А діаметр . Одна з діаметральні ланцюгів породжується безліччю вершин .