Ноу Інти, лекція, операції над графами

Анотація: Наводяться основні операції над графами такі як об'єднання, перетин, кільцева сума, видалення вершини, видалення ребра, замикання і стягування. Ці операції розглядаються для представлення графів матрицями суміжності. Мета лекції: Дати уявлення про операції над графами і можливі способи їх подання до матричних структурах.

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

Об'єднання графів G1 і G2. позначається як, являє такий граф, що безліч його вершин є об'єднанням Х1 і Х2. а безліч ребер - об'єднанням A1 і A2. Граф G3. отриманий операцією об'єднання графів G1 і G2. показаний на рис. 2.1, д, а його матриця суміжності - на рис. 2.1, е. Матриця суміжності результуючого графа виходить операцією поелементного логічного додавання матриць суміжності вихідних графів G1 і G2.

Перетин графів G1 і G2. позначається як, являє собою граф. Таким чином, безліч вершин графа G4 складається з вершин, присутніх одночасно в G1 і G2. Операція перетину графів показана на рис. 2.2, в, а результуюча матриця суміжності виходить операцією поелементного логічного множення матриць суміжності вихідних графів G1 і G2. показана на рис. 2.2 .р.

Рис.2.2. Операція перетину і кільцевої суми: а - граф G1; б - граф G2; в - граф; г - матриця суміжності графа; д - граф; е - матриця суміжності графа

Кільцева сума двох графів G1 і G2. позначається як, являє собою граф G5. породжений на безлічі ребер. Іншими словами, граф G5 не має ізольованих вершин і складається тільки з ребер, присутніх або в G1. або в G2. але не в обох одночасно. Кільцева сума графів G1 і G2 показана на рис. 2.2, д, а результуюча матриця суміжності виходить операцією поелементного логічного додавання по mod 2 матриць суміжності вихідних графів G1 і G2. показана на рис. 2.2. Е.

Легко переконатися в тому, що три розглянуті операції комутативні т. Е., І багатомісних, т. Е.. і так далі.

Розглянемо унарні операції на графі.

Видалення вершини. Якщо хi -вершина графа G = (X, A). то G-хi -порожденний підграф графа G на множині вершин X-хi. т. е. G-хi є графом. вийшов після видалення з графа G вершини хi і всіх ребер, інцидентних цій вершині. Видалення вершини х3 показано на рис. 2.3, б (для вихідного графа, зображеного на рис. 2.3, а). Матриця суміжності вихідного графа представлена ​​на таблиці 2.1а). Результуюча матриця суміжності графа після виконання операції видалення вершини хi виходить шляхом видалення відповідного i - го стовпця і i -ої рядки з вихідної матриці і "стискання" матриці по вертикалі і горизонталі починаючи з (i + 1) - го стовпця і (i + 1 ) -ої рядки (таблиця 2.1б). Надалі елементи графа можуть бути переобозначив.

Видалення ребра або видалення дуги. Якщо ai - дуга графа G = (X, A). то G-ai - підграф графа G. що утворився після видалення з G дуги ai. Зауважимо, що кінцеві вершини дуги ai будуть збережені. Видалення з графа безлічі вершин або дуг визначається як послідовне видалення певних вершин або дуг. Видалення дуг a4 і a7 показано на рис. 2.3, в. Результуюча матриця суміжності графа після виконання операції видалення дуги ai виходить шляхом видалення відповідних елементів з вихідної матриці (таблиця 2.1в).