Реферат на тему:
Підграфи. Ізоморфізм графів. Алгебра графів
Граф 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
Нашли опечатку? Выделите и нажмите CTRL+Enter
