 |
|
Операції над графами та перетворення графів
Об’єднанням графів G1=(V1,E1) та G2=(V2,E2) (позначається G1ÈG2) називається граф виду (V1ÈV2,E1ÈE2). Якщо графи G1=(V1,E1) та G2=(V2,E2) такі, що V1ÇV2=Æ, то G1ÈG2 називається диз’юнктивним об’єднанням G1 та G2.
Нехай, наприклад, G1=({a,b,c},{(a,b),(a,c)}), G2=({a,b,c,d},{(a,d),(b,a), (c,d)}). Тоді G1ÈG2=({a,b,c}È{a,b,c,d},{(a,b),(a,c)}È{(a,d),(b,a),(c,d)}) =({a,b, c,d},{(a,b),(a,c),(a,d),(c,d)}).
Розглянемо приклад диз’юнктивного об’єднання графів. Нехай G1=({a,b,c},{(a,b),(a,c)}), G2=({1,2,3,4},{(1,4),(2,3),(3,1)}). Оскільки {a,b,c}Ç{1,2,3,4}=Æ, то G1ÈG2=({a,b,c,1,2,3,4},{(a,b),(a,c),(1,4),(2,3),(3,1)}) – диз’юнктивне об’єднання графів G1 та G2.
Перерізом графів G1=(V,E1) та G2=(V,E2) (позначається G1ÇG2) називається граф виду (V,Е1ÇЕ2).
Різницею графів G1=(V,E1) та G2=(V,E2) (позначається G1\G2) називається граф виду (V,E1\E2).
Доповненням графу G=(V,E) (позначається G¢) називається граф виду (V,V(2)\E).
Нехай, наприклад,
G1=({a,b,c,d}, {(a,c),(a,d),(b,c),(c,c),(d,c)}),
G2=({a,b,c,d}, {(a,a),(b,c),(c,a),(c,d)}).
Тоді G1ÇG2=({a,b,c,d}, {(a,c),(b,c),(d,c)}),
G1\G2=({a,b,c,d},{(a,d),(c,c)}),
G2\G1=({a,b,c,d},{(a,a)}),
G1¢=({a,b,c,d},{(a,a),(a,b),(b,b),(b,d),(d,d)}),
G2¢=({a,b,c,d},{(a,b),(a,d),(b,b),(b,d),(c,c),(d,d)}).
Добутком графів G1=(V1,E1) та G2=(V2,E2) (позначається G1*G2) називається граф виду (V1*V2,E), множина ребер якого Е визначається такою умовою:
та 
або
та 
.
Нехай, наприклад,
G1=({a,b,c},{(a,a),(a,c),(b,c)}),
G2=({1,2,3},{(1,2),(1,3)}).
Тоді G1*G2=({<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>,<c,1>,<c,2>,<c,3>}, {(<a,1>,<a,1>),(<a,1>,<a,2>),(<a,1>,<a,3>),(<a,1>,<c,1>),(<a,2>,<a,2>),
(<a,2>,<c,2>),(<a,3>,<a,3>),(<a,3>,<c,3>),(<b,1>,<b,2>),(<b,1>,<b,3>), (<b,1>,<c,1>),(<b,2>, <c,2>), (<b,3>,<c,3>),(<c,1>,<c,2>),(<c,1>,<c,3>)}).
Вилучення вершини. Нехай G=(V,E) – граф, vÎV. Вилучення вершини v з графа G визначається таким чином: G-v=(V\{v}, E\{(v,u)|(v,u)ÎE}). Нехай, наприклад, G=({a,b,c,d},{(a,b),(a,c),(b,d),(b,c)}). Тоді
G-a=({a,b,c,d}\{a},{(a,b),(a,c),(b,d),(b,c)}\{(a,b),(a,c)})=({b,c,d},{(b,d), (b,c)});
G-b=({a,b,c,d}\{b},{(a,b),(a,c),(b,d),(b,c)}\{(a,b),(b,d),(b,c)})= ({a,c,d},{(a,c)}).
Уведення вершини. Нехай G=(V,E) – граф, vÏV. Уведення вершини v у граф G визначається таким чином: G+v=(VÈ{v},E}). Нехай, наприклад, G=({a,b,c,d},{(a,b),(a,c),(b,d),(b,c)}). Тоді G+f=({a,b,c,d}È{f},E)=({a,b,c,d,f},E).
Вилучення ребра. Нехай G=(V,E) – граф, еÎE. Вилучення ребра е з графа G визначається таким чином: G-е=(V, E\{е}). Нехай, наприклад, G=({a,b,c,d},{(a,b),(a,c),(b,d),(b,c)}), е=(a,c). Тоді:
G-е=({a,b,c,d},{(a,b),(a,c),(b,d), (b,c)}\ {(a,c)})=({a,b,c,d}, {(a,b),(b,d),(b,c)}).
Уведення ребра. Нехай G=(V,E) – граф, u,vÎV, u та v несуміжні. Уведення ребра е=(u,v) у граф G визначається таким чином: G+е=(V,EÈ{е}). Нехай, наприклад, G=({a,b,c,d},{(a,b),(a,c)}). У цьому графі вершини а та d несуміжні, отже, можна увести в G ребро е=(a,d). Маємо: G+е=({a,b,c,d}, {(a,b),(a,c)}È{(a,d)})=({a,b,c,d},{(a,b),(a,c),(a,d)}).
Уведення вершини у ребро. Нехай G=(V,E) – граф, uÏV, (v,w)ÎE. Щоб увести вершину u у ребро (v,w) графу G, потрібно: а) вилучити ребро (v,w) з графу G; нехай G1=G-(v,w); б) увести вершину u у граф G1: G2=G1+u; в) увести у граф G2 ребра (u,v) та (u,w): G3=(G2+(u,v))+(u,w). Нехай, наприклад, G=({a,b,c,d},{(a,b),(a,c),(b,d),(b,c)}). Уведемо вершину е у ребро (a,c). Маємо:
G1=G-(а,с)=({a,b,c,d},{(a,b),(b,d),(b,c)}); G2=G1+е=({a,b,c,d,е},{(a,b),(b,d),(b,c)}); G3=(G2+(е,а))+(е,с)=({a,b,c,d,е},{(a,b),(b,d),(b,c),(е,а),(е,с)}).
Ототожнення вершин. Нехай G=(V,E) – граф, v,wÎV. Щоб ототожнити вершини v та w графу G потрібно:
а) якщо вершини v та w суміжні, то вилучити ребро (v,w) й покласти G1=G-(v,w), інакше покласти G1=G;
б) побудувати множини См(v)={x| xÎV,(v,x)ÎE}, См(w)={x| xÎV,(w,x)ÎE};
в) вилучити вершини v та w з графу G1: G2=(G1-v)-w;
г) увести вершину u у граф G2: G3=G2+u;
д) послідовно увести у граф G3 ребра виду (u,x), де x Î См(v)ÈСм(w).
Нехай, наприклад, G=({a,b,c,d},{(a,d),(a,c),(b,d),(b,c)}). Ототожнимо вершини a та b графу G. Оскільки a та b несуміжні, то G1=G; См(a)={d,c}, См(b)={d,c}, См(a)ÈСм(b)={d,c}; G2=(G1-a)-b=({c,d},Æ). Оскільки серед вершин графу G2 немає вершини a, то можемо увести a у G2: G3=G2+a=({а,c,d},Æ); тепер слід послідовно увести в G3 ребра (a,d) та (a,c): G4=(G3+(a,d))+(a,c)=({a,d,c},{(a,d),(a,c)}).
Стягування ребра. Нехай G=(V,E) – граф, (v,w)ÎE. Щоб стягнути ребро (v,w), потрібно ототожнити кінці цього ребра, тобто вершини v та w графу G. Нехай, наприклад, G=({a,b,c,d},{(a,d),(a,c),(b,d),(b,c)}). Стягнемо ребро (a,c) графу G. Спочатку вилучимо ребро (a,c): G1=G-(a,c) =({a,b,c,d},{(a,d),(b,d),(b,c)}). Знайдемо вершини, суміжні відповідно з a та c: См(a)={d}, См(c)={b}. G2=(G1-a)-c=({b,d},{(b,d)}). Оскільки серед вершин графу G2 немає a, то можемо увести a у G2: G3=G2+a=({а,b,d},{(b,d)}); тепер слід послідовно увести в G3 ребра (a,d) та (a,b): G4=(G3+(a,d))+(a,b) = ({a,b,d}, {(a,d),(a,b),(b,d)}).
Контрольні питання
1. Що таке: а) неорієнтований граф, б) вершина графу, в) ребро графу,
г) петля, д) порядок графу, е) степінь вершини графу?
2. За якої умови: а) ребро е графу інцидентне вершині v цього графу,
б) ребра е1 та е2 графу суміжні, в) вершини u та v графу суміжні?
3. Що таке: а) кінцева вершина графу, б) ізольована вершина графу,
в) кінцеве ребро графу?
4. Що таке: а) порожній граф, б) тривіальний граф, в) простий граф,
г) псевдограф, д) повний граф, е) граф Kn, є) однорідний граф?
5. Що таке степінь однорідного графу?
6. Які властивості має: а) простий граф скінченного порядку, б) простий скінченний однорідний граф?
7. Що таке: а) матриця суміжності графу, б) матриця інцидентності графу?
8. Як подати граф у вигляді діаграми?
9. Що таке: а) об’єднання (диз’юнктивне об’єднання, переріз, різниця, добуток) графів, б) доповнення графу?
10. Як здійснюється вилучення вершини (уведення вершини, уведення вершини в ребро, вилучення ребра, уведення ребра, стягування ребра, ототожнення вершин) графу?
Задачі та вправи
І. Побудувати неорієнтований граф:
1) з 4 вершинами та 5 ребрами; 2) з 5 вершинами та 4 ребрами;
3) з 5 вершинами та 5 ребрами; 4) з множиною вершин N;
5) з множиною вершин Z; 6) з множиною вершин R;
7) з множиною вершин {a,b,c} та мінімально можливою кількістю ребер;
8) з множиною вершин {a,b,c} та максимально можливою кількістю ребер;
9) у якому ребер удвічі більше, ніж вершин;
10) у якому вершин утричі більше, ніж ребер.
ІІ. Для заданого графу визначити: а) які вершини суміжні, б) які ребра суміжні, в) які вершини та ребра інцидентні, г) степінь кожної вершини, д) чи має граф кінцеві вершини, е) чи має граф ізольовані вершини, є) порядок графу.
1) ({1,2,3},{(1,2),(3,2)});
2) ({1,2,3,4,5},{(1,3),(1,4),(2,4),(2,5),(3,4),(4,5)});
3) ({1,2,3,4,5,6},{(1,2),(1,6),(2,3),(4,3),(4,5),(5,6)});
4) ({1,2,3,4},{(1,2),(1,3),(1,4),(2,3),(2,4),(4,3)});
5) ({1,2,3,4,5},{(1,4),(2,4),(4,5),(4,3),(1,1),(3,3)});
6) ({1,2,3,4,5,6},{(1,2),(1,5),(3,4),(5,6),(6,2)});
7) ({1,2,3,4,5,6,7,8,9},{(1,2),(2,7),(7,1),(7,9),(5,6),(8,7)});
8) ({1,2,3},{(1,1),(1,2),(2,3),(3,3)});
9) ({1,2,3},{(1,2),(1,1),(2,2),(2,3),(3,3)});
10) ({1,2,3,4,5,6},{(1,4),(5,2),(3,6)});
11) ({1,2,3,4,5,6},Æ);
12) ({1,2,3,4,5,6,7},{(1,2),(2,3),(3,4),(3,5),(5,7),(6,4)}).
ІІІ. Визначити, які із заданих у п.ІІ графів є: а) порожніми, б) простими, в) повними, г) повними простими, д) однорідними.
IV. Побудувати усі прості однорідні графи порядку: 1) 4, 2) 5, 3) 6.
V. Для кожного з графів п.ІІ побудувати: а) матрицю суміжності, б) матрицю інцидентності, в) діаграму.
VI. Задано графи G1=({1,2,3},{(1,2),(2,3)}), G2=({1,2,3},{(1,3),(2,1)}), G3=({0,1},{(0,0),(0,1)}). Обчислити: G1ÈG2, G1*G3, G2*G3, G3*G2, G3*G1, G1ÈG3, G2ÈG3, G1ÇG2, G1\G2, G2\G1, G1¢, G2¢, G3¢.
VII. Сформулювати правила побудови:
1) діаграми графу за його матрицею суміжності (й навпаки);
2) діаграми графу за його матрицею інцидентності (й навпаки);
3) матриці інцидентності графу за його матрицею суміжності (й навпаки).
VIII. Чому дорівнює степінь кожної вершини: а) повного графу порядку n, б) повного простого графу порядку n?
IX. Скільки ребер містить: а) повний граф порядку n, б) повний простий граф порядку n?
X. Чи існує повний простий граф, у якого кількість ребер дорівнює: а) 15, б) 18, в) 199…900…0 (n дев’яток, n нулів, nÎN), г) 8k2+2k, kÎN+?
XI. Нехай G – простий граф порядку n. Чому дорівнює степінь вершини v у графі G¢, якщо у графі G: а) n(v)=1, б) n(v)= n-1, в) n(v)=0, г) n(v)= k (kÎN)?
ХІІ. Чому дорівнює кількість ребер у графі G¢, якщо граф G має n вершин та k ребер (k,nÎN)?
ХІІІ. Нехай графи G1=(V,E1), G2=(V,E2) подано матрицями суміжності. Сформулювати правила побудови матриць суміжності графів G1ÈG2, G1ÇG2, G1\G2, G1¢ за матрицями суміжності графів G1 та G2.
ХІV. Як за допомогою матриці суміжності графу G визначити: а) порядок графу G, б) кількість ребер графу G, в) степінь n(v) певної вершини v графу G, г) чи є G повним д) чи є G простим повним графом?
ХV. Скільки ребер має простий граф порядку n степеня 2?
ХVІ. Чи існує простий граф порядку n, усі вершини якого є кінцевими, якщо: а) n=10, б) n=11, в) n=2k-1, г) n=2k?
ХVІІ. Скільки вершин може мати простий граф, усі вершини якого є кінцевими? Скільки ребер у такому графі?
ХVІІІ. Чи можна з повного простого графу K17 вилучити деякі ребра так, щоб степінь кожної вершини дорівнював: а) 15, б) 2, в) 1?
ХІХ. У певному товаристві з n осіб кожен знайомий з рівно k іншими особами. Чи можливе таке товариство для: а) n=5, k=2, б) n=5, k=3, в) n=2m, k=1, г) n=2m, k=3?
ХХ. Побудувати простий граф з п’ятьма вершинами, у якому тільки дві вершини мають однакові степені.
ХХІ. У графі порядку 5 лише дві вершини мають однакові степені. Чи можуть обидві ці вершини мати степінь 0 або степінь 4?
ХХІІ. Нехай G – простий граф порядку n, що має лише дві вершини з одна-ковими степенями. Скільки вершин з однаковими степенями має граф G¢?
ХХІІІ. Чи існує простий граф порядку 6, степені яких дорівнюють:
а) 2,3,3,4,4,4, б) 2,2,2,4,5,5?
ХХІV. Довести твердження.
1) Нехай А – матриця суміжності графу G порядку n. Довести, що i-й діагональний елемент матриці А2 дорівнює степеню i-ї вершини графу G, 1£i£n.
2) Нехай В – матриця інцидентності графу G порядку n. Довести, що і-й діагональний елемент матриці ВВТ дорівнює степеню і-ї вершини графу G, 1£i£n.
3) Нехай А – матриця суміжності, а В – матриця інцидентності простого графу G. Довести, що матриця А дорівнює матриці, яка утворюється з матриці ВВТ шляхом заміни усіх діагональних елементів нулями.
4) Нехай у простому графі порядку n з m ребрами є p вершин степеня t, а усі інші вершини мають степінь t+1. Довести, що p=(t+1)n-2m.
5) У футбольному турнірі беруть участь 29 команд. Довести, що у будь-який момент знайдеться команда, що зіграла парну кількість матчів.
6) Довести, що у будь-якому простому графі порядку n (n³2) завжди знайдуться принаймні дві вершини з однаковими степенями.
7) Довести, що у простому графі порядку 6 завжди знайдуться три вершини, що є або попарно суміжними, або попарно несуміжними.
8) Нехай G – граф. Довести, що (G¢)¢=G.