Ізоморфні графи

Графи є ізоморфними, якщо вони мають однакову кількість вершин і однакові зв’язки. Тут ми не аналізуватимемо точне математичне визначення (його можна знайти, наприклад, тут), а лише інтуїтивну ідею. Уявімо собі вершини графа як дерев’яні кілочки, а ребра – як гумки між ними. Ми можемо переміщати кілочки та гумки, і це все один і той самий графік, тому що зв’язок між змінними зберігається. Ізоморфізм графів належить саме до цього типу «однаковості». Чи ми можемо рухатися за допомогою одного графіка стільки, щоб з нього отримати інший?

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