Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Відношення на графах. Підграф. Ізоморфізм графів.
Мета: узагальнити поняття відношення на графах,
ознайомитись з його властивостями; сформувати
поняття підграфа, навчити досліджувати графи на
ізоморфність.
План
1. Відношення на графах.
2. Поняття підграфа. Ізоморфізм графів. Деякі класи
простих графів.
Відношення на графах.
Приклад 1. А={1;2;3;}, R≤, R={(1,1)(1,2)(2,3)(1,3)(3,1)} це відношення задає граф
Властивості матриць бінарних відношень.
1.Якщо R,Q ≤A×B, [R] = (), [Q] = (), то [RQ]= і [RQ]=. 0+0=0, 1+1=1+0=0+1=1.
Приклад 2.
[R]=, [Q] = – матриці відношення, тоді
[RQ]=[Р]+[Q]=
[RQ]=[R]•[Q]=
2.Якщо R ≤A×B, Q ≤B×C, то =[R][Q] де множини матриць є по звичайному правилу ,а сума добутків по П.1.
Приклад 3.
[R]= [Q] =, то
[RQ]=
3.Матриця оберненого відношення рівна транспонованій матриці відношення R.
Відношення на графах
1.Відношення R є рефлексивним, якщо має місце .При задані відношення графом, кожний елемент має петлю (матриця: всі елементи діагоналі є рівні 1) (мал. 1).
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
1 |
(мал. )
2.Віднлшення R є симетричним, якщо (a,b)R =>(b,a) R .
Матриця симетричного відношення є симетричною відносно головної діагоналі, a в графі для кожної дуги з в існує протилежно спрямована дуга з в (мал.2.).
|
0 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
(мал. )
3.Відношення R є транзитивним якщо з aRb і bRс =>aRc.
У графі транзитивного відношення R для пар дуг таких, що кінець першої співпадає з початком другої існує третя дуга, що має спільний початок з першою і спільний кінець з другою.
|
0 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
0 |
0 |
1 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
(мал. )
Відношення еквівалентності — рефлексивне, симетричне, транзитивне.
Приклад 3.
Дано множину А={1,2,3}, відношення R задане графом (мал. 4.) R={(2,2)(1,2)(1,3)(2,3)} R≤
( мал. )
Так як в матриці на головній діагоналі є нулі, і немає всіх петель у графі, відношення не рефлексивне. Матриця і дуги не є симетричні.
Є транзитивним, бо .
Відношення є антисиметричним, бо всі елементи поза головною діагоналлю нулі перевірити
Приклад 4. Відношення R Задане на множині A={a,b,c,d} задане графом (мал.5.)Побудувати степені відношення
(мал. )
Квадрат відношення множина побудувати використовуючи правило: в графі присутня дуга (x,y), якщо існує така вершина z, що правильні
xRz:zRy (мал.6.)
Оскільки (a,b) (b,a) => (a,a)
(b,a) (a,b) => (b,b)
(b,c) (c,d) => (b,a)
(a,b) (b,d) => (a,c)
( мал. )
Степінь можна побудувати: і (мал.7.)
(a,c) (c,d) => (a,d)
(a,a) (a,b) => (a,b)
(b,b)(b,c) => (b,c)
(мал. ) (b,b)(b,a) => (b,a)
Степінь і ZRY
Приклад 5.
Нехай орієнтований граф є на (мал.8.) задає відношення R: яким є дане відношення?
a) не є рефлексивне
б) не є симетричне aRb є, bRa немає
в) не є транзитивне бо aRb і bRa, відношення аRd
(мал. )
Поняття підграфа. Ізоморфізм графів. Деякі класи простих графів.
Означення:
Граф називається підграфом графа, якщо кожна вершина і кожне ребро графа є відповідно вершиною і ребром графа G.
Граф називається каркасом (остовом) графа є (каркасним підграфом) якщо він містить всі його вершини.
Приклад 6.
На (мал.9.) зображенні підграфи графа (г) (а,б,в), причому б) є його каркас.
(мал. 9)
Задати граф означає описати множини його вершин і ребер , а також відношення інцидентності .
Означення :
Граф називається повністю заданим, якщо нумерація його вершин і ребер зафіксована.
Графи, що відрізняються тільки нумерацією називаються ізоморфними. (Графи є ізоморфні, якщо їхні вершини можна пронумерувати таким чином, що ребро з’єднює вершину графі , коли ребро з’єднує у графі .
Приклад 7.
Графи а),б)—ізоморфні.
– ізоморфні
Граф називається регулярним, якщо всі його вершини мають один і той самий степінь. Регулярні графи в степені 3 називаються кубічними або трьохвалентними .
Відомим прикладом кубічного графа є граф Петерсона який показаний на малюнку .
Платоновим називається граф утворений вершинами і ребрами п’яти правильних многогранників – Платонових тіл: тетраедра, куба, октаедра.
Запитання для самоперевірки.
1. Які є властивості матриць бінарних відношень?
2. Як графічно зображується а) рефлексивне, б) симетричне,
в) транзитивне відношення?
3. Що таке підграф?
4. Який граф є повністю заданим?
5. Як виглядає граф Петерсона?
Література