• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Неорієнтовані графи

Визначення 2.1. Граф — це сукупність непорожньої множини (точок) V і множини (ліній) Е, між якими визначено відношення відповідності (інцидентності) &, причому кожний елемент відповідає двом елементам , .

Елементи множини V називають вершинами графа G і позначають великими буквами А, В, С…, або цифрами 1, 2, … . Відповідно елементи множини Е називають ребрами і позначають (А; В), (А; С),…, (1; 2), (1; 3),… ,.

Графи, в яких множини Е і V — скінченні (порожня множина також розглядається як скінченна), називаються скінченними.

Зауважимо, що множина Е (але не V) може бути порожньою. Кажуть, що граф вироджений тоді і тільки тоді, коли він не має ребер.

Вершини, які не належать жодному ребру, називаються ізольованими. Отже, в виродженому графі всі вершини ізольовані.

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

Під паралельними розуміють ребра i , для яких і . Зокрема, дві петлі, інцидентні одній і тій вершині, є паралельними.

Кажуть, що вершини і суміжні, якщо існує хоча б одне ребро таке, що . Зокрема, вершина суміжна сама з собою, якщо існує петля, інцидентна ; в протилежному випадку не може бути суміжна сама з собою. Аналогічно ребра і називають суміжними, якщо вони мають, по крайній мірі, одну спільну граничну точку.

Зауважимо, що суміжність є відношенням між двома подібними елементами (між вершинами, або між ребрами), тоді як інцидентність є відношення між різнорідними елементами.

Визначення 2.2. Число ребер, інцидентних вершині (петля враховується двічі), називається степенем вершини і позначається .

Отже, вершина — ізольована, якщо . Зокрема, для всіх вершин виродженого графа .

Наголосимо на деякі властивості графів, пов'язані з поняттям степеня вершини:

а) в графі G сума степенів всіх його вершин — число парне і в два рази більше від числа його ребер;

б) число непарних вершин будь-якого графа — парне;

в) в будь-якому графі з n вершинами, де , завжди знайдуться хоча б дві вершини з однаковими степенями;

г) якщо в графі з n вершинами ( ) дві вершини мають однаковий степінь, то в цьому графі завжди знайдеться або одна вершина степеня 0, або одна вершина степеня ( ).

Проілюструємо сказане вище на графі, який зображений на рис.2.1.

Рис. 2.1.

Граничними точками ребра є вершини і . Петля має єдину граничну точку . Ребро суміжне з ребром і паралельне ребру . Вершина суміжна з і сама з собою. Вершини , , , мають парний степінь, а вершина є ізольованою і її степінь дорівнює нулю.

Визначення 2.3. Скінченна послідовність ребер графа , ,…, (не обов’язково різних) називається маршрутом довжини n, якщо існує послідовність , , ,…, , з (не обов’язково різних) вершин таких, що ,

Кажуть, що маршрут замкнутий, якщо і незамкнутий, якщо . В останньому випадку також кажуть, що маршрут з’єднує вершини і . Зауважимо, що одне ребро можна розглядати як маршрут довжиною 1.

Якщо всі ребра маршруту різні, а сам маршрут незамкнутий, то його називають ланцюгом і – циклом, якщо він замкнутий.

Якщо всі вершини , , ,…, — різні (очевидно, що в цьому випадку ребра різні), то відповідний ланцюг називається простим ланцюгом.

Якщо , а всі решта вершини різні, то послідовність ребер називається простим циклом.

Зауважимо, що якщо у графах всі прості цикли парної довжини, то граф не має жодного циклу непарної довжини.

Інколи в літературі ланцюг (простий ланцюг) називають ще шляхом (простим шляхом).

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

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

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

Граф G і його доповнення зображені на рис.2.2.

G

Рис. 2.2.

Число ребер повного графа дорівнює .

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

В іншому випадку граф називається незв’язним.

Визначення 2.5. Граф називається деревом, якщо він зв’язний і не має циклів.

Визначення 2.6. Граф, який не має циклів і складається з k дерев, називається лісом з k дерев.

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

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

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

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

Якщо дерево Т є підграфом графа G, то ребра G, які належать дереву Т, називають вітками дерева Т, а ребра, які не належать дереву Т — хордами відносно дерева Т.

Визначення 2.8. Ребро (А; В) графа G називається мостом, якщо в графі , що отримали з графа G в результаті видалення ребра (А, В) вершини А і В будуть незв’язними.

Таким чином, кожне ребро в дереві (лісі) є мостом.

Про граф, всі вершини якого належать дереву Т, кажуть, що дерево Т покриває граф G. Очевидно, що тільки зв’язні графи мають покриваючі дерева.

Рис. 2.3.

Дерева і – два різні покриваючі дерева для одного і того ж графа G. Той факт, що кожне з дерев і має по 4 ребра є наслідком загальної властивості дерев: кожне дерево з n вершинами має ребер; ліс із k дерев, який містить вершин має ребер.

Будь-які два дерева, які покривають один і той же граф, можна перетворити одне в одне, будуючи послідовність покриваючих дерев, кожне з яких відрізняється від попереднього одним ребром (рис. 2.4).

Рис.2.4.

Читайте також:

1. Henri Matisse- Биография художника на английском.
2. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
3. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
4. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
5. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
6. Биография населенного мира
7. Грамматико-орфографическая пропедевтика в период обучения грамоте.
8. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ОДНОИНДЕКСНЫХ ЗАДАЧ
9. Двочасткові графи
10. ДЕМОГРАФИЯ
11. Дифтонги i диграфи
12. Дробот В. Изучение биографии писателя в школе.- К., 1988.

Переглядів: 2684