вно маршрут. Сільнозв'язною компонентом графу назівається его Максимальний відносно включенням сільнозв'язній граф. Нехай G - зв'язного граф, а u и v - Дві его вершини, что НЕ співпадають. Довжина найкоротшого (u, v)-маршрутом назівається відстанню между вершинами u та v и позначається d (u, v). Нехай d (u, u) = 0. Очевидно, что введена таким чином відстань задовольняє Такі аксіомі:
1);
) тоді и Тільки тоді, коли;
) для неорієнотованого графа;
) (так кличуть входити нерівність трикутника).
Для фіксованої вершини u величина назівається ексцентрісітетом вершини u. Максимальний среди ексцентрісітетів вершин назівається діаметром графу G и позначається через d (G), тоб. p> Вершина v назівається періферійною, ЯКЩО. Простий ланцюг Довжина, відстань между кінцямі Якого рівна, назівається діаметральнім Ланцюг. p> Мінімальній Із ексцентрісітетів вершин звязного графу назівається его радіусом и позначається через. Очевидно, что Радіус графу НЕ больше его діаметра. p> Вершина v назівається центральною, ЯКЩО. Множини всех центральних вершин графа назівається его центром. Граф может мати єдину Центральну вершину або декілька. Центр графа может співпадаті з множини всех вершин. Наприклад, центр простого ланцюга при парній кількості вершин n Складається Рівно з двох вершин, а при непарній - з однієї; для циклу ВСІ вершини є центральними. br/>
.4 Ейлеровій граф, ланцюг, цикл
Ланцюг, что містіть ВСІ ребра графа, назівають ейлеровім Ланцюг. Цикл в графі назівається ейлеровім, ЯКЩО ВІН містіть ВСІ ребра графа. Зв'язного граф, в котрому є ейлеровій цикл, назівається ейлеровім графом. Такий граф можна намалюваті, що не відріваючі олівця від паперу и НЕ повторюючі ліній. p align="justify"> Теорема Ейлера. Зв'язного граф є ейлеровім тоді и Тільки тоді, коли степені всех его вершин парні. p align="justify"> Необхідність. Нехай G - ейлеровій граф. Ейлеровій цикл цього графу, что проходити через шкірні его вершину, входити в неї через Одне ребро, а виходе через Інше. Це означає, что Кожна вершина інцідентна парному числу ребер ейлерового циклу, а оскількі такий цикл містіть ВСІ ребра графа G, то звідсі віпліває парність ступенів усіх его вершин. p align="justify"> Достатність. Припустиме тепер, что степені вершин графа G парні. Почнемо ланцюг P1 з довільної вершини v1 и будемо продовжуваті ее, наскількі Можливо, обираючи щоразу нове ребро. Так як степені усіх вершин парні, то Потрапивши в Чергова відмінну від v1 вершину, мі всегда будемо мати в розпорядженні галі не пройдений ребро. Тому ланцюг P1 можна продовжіті Шляхом додавання цього ребра. Таким чином, побудова ланцюга P1 закінчіться у вершіні v1, тоб P1 неодмінно будемо циклом. Если виявило, что P1 містіть ВСІ ребра графа G, то це буде Потрібний ейлеровій цикл. У Іншому випадка, Відаль з G ВСІ ребра циклу P1, розглянемо граф G1, отриманий в результаті Такої Операції. Оскількі P1 и G мал...
