ЯК з матриці побудувати граф :: Наука

В інформатиці графом називають геометричне представлення безлічі точок (вершин) і ліній (ребер), що пов'язують всі або частину з даних точок. Наявність або відсутність зв'язку (ребра) у графі, а також спрямованість з'єднання (її орієнтованість, виродження в петлю) описується в спеціальних матрицях графів - інцінденцій і суміжності. За будь-якої з даних матриць можна побудувати граф, використовуючи відповідні визначення.

Інструкція

Графи бувають орієнтованими і неорієнтованими. У першому випадку ребра, що з'єднують вершини графа, задають напрямок руху стрілкою на одному зі своїх кінців. Якщо ребро починається і закінчується в одній і тій же вершині, воно вироджується в петлю. Всі дані умови графа явно задаються в матриці інцінденцій. Матриця смежностей містить лише інформацію про наявність зв'язку між вершинами графа, не розкриваючи її особливостей.

Побудуйте граф по матриці інцінденцій. Для цього порахуйте кількість рядків n і стовпців m в заданій матриці. Рядки відповідають вершинам графа, а стовпці - ребрах. На вільному просторі листа відзначте вершини споруджуваного графа гуртками, їх буде стільки, скільки рядків містить матриця інцінденцій. Пронумеруйте вершини від 1 до n.

Розбір матриці краще здійснювати за стовпцями, визначаючи таким чином наявність зв'язку між вершинами і її напрямок. Переглядаючи перший стовпець зверху вниз, шукайте значення відмінне від нуля. При знаходженні числа -1 або 1 запам'ятайте, в якому рядку воно розташоване, і шукайте другу одиницю в тому ж стовпці. Виявивши обидва числа, проведіть на графі лінію, що сполучає дві вершини з номерами зазначених рядків. Якщо одне зі знайдених значень було -1, значить, граф є орієнтованим - вкажіть на лінії направляючу стрілку до тієї вершини, де в матриці знаходиться -1. Якщо обидва значення описані одиницями, отже, споруджуваний граф неорієнтований і його ребра не мають напрямки. Якщо в стовпці виявлено число 2, проведіть петлю в вершині, відповідної позиційної рядку матриці. Нульові значення вказують на відсутність зв'язку. Розгляньте аналогічним чином інші стовпці і відображуватимете на малюнку всі задані ребра графа.

Побудуйте граф по матриці суміжності. Дана матриця є квадратною, тому число її рядків дорівнює числу стовпців і відповідає кількості вершин у графі. На аркуші намалюйте гуртки-вершини по числу термін матриці. Розбір матриці суміжності краще проводити, рухаючись по рядку. Починаючи з першого рядка зліва направо, шукайте значення відмінні від нуля. Знайшовши 1 (або інше ненульове число) зауважте його поточну позицію в рядку і стовпці. На графі проведіть лінію між вершинами, що відповідають поміченими рядку і стовпцю. Тобто якщо 1 стоїть на перетині 2 рядки і 3 стовпці матриці суміжності, ребро графа з'єднає 2 і 3 його вершини. Продовжіть пошук ненульових значень до кінця матриці суміжності і заповніть граф аналогічним чином.