Page 22 - 4386

максимальна кількість дорівнює n!⋅m!) Якщо після однієї із них

матриці інцидентності тотожно збіжаться, то графи ізоморфні.

Як в першому, так і в другому випадку це досить

трудомісткі операції і рішення задачі “вручну” не завжди

виправдано. Найчастіше ізоморфність графів простіше

встановити з їхніх графічних подань.

Під інваріантом графа G розуміють числовий параметр,

пов’язаний з G, значення якого однакові для всіх графів

ізоморфних G. Деякі найпростіші інваріанти є такими:

1. Ізоморфні графи мають однакову кількість вершин.

2. Ізоморфні графи мають однакову кількість ребер.

3. Ізоморфні графи для довільного k (k≥0) мають однакову

кількість вершин степеня k.

21