111 lines
5.0 KiB
Markdown
111 lines
5.0 KiB
Markdown
---
|
||
id: 587d8256367417b2b2512c79
|
||
title: Матриця інцидентності
|
||
challengeType: 1
|
||
forumTopicId: 301644
|
||
dashedName: incidence-matrix
|
||
---
|
||
|
||
# --description--
|
||
|
||
Граф можна представити ще й іншим способом — помістити його в <dfn>матрицю інцидентності</dfn>
|
||
|
||
<dfn>Матриця інцидентності</dfn> — це двовимірний масив. У цілому, цей термін використовують на позначення двох різних класів об'єктів між двома вимірами. Цей тип матриці має схожі властивості з матрицею суміжності. Однак тут рядки та стовпці означають дещо інше.
|
||
|
||
Графи мають ребра та вершини. Це і є "два різних класи об'єктів". Відповідно рядки в цій матриці відповідають вершинам, а стовпці — ребрам. А отже, ми можемо мати непарну кількість рядків та стовпців.
|
||
|
||
Кожний стовпець представляє відповідне ребро. Крім того, кожне ребро з'єднує дві вершини. Щоб показати, що між двома вершинами є ребро, помістіть 1 у два рядки певного стовпця. Нижче розташований граф, що складається з трьох вершин та одного ребра між вузлами 1 та 3.
|
||
|
||
<blockquote> 1<br> ---<br>1 | 1<br>2 | 0<br>3 | 1</blockquote>
|
||
|
||
Ось приклад матриці інцидентності `incidence matrix` з 4-ма ребрами та 4-ма вершинами. Пам'ятайте, стовпці — це ребра, а рядки — вершини.
|
||
|
||
<blockquote> 1 2 3 4<br> --------<br>1 | 0 1 1 1<br>2 | 1 1 0 0<br>3 | 1 0 0 1<br>4 | 0 0 1 0</blockquote>
|
||
|
||
Нижче видно реалізацію попереднього прикладу в JavaScript.
|
||
|
||
```js
|
||
var incMat = [
|
||
[0, 1, 1, 1],
|
||
[1, 1, 0, 0],
|
||
[1, 0, 0, 1],
|
||
[0, 0, 1, 0]
|
||
];
|
||
```
|
||
|
||
Щоб створити орієнтований граф, використовуйте `-1` для ребра, який виходить з певної вершини, і `1` для ребра, що входить у вершину.
|
||
|
||
```js
|
||
var incMatDirected = [
|
||
[ 0, -1, 1, -1],
|
||
[-1, 1, 0, 0],
|
||
[ 1, 0, 0, 1],
|
||
[ 0, 0, -1, 0]
|
||
];
|
||
```
|
||
|
||
Графи також можуть мати <dfn>ваги</dfn> для своїх ребер. Поки що ми маємо <dfn>незважені</dfn> ребра, де наявність і відсутність ребра є бінарним елементом (`0` або `1`). Ваги можуть бути різними в залежності від застосування. Різна вага представлена у вигляді чисел більших за 1.
|
||
|
||
# --instructions--
|
||
|
||
Створіть матрицю інцидентності для неорієнтованого графа з 5-ма вершинами та 4-ма ребрами. Вона повинна бути в багатовимірному масиві.
|
||
|
||
Ці 5 вершин розташовані в такому порядку. Перше ребро лежить між першою та другою вершинами. Друге ребро знаходиться між другою та третьою вершинами. Між третьою та п'ятою вершинами — третє ребро. А четверте ребро — між четвертою та другою вершинами. Вага ребер дорівнює 1, причому їх порядок також важливий.
|
||
|
||
# --hints--
|
||
|
||
`incMatUndirected` має містити виключно 5 вершин.
|
||
|
||
```js
|
||
assert(
|
||
incMatUndirected.length === 5 &&
|
||
incMatUndirected
|
||
.map(function (x) {
|
||
return x.length === 4;
|
||
})
|
||
.reduce(function (a, b) {
|
||
return a && b;
|
||
})
|
||
);
|
||
```
|
||
|
||
Між першою та другою вершинами повинне бути перше ребро.
|
||
|
||
```js
|
||
assert(incMatUndirected[0][0] === 1 && incMatUndirected[1][0] === 1);
|
||
```
|
||
|
||
Між другою і третьою вершинами має бути друге ребро.
|
||
|
||
```js
|
||
assert(incMatUndirected[1][1] === 1 && incMatUndirected[2][1] === 1);
|
||
```
|
||
|
||
Третє ребро повинне бути між третьою та п'ятою вершинами.
|
||
|
||
```js
|
||
assert(incMatUndirected[2][2] === 1 && incMatUndirected[4][2] === 1);
|
||
```
|
||
|
||
Четверте ребро повинне бути між другою та четвертою вершинами.
|
||
|
||
```js
|
||
assert(incMatUndirected[1][3] === 1 && incMatUndirected[3][3] === 1);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
var incMatUndirected = [
|
||
|
||
];
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
var incMatUndirected = [[1, 0, 0, 0],[1, 1, 0, 1],[0, 1, 1, 0],[0, 0, 0, 1],[0, 0, 1, 0]];
|
||
```
|