Питання для повторення
1.Чем присвячений розділ дискретної математики, що вивчає теорію графів?
2.В чому відмінність орієнтованого і неорієнтованого графів?
3. Дайте визначення графа?
4.У чому полягає сенс відносини інцидентності?
5.Локальная ступінь вершини графа це?
6. У якому випадку графи називаються ізоморфними?
7.Назовите способи завдання графів?
8.Перечислите відмінності матриці інцидентності і матриці суміжності?
9.Когда граф називається частиною графа?
Розглядається розділ дискретної математики вивчає теорію графів. Наведено основні поняття теорії графів такі, як вершина, ребро, орієнтований граф і так далі. Дано поняття локальної ступеня. Показані способи завдання графів з їх демонстрацією. Окремо розглянуті операції над частинами графа, а так само графи і бінарні відносини.
Мета. вивчити різні види конструкцій графів.
1 Розглянути поняття маршрут, шлях, ланцюг і цикл стосовно графам.
2 Розглянути структуру графа дерева і лісу.
Нехай G - неорієнтований граф.
Маршрутом в G називається така послідовність ребер M, в якій кожні два сусідніх ребра і мають загальну вершину. У маршруті один і той же ребро може зустрічатися кілька разів. Початок маршруту - вершина, инцидентная ребру і не инцидентная; кінець маршруту інциденту і не інцидентів. Якщо - кратні, потрібне додаткове вказівку, яку з двох інцидентних вершин вважати початком (кінцем) маршруту.
Маршрут, в якому збігаються його початок і кінець, (тобто замкнутий), називається циклічним. Маршрут, в якому всі ребра різні, називається ланцюгом. Ланцюг, не яка перетинає себе, тобто яка не містить повторюваних вершин, називається простий ланцюгом.
Циклічний маршрут називається циклом, якщо він є ланцюгом, і простим циклом. коли це - проста ланцюг.
Вершини називаються пов'язаними, якщо існує маршрут М з початком і кінцем. Пов'язані маршрутом вершини пов'язані також і простий ланцюгом. Ставлення пов'язаності вершин має властивості еквівалентності і визначає розбиття множини вершин графа на непересічні підмножини. Граф G називається пов'язаним. якщо всі його вершини пов'язані між собою. Тому все підграфи G () пов'язані і називаються пов'язаними компонентами графа. Кожен н-граф розпадається єдиним чином в пряму суму своїх пов'язаних компонент
Нехай G - орієнтований граф.
Послідовність ребер, в якій кінець кожного попереднього ребра збігається з початком наступного, називається шляхом (в ньому все ребра проходять по їх орієнтації). В дорозі одне і те ж ребро може зустрічатися кілька разів. Початком шляху є початок ребра, кінцем шляху - кінець ребра.
Шлях називається орієнтованої ланцюгом (або просто ланцюгом), якщо кожне ребро зустрічається в ньому не більше одного разу, і простий ланцюгом. якщо будь-яка вершина графа G инцидентна не більше ніж двом його ребрах.
Контур - шлях, в якому. Контур називається циклом, якщо він є ланцюгом, і простим циклом, коли це - проста ланцюг. Якщо граф містить цикли, то він містить і прості цикли. Граф, що не містить циклів, називається ациклічним.
Вершина називається досяжною з вершини, якщо існує шлях з початком і кінцем.
Орграф G називається зв'язковим, якщо він зв'язний без урахування орієнтації дуг, і сильно зв'язний, якщо з будь-якої вершини в будь-яку існує шлях.
Число ребер маршруту (шляху) називається його довжиною.
Відстань d (,) між вершинами і н-графа G називається мінімальна довжина простий ланцюга з початком і кінцем. Центром називається вершина н-графа, від якої максимальне з відстаней до інших вершин було б мінімальним. Максимальна відстань від центру G до його вершини називається радіусом графа r (G).
Ейлером цикл - цикл графа, що містить всі ребра графа. Ейлеров граф - граф, який має Ейлером цикл (Ейлером цикл можна вважати слідом пера, викреслювати цей граф, не відриваючись від паперу).
Теорема Ейлера. кінцевий неорієнтований граф G ейлерів тоді і тільки тоді, коли він зв'язний і ступеня всіх його вершини парних.
Ейлерова ланцюг - ланцюг, що включає всі ребра даного кінцевого н-графа G. однак вона має різні початок і кінець. Щоб в кінцевому н-графі G існувала ейлерова ланцюг, необхідні і достатні його зв'язаність і парність ступенів усіх вершин, крім початкової і кінцевої (і повинні мати непарні ступеня). Щоб в кінцевому орграфе існував Ейлером цикл, необхідні і достатні його зв'язаність, а так само рівність ступенів вершин цього графа по вхідних і виходять ребрах, тобто .
Гамильтонов цикл - простий цикл, що проходить через всі вершини даного графа. Гамильтонова ланцюг - простий ланцюг, що проходить через всі вершини графа, з початком і кінцем в різних вершинах.