tify"> Список ребер
Ребро12345678910Вершинипочатокaabbccdfffкінецьabacdeedeg
Відмінність матриці інцідентності орієнтованого графа від неорієнтованого складається у вказівці качана и кінця ребер. Матриця суміжності губити свою сіметрічність. У списку ребер Важлива порядок вказівки вершин, что з'єднують зазначену ребром (від качана до кінця).
Як відзначалося вищє, всі розглянуті Способи Завдання графів однозначно визначаються граф. Вінікає питання: чи можливо відновіті граф за завданням матриці інцідентності, суміжності або списку ребер? Очевидна позитивна відповідь.
За матриці інцідентності число ребер и вершин візначається з розмірності матриці: число ребер графа дорівнює числу стовпців, а число вершин - числу рядків матриці.
За матриці суміжності число вершин візначається з розмірності матриці. Як було відзначено, матриця суміжності н-графа симетричного относительно головної діагоналі, и Кількість ребер візначається верхнім правимо трикутником матриці, розташованім над головною діагоналлю, включаючі залишуся. Тобто, число ребер н-графа дорівнює сумі елементів, розташованіх на головній діагоналі и у верхньому правому трикутнику.
У матриці суміжності орграфа сіметрія відсутня, а число ребер дорівнює сумі всех елементів матриці суміжності.
Список ребер є скороченню варіантом матриці інцідентності. Кількість ребер очевидна, а Кількість вершин дорівнює максимальному номеру всех перерахованого вершин зі списком.
Тобто, матриця інцідентності и список ребер по суті, еквівалентні, то знаючи матрицю інцідентності можна Записатись список ребер, и навпаки.
Побудова матриці інцідентності за списком ребер. Коженая рядок списку ребер відповідає рядку в матриці інцидентності з тім же номером.
Для неорієнтованого графа в шкірному рядку списку ребер зазначені номери елементів матриці інцидентності, Рівні 1 (всі Інші Елементи - нулі).
Для орієнтованого графа Першів вказується вершина, что відповідає качана ребра (у матриці інцидентності - елемент), а другий - відповідному кінцю ребра (у матриці інцидентності - елемент 1).
При збігу елементів у рядку списку ребер, у відповідному рядку матриці інцидентності запісується число, відмінне від, 0, 1, например, 2. Така ситуация відповідає наявності у графі петель.
Приклад. Побудуваті матрицю інцідентності неорієнтованого графа за списком ребер:
Ребро12345678Вершініпочатокadecadbfкінецьdffebcff розв язання.
Матриця інцідентності, відповідно до списку ребер, має вигляд:
Приклад.
Запіcаті список ребер відповідно до матриці інцідентності орієнтованого графа:
розв язання:
Список ребер, Записаний відповідно до матриці інцідентності орієнтованого графа має вигляд:
Ребро12345678Вершініпочатокbbccddeaкінецьaccddeff
У візначенні уведение Поняття ізоморфніх графів. Чи можливо Встановити, чи є графи ізоморфнімі за їхнімі матриці інцідентності, суміжності, або списку ребер?
Для перевіркі ізоморфності графів и за матрицею суміжності та патенти візначіті, чі існує така перестановка рядків и стовпців у матриці суміжності, щоб у результате Вийшла матриця. Із цією метою треба сделать всі Можливі перестановки рядків и стовпців (а їхня максимальна Кількість дорівнює?)! Если после однієї Із ціх перестановок матриці суміжності тотожня збіжаться, то графи ізоморфні.
Для перевіркі ізоморфності графів и за матрицею інцідентності (і списку ребер) та патенти візначіті, чі існує така перестановка рядків и стовпців у матриці інцідентності, щоб у результате Вийшла матриця. Із цією метою треба сделать всі Можливі парі перестановок рядків и стовпців (а їхня максимальна Кількість дорівнює)! Если после однієї Із ціх перестановок матриці інцідентності тотожня збіжаться, то графи ізоморфні.
І в дере, и в іншому випадка це й достатньо трудомісткі операции, и решение задачі вручну НЕ всегда віправдано. Найчастіше ізоморфність графів простіше Встановити з їх графічних Поданєв.
5.3 Зв язність графа. Маршрути, шляхи, ланцюги, циклі
5.3.1 G - неорієнтованій граф
Визначення. Маршрутом (путем) у графі назівається така послідовність ребер, у Якій кожні дві сусідніх ребра и мают Загальну вершину. У маршруті ті самє ребро может зустрічатіся кілька разів. Іншімі словами маршрут - це сукупність ребер, Які об'єднані разом вершинами так, что можна...
