и, будемо спіратіся на следующие визначення.
Визначення. Графи и Рівні, если множини їхніх вершин и ребер, визначених через парі інцідентніх Їм вершин, збігаються. Например, графи, зображені на рис. 6.1 Рівні.
Задати граф - означає описати множини его вершин и ребер, а такоже відношення інцідентності. Колі граф - кінцевій, для его Опису й достатньо занумеруваті вершини и ребра.
Визначення. Граф назівається Повністю завданні у точному значенні, если нумерація его вершин и ребер зафіксована. Графи, что відрізняються только нумерацією, назіваються ізоморфнімі.
Пріведемо ще одне визначення ізоморфніх графів.
Визначення. Графи и ізоморфні если їхні вершини можна пронумеруваті таким чином, что ребро тоді и только тоді з єднує вершини и у графі, коли ребро з єднує вершини и у графі.
Приклад. Графи, зображені на рис. 5.7, (а), (б) - ізоморфні.
Малюнок 5.7 - ізоморфні графи
Приклад. На рис. 5.8 зображені графа - з п'ятьма вершинами в шкірному. Порівняті графи.
Малюнок 5.8 - Порівняння графів
розв язання:
Графи - - неорієнтовані графи, а - - орієнтовані.
Графи і - повні, причому =.
Граф НЕ є ПОВНЕ, того что незважаючі на те, что Кожна пара вершин з'єднана ребром, є петля.
Графи и є мультиграфом, того що містять кратні ребра.
Граф - має порожню множини ребер, всі вершини графа є ізольованімі.
Графи и є ДОПОВНЕННЯ друг до друга.
Графи и не є рівнімі, того что ребра 5 мают різній напрямок.
Граф - орієнтований мультіграф, того что має кратні ребра, у тієї годину як граф НЕ є мультиграфом, того что ребра 8 и 9 по-різному орієнтовані.
5.2 Способи Завдання графів
Як було сказано в п. 6.1 для Завдання графа необходимо занумеруваті вершини и ребра, а такоже Задати відношення інцідентності. Відношення інцідентності будемо опісуваті трьома способами: матриця інцідентності, матриць суміжності, списком ребер графа. Опішемо докладно Кожний з перерахованого способів.
Матриця інцідентності - це матриця розміром, де вертикально вказуються вершини, а горизонтально - ребра. На перетіні -того и -того рядків число дорівнює:
а) у випадка неорієнтованого графа
б) у випадка орієнтованого графа
Матриця суміжності - це квадратна матриця розміром, де вертикально и горизонтально вказуються вершини графа і. На перетінанні -того и -того рядків число дорівнює:
числу ребер, что з'єднують ЦІ вершини у випадка неорієнтованого графа;
числу ребер з качаном в -тій вершіні и кінцем в -тій вершіні у випадка орієнтованого графа.
Список ребер графа - це таблиця, что складається Із трьох рядків. У Першому перераховані всі ребра; у іншому и третьому - інцідентні Їм вершини:
у випадка неорієнтованого графа порядок вершин у рядку довільній;
у випадка орієнтованого графа Першів запісується вершина, де почінається ребро (другий рядок); вершина, де закінчується ребро, запісується у третій рядок.
Для нумерації вершин и ребер графа Використовують різній символьний записів: рімські, арабські цифри, що латінські букви.
Если графи Рівні, то їх матриці суміжності и інцідентності, а такоже список ребер, однакові.
Приклад.
Задати матрицю інцідентності и суміжності, а такоже списком ребер, неорієнтованій граф, збережений на Наступний малюнку.
розв язання:
Тут.
Список ребер
Ребро12345678910Вершинипочатокabaccdcdeeкінецьbccdddeefg
Як бачим, у кожному стовпці матриці інцідентності є только дві елєменти, відмінніх від нуля (або один, если ребро - петля).
Матриця суміжності симетричного относительно головної діагоналі.
Список ребер є найбільш компактним способом Завдання графів.
Кожний Із НАДАННЯ способів однозначно опісує граф, збережений на малюнку.
Приклад. Задати матрицю інцідентності, суміжності, списком ребер орієнтований граф, збережений на Наступний малюнку.
розв язання:
