Підграфи. Ізоморфізм графів. Алгебра графів (реферат)

Реферат на тему:

Підграфи. Ізоморфізм графів. Алгебра графів

Граф G1=(V1,E1) називається підграфом графа G =(V,E ), якщо V1 ?V i
E1 ?E.

Важливі класи підграфів складають підграфи, які отримуються в результаті
застосування до заданого графа операції вилучення вершини і/або операції
вилучення ребра.

Операція вилучення вершини v з графа G =(V,E ) полягає у вилученні з
множини V елемента v, а з множини E ( всіх ребер, інцидентних v.

Операція вилучення ребра e з графа G =(V,E ) ( це вилучення елемента e з
множини E. При цьому всі вершини зберігаються.

Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними, якщо існує таке
взаємно однозначне відображення ? множини вершин V1 на множину вершин
V2, що ребро (v,w)?E1 тоді і тільки тоді, коли ребро (? (v),? (w))?E2.
Відображення ? називається ізоморфним відображенням або ізоморфізмом
графа G1 на граф G2.

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

Ізоморфне відображення графа G на себе називається автоморфізмом графа
G. Автоморфізм ? графа G =(V,E ), при якому для кожної вершини v ?V
виконується ? (v)=v, називається тривіальним автоморфізмом.

Приклад 3.6. Пропонуємо переконатись, що всі графи, зображені на
рис.3.2, ізоморфні між собою, а графи на рис.3.3 ( не є ізоморфними.

G1 G2 G3

Рис.3.2

H1 H2

Рис.3.3

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

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

Доведення. Справді, як було зазначено вище, ізоморфні графи G1 і G2
відрізняються між собою лише порядком нумерації вершин, тобто існує
бієктивне відображення ( множини номерів вершин першого графа на множину
номерів вершин другого. Отже, кожен елемент aij(1) матриці суміжності A1
графа G1 збігається з елементом a((i)((j)(2) (тобто елементом, який
знаходиться в рядку з номером ((i ) і стовпчику з номером ( (j)) матриці
суміжності A2 графа G2. Таким чином, шляхом послідовного одночасного
обміну місцями (перестановок) рядків і стовпчиків з номерами i та ( (i )
для всіх i=1,2,…,n матрицю суміжності A1 можна перетворити у матрицю
суміжності A2 і навпаки.

Якщо відображення ( відоме, то таке перетворення виконати неважко. У
разі ж, коли потрібно перевірити за допомогою матриць суміжності, чи є
ізоморфними два задані графи з n вершинами кожний, необхідно здійснити
різноманітні одночасні перестановки рядків і стовпчиків однієї з них.
Якщо після чергової з таких перестановок дістанемо матрицю, яка повністю
збігається з іншою, то ці графи ізоморфні. Однак, щоб в такий спосіб
з’ясувати, що задані графи не є ізоморфними, потрібно виконати всі n!
перестановок рядків і стовпчиків. Вже для порівняно невеликих значень n
здійснити цей перебір практично неможливо навіть за допомогою
обчислювальної машини. У прикладній теорії алгоритмів розробляються
різноманітні алгоритми перевірки ізоморфізму графів, які для більшості
графів (або окремих типів графів) дозволяють суттєво скоротити обсяг
необхідних перевірок [2,7,8].

Для матриць інцидентності графів G1 і G2 з n вершинами і m ребрами
кожний справедливі аналогічні міркування. Відмінність у тому, що коли G1
і G2 ізоморфні, тоді для їхніх множин вершин існує бієкція (, а для
множин ребер ( інша бієкція (. Загальна ж кількість необхідних кроків
для перевірки ізоморфізму графів G1 і G2 у цьому випадку не перевищує
n!m!.

Граф G =(V,E ) називається повним, якщо будь-які дві його вершини
суміжні (тобто E=V  (2)). Повний граф з n вершинами позначається Kn.

Очевидно, що будь-яка підстановка множини вершин повного графа Kn є
автоморфізмом цього графа. Тому кількість усіх можливих автоморфізмів
графа Kn дорівнює n!

Для графів можна означити операції об’єднання, перетину і доповнення.

Об’єднанням графів G1=(V1,E1) і G2=(V2,E2) називається граф
G =(V1?V2,E1?E2); позначається G =G1?G2. Об’єднання G =G1?G2 називається
прямою сумою графів G1 i G2, якщо V1?V2=?.

Перетином і різницею графів G1=(V,E1) i G2=(V,E2) з однаковими множинами
вершин називаються графи G (=(V,E1?E2) i G ((=(V,E1\E2) відповідно;
позначаються G (=G1?G2 і G ((= G1\G2.

=Kn\G.

Таким чином можна означити алгебру графів A=<Г,{(, (,((}> (типу
(2,2,1)), носієм якої є множина Г всіх графів. Iснують й інші операції
для графів, отже, сигнатуру алгебри A можна розширювати.

Неважко переконатись у справедливості такого твердження.

2.

Приклад 3.7. Об’єднання і перетин графів H1 і H2 з попереднього прикладу
зображені на рис.3.4. Доповнення графів G2 i H2 зображені на рис.3.5.

H1(H2 H1?H2

Рис.3.4

2????????????

Рис.3.5

Список літератури

1. Харари Т. Теория графов.- М.,1973.

2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.

3. Зыков А.А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р. Введение в теорию графов.- М., 1977

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *