Ізоморфізм графів

Графи G₁=(V₁,E₁) і G₂=(V₂,E₂) називаються ізоморфними, якщо існує таке взаємно однозначне відображення  множини вершин V₁ на множину вершин V₂, що ребро (v,w)E₁ тоді і тільки тоді, коли ребро ( (v), (w))E₂. Відображення  називається ізоморфним відображенням або ізоморфізмом графа G₁ на граф G₂.

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

Відношення ізоморфізму є відношенням еквівалентності на сукупності графів.

Теорема 3.1. Графи G₁ та G₂ ізоморфні тоді і тільки тоді, коли матрицю суміжності (матрицю інцидентності) одного з цих графів можна одержати з матриці суміжності (матриці інцидентності) іншого графа за допомогою відповідних перестановок рядків та стовпчиків.

Планарні графи.

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

Критерій непланарності

· достатня умова — якщо граф містить дводольний підграф K3,3 або повний підграф K5, то він є не планарним;

· необхідна умова — якщо граф не планарний, то він повинен містити більше 4 вершин, ступінь яких більше 3, або більше 5 вершин ступеня 2.