Як зробити граф

Як зробити граф

Граф складається з вершин і ребер. Вершини з’єднуються ребрами за певним властивості — відношенню інцидентності, яке і задає безліч ребер. При цьому можуть утворюватися петлі і ізольовані вершини.

Інструкція

  1. Нехай задано безліч ребер графа і задано співвідношення, за яким можна провести ребро від однієї вершини до іншої. Як приклад безліч вершин {1, 2, 3, 4, 5, 6, 7, 8}, дві вершини x і y полягають у відношенні x + y <8.
  2. Побудуйте матрицю суміжності вершин. Для цього побудуйте квадратну таблицю, число рядків і стовпців у таблиці співпадає з кількістю вершин. Потім поставте 1 на перетині i-го рядка і j-го стовпця, якщо вершини i та j задовольняють заданому співвідношенню. Поставте 0 на перетині i-го рядка і j-го стовпця, якщо співвідношення для відповідних елементів не виконується.

    У нашому прикладі перший рядок заповнюється наступним чином:

    1 +1 <8, значить на перетині першого рядка та 1-го стовпця коштує 1

    1 +2 <8, знову 1

    1 +3 <8, знову 1



    1 +7 <8, невірне нерівність, значить цим елементом таблиці буде 0

    1 +8 <8, знову 0
  3. Щоб дізнатися кількість ребер, підрахуйте кількість одиниць в матриці суміжності, при цьому варто не задваівать ребра.

    У прикладі вийшла симетрична матриця, тому підрахували спочатку одиниці вище головної діагоналі матриці (відзначені блакитним), а потім і одиниці на головній діагоналі (відмічені червоним). Загальна кількість ребер вийшло 12.
  4. Побудуйте матрицю інціденцій (ребер). Для цього накресліть таблицю, число рядків у ній дорівнює числу вершин графа, а число стовпців — кількості ребер. Проставте одиниці в тих рядках, які будуть з’єднані ребром. Ребра, що ведуть від вершини до неї ж, називають петлями і додають у кінець матриці. У стовпцях, відповідних петлям, варто тільки одна одиниця на відміну від інших ребер.
  5. Тепер накресліть граф. Додайте вершини на папері довільним чином і з’єднайте їх ребрами, використовуючи побудовані таблиці. Вершини, не з’єднані ребрами, називаються ізольованими.

Зверніть увагу

На малюнку позначені ребра для наочності. Звичайно ж над ребром пишуть вага ребра.