Операції над множинами | Правила рішення рівнянь і систем рівнянь з одним невідомим в алгебрі множин. | Завдання до виконання роботи | Основні відомості про графах | Способи завдання графів | Можливості підключення в графах | розфарбування графа | Завдання до виконання роботи | Стійкі безлічі вершин графа | Диз'юнктивна і Кон'юнктивна нормальні форми |

загрузка...
загрузка...
На головну

Фундаментальні цикли графа

  1. II. 11. Наведіть принципову схему установки і поясніть, як в лабораторній роботі визначали чутливість осцилографа.
  2. II. 9. Поясніть принцип дії електронного осцилографа.
  3. Б. Внести фундаментальні зміни в теорію і практику міжнародних відносин, яких дотримується уряд, який перебуває при владі в Росії.
  4. біогеохімічні цикли
  5. Великі цикли Н. Д. Кондратьєва та їх роль в інноваційному менеджменті.
  6. Бу к?штері ?ондир?иларини? (БК?) термодінамікали? ціклин есептеу
  7. Буття і небуття як фундаментальні категорії онтології.

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

Остовно підграф графа - це підграф, що містить всі вершини графа.

кістяком називається остовно підграф, що є деревом.

Хордою остова D в зв'язковому графі G називається всяке ребро графа, що не належить D.

Будь-підграф, що складається з хорди і остова, має точно один цикл.


рис.3

На рис.3 показаний граф і його остовне підграфи, що є деревом. Остов не містить циклів. Щоб побудувати остов графа, потрібно в графі ліквідувати всі цикли (викидаючи з графа відповідні ребра). Ребра остова забезпечують його мінімальну зв'язність, тобто, якщо з остова видалити будь-ребро, він розпадається на дві зв'язні компоненти графа. Якщо граф має n вершин, то його остов завжди має (п-1) ребро.

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

V (G) = R- (N-1), де R - число ребер графа; N - число вершин графа.

Цикломатичне число V {G} визначає зв'язність графа.

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

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

На перетині i-го рядка і j-ro стовпця ставиться одиниця, якщо ребро j входить в фундаментальний цикл, утворений додаванням до остову ребра i, і ставиться нуль - в іншому випадку. Кожен рядок матриці є фундаментальний цикл, представлений у вигляді довічного вектора. Будь не фундаментальну цикл графа може бути отриманий підсумовуванням за модулем 2 деякого числа фундаментальних циклів.

Матриця фундаментальних циклів для графа на Рис.3 а) має вигляд:

 Сф (G) =  з m d a b e f g h  
 
1

 

 хорди
 рис.4



Визначення чисел стійкості графа | Завдання до виконання роботи
загрузка...
© um.co.ua - учбові матеріали та реферати