Два графа називаються ізоморфними, якщо вони однакове число вершин (позначимо його n) і вершини кожного їх можна занумерувати так числами від 1 до n, що у першому графі дві вершини з'єднані ребром тоді і тільки тоді, коли вершини з такими ж номерами у другому графі з'єднані.
Як довести, що графи ізоморфні?
Як довести неізоморфність графів
- Різна кількість вершин або ребер
- Різна кількість компонентів
- Ступені вершин у кожному графі
- Зміст абсолютно однакових підграфів
Як перевірити ізоморфізм?
Визначення Два графи ізоморфні, якщо за допомогою перейменування вершин та ребер їх можна зробити однаковими. У ізоморфних графів одні й самі властивості, що виражаються в термінах теорії графів – наприклад, однакове число вершин, ребер, висячих ребер, петель, вершин певної міри.