В інформатиці графом називають геометричне представлення безлічі точок (вершин) і ліній (ребер), що зв 'язують всі або частину з даних точок. Наявність або відсутність зв 'язку (ребра) у графі, а також спрямованість з' єднання (її орієнтованість, виродження в петлю) описується в спеціальних матрицах графів - інцинденцій і суміжності. За будь-якою з даних матриць можна побудувати граф, використовуючи відповідні визначення.
Інструкція
1. Графи бувають орієнтованими і неорієнтованими. У першому випадку ребра, що з 'єднують вершини графа, задають напрямок руху стрілкою на одному зі своїх кінців. Якщо ребро починається і закінчується в одній і тій же вершині, воно вироджується в петлю. Всі дані умови графа явно задаються в матриці інцинденцій. Матриця суміжностей містить лише інформацію про наявність зв 'язку між вершинами графа, не розкриваючи її особливостей.
2. Побудуйте граф по матриці інцинденцій. Для цього порахуйте кількість рядків n і стовпчиків m у заданій матриці. Рядки відповідають вершинам графа, а стовпчики - ребрам. На вільному просторі аркуша позначте вершини споруджуваного графа гуртками, їх буде стільки, скільки рядків містить матриця інцинденцій. Пронумеруйте вершини від 1 до n.
3. Розбір матриці краще здійснювати по стовпцях, визначаючи таким чином наявність зв 'язку між вершинами і її напрямок. Переглядаючи перший стовпчик зверху вниз, шукайте значення, відмінне від нуля. Коли ви знаходите число -1 або 1, запам "ятайте, в якому рядку воно розташоване, і шукайте другу одиницю в тому самому стовпчику. Виявивши обидва числа, проведіть на графі лінію, що з 'єднує дві вершини з номерами зазначених рядків. Якщо одне зі знайдених значень було -1, значить граф є орієнтованим - вкажіть на лінії напрямну стрілку до тієї вершини, де в матриці знаходиться -1. Якщо обидва значення описані одиницями, отже, споруджуваний граф неорієнтований і його ребра не мають напряму. Якщо у стовпчику виявлено число 2, проведіть петлю у вершині, що відповідає позиційному рядку матриці. Нульові значення вказують на відсутність зв 'язку. Розгляньте подібний спосіб інші стовпчики і відобразіть на малюнку всі задані ребра графа.
4. Побудуйте граф по матриці суміжності. Ця матриця є квадратною, оскільки кількість її рядків дорівнює числу стовпчиків і відповідає кількості вершин у графі. На аркуші намалюйте гуртки-вершини за кількістю термін матриці. Розбір матриці суміжності краще проводити, рухаючись по рядку. Починаючи з першого рядка зліва направо, шукайте значення, відмінні від нуля. Знайшовши 1 (або інше ненульове число) зауважте його поточну позицію в рядку і стовпчику. На графі проведіть лінію між вершинами, що відповідають поміченим рядкам і стовпчику. Тобто. якщо 1 стоїть на перетині 2 рядки і 3 стовпчики матриці суміжності, ребро графа з 'єднає 2 і 3 його вершини. Продовжіть пошук ненульових значень до кінця матриці суміжності і заповніть граф аналогічним чином.