double arrow

Маршрут. Зв’язність графів. Компоненти зв’язності.

Маршрутом (шляхом) у графі G називається послідовність ребер та інцидент них ним вершин, що складають неперервну криву.

Довжиною маршруту називають кількість ребер в ньому, при чому кожне ребро в ньому вказується стільки разів, скільки воно зустрічається в маршруті.

Маршрутом довжини 0 називається маршрут, що складається з єдиної вершини.

Маршрути: відкритий; замкнений, якщо він починається і закінчується в одній і тій самій вершині.

Маршрут всі ребра якого різні називається ланцюгом.

Граф G називається зв’язним, якщо кожні дві його вершини зв’язні між собою.

Максимальний не пустий зв’язний підграф G’ графа G називають компонентою зв’язності.

Ейлерові графи. Теорема Ейлера.

Цикл, який містить усі ребра графа називається Ейлеровим.

Зв’язний граф G, що мітить Ейлерів цикл називається Ейлеровим графом.

Зв’язний граф G є Ейлеровим тоді коли степені всіх його вершин є парними.

Не тривіальний граф G має цикл тільки тоді коли він має тільки дві вершини непарного степеня.

Гамільтонові графи. Приклади.

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

Граф G називається Гамільтоновим, якщо він містить Гамільтонів цикл.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: