Page 49 - 2577

за діаметром або не є двозв’язним, то вилучаються ребро e , та додаються ребра з
M i 1 
номерами від i  1 до i . Якщо x   2 задає двозв’язаний граф з діаметром d  3, то із
M 1  M 0 i 1
числа ребер з номерами від i до i  1 вибирається i i   1 ребер, після вилучення яких
M 0 M M 0 M
отримаємо двозв’язаний граф з діаметром d 1  3 і М ребрами. Якщо неможливо вилучити
i i   1, то вектор x   2 задає граф, який не задовільняє обмеження на діаметр або не є
M 0 M i
двозв’язаним. У цьому випадку вилучається ребро e і додаються ребра з номерами від
M i  2
i + 1 до i і т.д. Процес закінчується, коли не існує розв’язку задачі на множині ребер з
M  2 M 0
номерами від i  1 до i .
1 M 0
В процесі генерації для кожного графа провіряють необхідні та достатні умови
двозв’язаності.
Критерій двозв’язаності. Граф G = G(V,E) є двозв’язаним тоді і тільки тоді, коли для
V
будь – якої вершини v  виконана умова
deg   v   G v   M  N  2, (3.5)
де G v   – цикломатичне число графа G – v.

Оскільки G v   за визначенням число додатне, то умову (3.5) можна замінити на
іншу
deg   v  M  N  2. (3.6)
Якщо VG , E  – каркасний граф двозв’язаного графа G=(V,E), то для будь – якої
вершини v виконується нерівність
deg   v   G   v  M  N  2. (3.7)
Якщо граф задовільняє умови (3.5) – (3.7), то він двозв’язаний з діаметром d 3.
Наведений алгоритм генерує двозв’язані графи з діаметром d  3 для довільного
1
числа ребер. Але використання нижньої границі числа ребер в графі дає можливість значно
скоротити число можливих варіантів розв’язку задачі оскільки відпадає необхідність у
дослідженні графів з М ребрами для M < M min.
Таким чином, стан проектування топологічної структури комп’ютерної мережі
включає в себе такі етапи:
- обчислення нижньої границі числа ребер в графі;
- генерація каркасних двозв’язаних підграфів заданого графа;
- обчислення нижньої оцінки вартості мережі;
- перевірка обмежень (3.1) – (3.4).
Отриманий алгоритм дає змогу вибрати оптимальну схему з’єднання вузлів
комунікації.

Контрольні питання та завдання

1. Дайте визначення кінцевого графа.
1. Які вершини і ребра графа будуть інцендентними?
2. Визначіть степені кожної із вершин графа, який показаний на рисунку.

46