UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
Назва Підграфи. Ізоморфізм графів. Алгебра графів (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2703
Скачало300
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Граф 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 вершинами кожний, необхідно здійснити

різноманітні одночасні перестановки рядків і стовпчиків однієї з них.

Якщо після чергової з таких перестановок дістанемо матрицю, яка повністю

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ