7. Для кожного з наступних бінарних відносин досліджувати, чи є воно всюди певним, функціональним; відповідь обгрунтувати.
8. Вказати всі сюр'ектівние відображення безлічі А = на безліч B =. Чи існують ін'єкційних відображення А в В?
9. Знайти всі відображення безлічі А = в себе, вкажіть, які з них ін'єкційних, сюр'ектівние.
10. Нехай f - відображення кінцевого безлічі А в себе. Доведіть, що f ін'єкційних тоді і тільки тоді, тоді f сюр'ектівно.
література
5. Практичне заняття № 5
Тема: «Елементи графа. Способи завдання графа. Підграфи.
ізоморфізм »
Мета заняття:
засвоєння таких понять, як граф, вершини і ребра графа, орієнтований і неорієнтований граф, мультіграф, псевдографом, суміжність, инцидентность, ізоморфізм, матриці суміжності і інцидентності, двочастковий граф, повний граф, підграф, ступінь вершини.
Пояснення до роботи
Час виконання практичного завдання - 2 години.
1. Керуючись наведеним теоретичним матеріалом, відповісти на наступні питання:
Які вершини графа називаються суміжними?
У чому полягає поняття инцидентности?
Як задається матриця інціденцій для орграфа?
Який граф називається псевдографом?
Який граф називається дводольним?
2. Дати визначення таких понять:
3. Виконати завдання для аудиторних занять.
4. Виконати завдання для самостійної роботи.
5.1. елементи графа
Граф G - це сукупність двох множин: непорожньої безлічі вершин V = v 1, v 2. vn> і безлічі ребер (дуг) Е = е 1, е 2. еn>. Таким чином, G = (V. Е), V ¹ Æ, Е Ì V × V.
Якщо (v 1, v 2) - впорядкована пара (т. Е. Дуга), то v 1 називається початком, a v 2 - кінцем дуги е. Якщо v 1, v 2> - невпорядкована пара, то ребро е називається неорієнтованим. Всякому графу G можна поставити у відповідність співвіднесений неорієнтовані граф G з тими ж множинами V і Е і інцидентності, але все пари невпорядковані. Такий граф називається асоційованим. Вершина, що не инцидентная жодному ребру, називається ізольованою. Вершина, инцидентная рівно одному ребру, і саме це ребро називаються кінцевими або висячими. Ребро з співпадаючими кінцями називається петлею. Дві вершини, інцидентні одному і тому ж ребру, називаються суміжними. Два ребра, інцидентні одній і тій же вершині, називаються суміжними. Ребра, яким поставлена у відповідність одна і та ж пара вершин, називаються кратними або паралельними.
Граф, що містить кратні ребра, називається мультиграфом. Неорієнтоване ребро графа еквівалентно двом протилежно спрямованим дуг, що з'єднує ті ж самі вершини. Граф з кратними ребрами і петлями називається псевдографом.
На рис. 3 зображені: орієнтований псевдографом, що має 7 вершин і 6 дуг, і неорієнтований мультіграф, що має 4 вершини і 5 ребер. Проілюструємо деякі введені поняття.
Для орграфа (рис. 3а): v 1, v 2, v 3, v 4, v 5, v 6. v 7 - вершини (вузли); v 5 - ізольована вершина; v 1, v 4 - кінцеві (висячі) вершини; v 2 і v 3, v 2 і v 1 - пари сусідніх вершин; е 1, е 2, е 3, е 4, е 5, е 6 - орієнтовані ребра (дуги); е 2 і е 3 - паралельні (кратні) дуги; е 2 і е 1 - суміжні дуги; е 6 -петлі для орграфа.
Для графа (рис. 3б): v 1, v 2, v 3, v 4 - вершини; v 4 - кінцева (висяча) вершина; v 2 і v 3, v 2 і v 1 - пари сусідніх вершин; е 1, е 2, е 3, е 4, е 5 - ребра (дуги); е 4 і е 5 - паралельні (кратні) ребра; е 2 і е 3 - суміжні ребра; петель немає.
5.2. Способи завдання графів
1. Перерахування (список) ребер графа із зазначенням їх кінців і додаванням списку ізольованих вершин.
2. Матриця суміжності A = (aij) визначається однаково для орієнтованого і неорієнтованого графів. Це квадратна матриця порядку n. де n - число вершин, у якій
Матрицею інцидентності B = (bij) орієнтованого графа називається матриця (n 'm), де n - число вершин, m - число ребер, у якій
Для неорієнтованого графа матриця інцидентності B задається наступним чином:
Петлі відповідає елемент, рівний 2.
Матриці суміжності та інцидентності графа, зображеного на рис. 3а. мають вигляд (рис. 4):
3. Для наочності граф представляють у вигляді геометричного об'єкта: вершин відповідають різні виділені точки в просторі (на площині), ребрах - відрізки кривих, що зв'язують вершини.
Розглянемо деякі різновиди графів.
Неорієнтовані граф G = (V. E) - двочастковий, якщо безліч його вершин V можна розбити на два такі підмножини V 1 і V 2, що кожне ребро має один кінець в V 1, а інший в V 2. Якщо ж кожна з вершин класу V 1 пов'язана ребром з кожною вершиною класу V 2, то граф називається повним дводольним і позначається до m, n, де m = | V 1 |, n = | V 2 |. На рис. 5а зображений двочастковий граф, на рис. 5б і 5в - повні дводольні графи До 3,2 і К 3,3.
Повним графом називається граф без кратних ребер (і іноді без петель), в якому будь-які дві вершини з'єднані ребром (орієнтованим або неорієнтованим). Повний неорієнтовані граф з n вершинами позначається Кn. Очевидно, граф Кn містить n (n - 1) / 2 ребер.
На рис. 6а. 6б і 6в зображені графи До 3, До 4, К 5, відповідно. На рис. 6г також зображений повний граф.
5.3. підграфи
Граф G ¢ = (V ¢, E ¢) називається подграфом графа G = (V, Е). позначення: G ¢ Í G. якщо V ¢ Í V. Е ¢ Í Е і для множин V 'і Е' зберігаються інціденцій графа G. При цьому, очевидно, кожне ребро з Е 'входить в підграф G ¢ разом зі своїми кінцями. Подграф називається власним. якщо він відмінний від самого графа.
Приклад. Графи на рис. 7б і 7в є подграфа графа на рис. 7а.
5.4. ізоморфізм графів
Два графа G 1 = (V 1, E 1) і G 2 = (V 2, E 2) ізоморфні, якщо між їх вершинами існує взаємно однозначна відповідність j: V 1 ® V 2 таке, що для будь-якої пари вершин u, v з V 1 ребро (u, v) Î Е1 «ребро (j (u), j (v)) Î Е2.
Приклад. Графи, зображені на рис. 8, є ізоморфними.
Ізоморфні графи відрізняються тільки нумерацією вершин. Матриці суміжності двох ізоморфних графів можуть бути отримані одна з іншої перестановкою рядків і стовпців. Щоб дізнатися, чи є два графа ізоморфні, потрібно зробити всі можливі перестановки рядків і стовпців матриці суміжності одного з графів. Якщо після якої-небудь перестановки вийде матриця суміжності другого графа, то ці графи ізоморфні. Щоб переконатися, що графи неізоморфних, треба виконати всі n. можливих перестановок рядків і стовпців.
5.5. Ступені вершин графа
Ступенем вершини v графа G називається число d (v) ребер графа G. інцідентних вершині v. Вершина графа, що має ступінь 0, називається ізольованою, а ступінь 1 - висячої.
У разі неорієнтованого псевдографом вважається, що внесок кожної петлі, инцидентной деякої вершини v. в d (v) дорівнює 2 (тоді як внесок будь-якого іншого ребра, інцидентні вершині v. дорівнює 1).
Полустепені результату (заходу) вершини v орграфа D називається число d + (v) (d- (v)) дуг орграфа D. виходять з вершини v (що входять в вершину v).
У разі орієнтованого псевдографом внесок кожної петлі, инцидентной деякої вершини v. в d (v) дорівнює 1, як в d + (v), так і в d- (v).
У графі G (рис. 3б) ступінь вершини v 1 дорівнює чотирьом, т. Е. D (v 1) = 4; вершина v 4 - висяча, так як d (v 4) = 1. В орієнтованому псевдографом (рис. 3а) ступінь вершини v 6 дорівнює трьом, т. е. d (v 6) = d + (v 6) + (d- (v 6) = 2 + 1 = 3; вершина v 1 - висяча, так як d (v 1) = 1, вершина v 5 - ізольована, так як d (v 5) = 0.
Для аудиторних занять
1. Дано реалізації графів (рис. 9). Які це графи? Описати їх основні характеристики. Привести приклади елементів графів.