Ізоморфні графи - студопедія

Два графа, які відрізняються лише нумерацією вершин і ребер називаються ізоморфними.

Вони можуть відрізнятися графічним зображенням і матрицями суміжності і інцидентності. Щоб переконатися, що два графа - це один і той же граф, необхідно і достатньо встановити взаємно однозначні відповідності між ними.

Необхідні умови, щоб два графа були ізоморфними:

1. Мають однакову кількість вершин і ребер

2. Вершини графів мають однакові ступеня.

Але виконання цих властивостей не є достатньою умовою для ізоморфізму графів.

Приклад: Побудувати граф ізоморфний графу з попереднього прикладу.

Шлях і цикл в графі

Шляхом в графі називається послідовність ребер, що веде від вершини до вершини.

Циклом називається шлях, у якого кінцеві і початкові вершини збігаються. Цикл називається простим, якщо він проходить через одну вершину один раз.

Довгою циклу називається кількість ребер в ньому.

Якщо у графа все прості цикли парної довжини, то граф не має жодного циклу непарної довжини.

Зв'язний граф є простим циклом тоді і тільки тоді, коли всі його вершини мають ступінь 2.

При видаленні з графа одного ребра може вийти як зв'язний, так і незв'язних граф.

Ребро АВ називається мостом. якщо при його видаленні вершини А і В залишаються незв'язними.

Тут будь-ребро є мостом

1. Ребро АВ є мостом, якщо АВ єдиний шлях, що з'єднує вершину А з В.

2. АВ є мостом, коли ребро АВ не належить жодному циклу.

3. АВ. є мостом, якщо знайдеться дві вершини С1 і С2 такі, що шлях їх з'єднує проходить через АВ.