111 lines
4.2 KiB
Markdown
111 lines
4.2 KiB
Markdown
---
|
||
id: 587d8256367417b2b2512c79
|
||
title: 接続行列
|
||
challengeType: 1
|
||
forumTopicId: 301644
|
||
dashedName: incidence-matrix
|
||
---
|
||
|
||
# --description--
|
||
|
||
グラフを表すもう一つの方法は、 <dfn>接続行列</dfn>に入れることです。
|
||
|
||
<dfn>接続行列</dfn> は二次元 (2D) 配列です。 一般に接続行列は、2 つの次元の間で 2 種類のクラスのオブジェクトを関連付けます。 このような行列は隣接行列に似ています。 しかし、行と列の意味がそれとは異なります。
|
||
|
||
グラフにはエッジとノードがあります。 この 2 つは、私たちが使う「オブジェクトの 2 種類のクラス」です。 この行列では、行がノード、列がエッジを表します。 したがって、行と列の数が違っていても構いません。
|
||
|
||
各列は一意のエッジを表します。 また、各エッジは 2 つのノードを接続します。 2 つのノードの間に 1 本のエッジがあることを示すために、特定の列の 2 行に 1 を入れます。 下に示したのは、ノード 1 とノード 3 の間に 1 本のエッジがある、3 ノードのグラフです。
|
||
|
||
<blockquote> 1<br> ---<br>1 | 1<br>2 | 0<br>3 | 1</blockquote>
|
||
|
||
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> を付けることもできます。 これまでに見てきたエッジは、単にエッジの有無が二項 (`0` または `1`) で表された、<dfn>重み付けされていない</dfn>エッジです。 用途によって重みを変えることができます。 異なる重みは 1 より大きい数字として表されます。
|
||
|
||
# --instructions--
|
||
|
||
5 つのノードと 4 本のエッジを持つ、無向グラフの接続行列を作成してください。 この行列は多次元配列でなければなりません。
|
||
|
||
これら 5 つのノードは次のような関係にあります。 1 本目のエッジは 1 番目と 2 番目のノードの間にあります。 2 本目のエッジは 2 番目と 3 番目のノードの間にあります。 3 本目のエッジは 3 番目と 5 番目のノードの間にあります。 4 本目のエッジは 4 番目と 2 番目のノードの間にあります。 すべてのエッジの重みは 1 であり、エッジの順序には意味があります。
|
||
|
||
# --hints--
|
||
|
||
`incMatUndirected` には 5 つのノードのみが含まれている必要があります。
|
||
|
||
```js
|
||
assert(
|
||
incMatUndirected.length === 5 &&
|
||
incMatUndirected
|
||
.map(function (x) {
|
||
return x.length === 4;
|
||
})
|
||
.reduce(function (a, b) {
|
||
return a && b;
|
||
})
|
||
);
|
||
```
|
||
|
||
1 番目と 2 番目のノードの間には 1 本目のエッジが必要です。
|
||
|
||
```js
|
||
assert(incMatUndirected[0][0] === 1 && incMatUndirected[1][0] === 1);
|
||
```
|
||
|
||
2 番目と 3 番目のノードの間には、2 本目のエッジが必要です。
|
||
|
||
```js
|
||
assert(incMatUndirected[1][1] === 1 && incMatUndirected[2][1] === 1);
|
||
```
|
||
|
||
3 番目と 5 番目のノードの間には、3 本目のエッジが必要です。
|
||
|
||
```js
|
||
assert(incMatUndirected[2][2] === 1 && incMatUndirected[4][2] === 1);
|
||
```
|
||
|
||
2 番目と 4 番目のノードの間には、4 本目のエッジが必要です。
|
||
|
||
```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]];
|
||
```
|