На головну

розрізи

  1. B. лампасние розрізи
  2. Геологічні карти і розрізи.
  3. Фасади і розрізи.

Поняття розрізу грає важливу роль при вивченні питань, пов'язаних з відділенням одного безлічі вершин графа від іншого. Такі завдання виникають, наприклад, при вивченні потоків в мережах (мережею називається зв'язний орграф G = потоком в мережі G називається функція, яка ставить у відповідність дуги деякий число-вагу дуги). У цих завданнях фундаментальну роль відіграють вивчення поперечних перерізів мережі (т. Е. Множин дуг, які з'єднують вершини двох непересічних множин вершин) і знаходження обмеженого поперечного перерізу, яке є найвужчим місцем. Ці вузькі місця визначають пропускну здатність системи в цілому.

Нехай G = - неорграф = розбиття множини M. розрізом графа G (по розподіленню) називається безліч всіх ребер, що з'єднують вершини з M1 з вершинами з M2 (Рис. 4.46). Відзначимо, що в зв'язковому графі будь-розріз непорожній.

Непорожній розріз K неорграфа G називається простим розрізом або коціклом, Якщо будь-який непорожній власне підмножина K? K не є розрізом, ні за яку розбиття. Іншими словами, з K можна видалити жодне ребро з тим, щоб безліч було непустою розрізом.



M? Розріз M?

Мал. 4.46

Теорема 4.12.1. В кінцевому неорграфе G = , Що має з компонент зв'язності, безліч ребер K тоді і тільки тоді є коціклом, коли граф має (c + 1) компонент зв'язності.

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

Наступні дві майже очевидні теореми дають інформацію про зв'язок кістяків з розрізами, а також циклів з розрізами.

Теорема 4.12.2. У зв'язковому неорграфе кістяк має принаймні одне спільне ребро з будь-яким з розрізів графа.

Теорема 4.12.3. У зв'язковому неорграфе будь-який цикл має з будь-яким розрізом парне число загальних ребер.

В умовах, зазначених у попередньому параграфі, розглянемо неорграф G з остовом T. Знову нехай гілки остова T. Видаляючи з остова T довільну гілка, отримуємо ліс c (c + 1) компонентами зв'язності, т. Е. Кожне ребро є розрізом остова T по деякого розбиття (рис. 4.47).



M? M?

Мал. 4.47

У графі G можуть знайтися ще якісь ребра (є хордами T), які з'єднують вершини з і. Безліч утворює простий розріз, який називається фундаментальним розрізом графа G щодо гілки остова T. Безліч всіх фундаментальних розрізів графа G називається фундаментальним безліччю коціклов графа G щодо остова T. Зазначимо, що потужність фундаментального безлічі коціклов не залежить від вибору остова T і дорівнює корангу *.

Аналогічно фундаментальним циклам кожному фундаментальному розрізу ставиться у відповідність вектор i , Який визначається за правилом

Фундаментальне безліч коціклов задається матрицею фундаментальних розрізів , рядки якої є векторами 1, 2, ..., v * (G):

.

Оскільки кожен фундаментальний розріз містить рівно одну гілку, а саме, матриця має вигляд

.

Таким чином, K =, де одинична матриця порядку. Відзначимо, що якщо C = відповідна матриця фундаментальних циклів, то = CT2.

П р и м і р 4.12.1. Знайдемо матрицю фундаментальних розрізів графа G = , Зображеного на рис. 4.45. Оскільки фундаментальних розрізів. Ребру 4 відповідає коцікл, так як при видаленні ребра 4 з остова T безліч вершин M розбивається на дві часті: і M \, а ребра 1 і 4 утворюють розріз по розподіленню. Аналогічно ребру 5 відповідає коцікл, ребру 6-коцікл, ребру 7-коцікл, ребру 8-коцікл. Отже, матриця фундаментальних розрізів має вигляд

.

§ 4.13. Векторні простору,



фундаментальні цикли | Пов'язані з графами

остови графів | Рішення завдання комівояжера | Впорядковані і бінарні дерева | розмальовки графів | Завдання і вправи |

© um.co.ua - учбові матеріали та реферати