2014-02-02
759
Ранг графа визначається як 
, де n – число вершин, k – число компонент зв'язності графа. Коранг графа, або цикломатичний| ранг, є 
, де m – число ребер.
Ранг-поліном графа G має вигляд|вид|
,
де 
– ранг графа G, а 
– коранг| остовного| (тобто що включає всі вершини графа) підграфа H, а 
– його ранг. Підсумовування ведеться по всіх остовным| підграфах графа G.
Ранг поліном служить для аналізу безлічі остових| підграфів. Так, наприклад, коефіцієнт при 
в 
є число підграфів розміру k, а значення 
рівне числу підграфів (включаючи невласний підграф), ранг яких рівний рангу самого графа.
Приклад|зразок| 12.8. Знайти ранг-поліном графа, зображеного|змальованого| на мал. 12.8.
Рішення|розв'язання,вирішення,розв'язування|. Знайдемо всіх 16 остових| підграфів графа G (мал. 12.9). Множину|безліч| представимо|уявимо| у вигляді чотирьох графів розміру 1 (тобто з|із| одним ребром), шести графів розміру 2, чотирьох графів розміру 3 і двох невласних графів (порожній|пустий| граф і граф G).
Мал. 12.9
Враховуючи, що ранг 
графа рівний 3, одержуємо|отримуємо| суму:
