Files

camperbot 5c868af2b8 chore(i18n,learn): processed translations (#44851 )

2022-01-20 20:30:18 +01:00

4.2 KiB

Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d8256367417b2b2512c79	接続行列	1	301644	incidence-matrix

--description--

グラフを表すもう一つの方法は、接続行列に入れることです。

接続行列は二次元 (2D) 配列です。一般に接続行列は、2 つの次元の間で 2 種類のクラスのオブジェクトを関連付けます。このような行列は隣接行列に似ています。しかし、行と列の意味がそれとは異なります。

グラフにはエッジとノードがあります。この 2 つは、私たちが使う「オブジェクトの 2 種類のクラス」です。この行列では、行がノード、列がエッジを表します。したがって、行と列の数が違っていても構いません。

各列は一意のエッジを表します。また、各エッジは 2 つのノードを接続します。 2 つのノードの間に 1 本のエッジがあることを示すために、特定の列の 2 行に 1 を入れます。下に示したのは、ノード 1 とノード 3 の間に 1 本のエッジがある、3 ノードのグラフです。

1
---
1 | 1
2 | 0
3 | 1

4 本のエッジと 4 つのノードを持つ接続行列の例を示します。列はエッジ、行はノード自体であることを思い出してください。

1 2 3 4
--------
1 | 0 1 1 1
2 | 1 1 0 0
3 | 1 0 0 1
4 | 0 0 1 0

次のコードは、同じことを JavaScript で実装したものです。

var incMat = [
  [0, 1, 1, 1],
  [1, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 0]
];

有向グラフを作成するには、特定のノードを離れるエッジに -1 を使用し、ノードに入るエッジに 1 を使用します。

var incMatDirected = [
  [ 0, -1,  1, -1],
  [-1,  1,  0,  0],
  [ 1,  0,  0,  1],
  [ 0,  0, -1,  0]
];

グラフのエッジに重みを付けることもできます。これまでに見てきたエッジは、単にエッジの有無が二項 (0 または 1) で表された、重み付けされていないエッジです。用途によって重みを変えることができます。異なる重みは 1 より大きい数字として表されます。

--instructions--

5 つのノードと 4 本のエッジを持つ、無向グラフの接続行列を作成してください。この行列は多次元配列でなければなりません。

これら 5 つのノードは次のような関係にあります。 1 本目のエッジは 1 番目と 2 番目のノードの間にあります。 2 本目のエッジは 2 番目と 3 番目のノードの間にあります。 3 本目のエッジは 3 番目と 5 番目のノードの間にあります。 4 本目のエッジは 4 番目と 2 番目のノードの間にあります。すべてのエッジの重みは 1 であり、エッジの順序には意味があります。

--hints--

incMatUndirected には 5 つのノードのみが含まれている必要があります。

assert(
  incMatUndirected.length === 5 &&
    incMatUndirected
      .map(function (x) {
        return x.length === 4;
      })
      .reduce(function (a, b) {
        return a && b;
      })
);

1 番目と 2 番目のノードの間には 1 本目のエッジが必要です。

assert(incMatUndirected[0][0] === 1 && incMatUndirected[1][0] === 1);

2 番目と 3 番目のノードの間には、2 本目のエッジが必要です。

assert(incMatUndirected[1][1] === 1 && incMatUndirected[2][1] === 1);

3 番目と 5 番目のノードの間には、3 本目のエッジが必要です。

assert(incMatUndirected[2][2] === 1 && incMatUndirected[4][2] === 1);

2 番目と 4 番目のノードの間には、4 本目のエッジが必要です。

assert(incMatUndirected[1][3] === 1 && incMatUndirected[3][3] === 1);

--seed--

--seed-contents--

var incMatUndirected = [

];

--solutions--

var incMatUndirected = [[1, 0, 0, 0],[1, 1, 0, 1],[0, 1, 1, 0],[0, 0, 0, 1],[0, 0, 1, 0]];

4.2 KiB Raw Permalink Blame History Unescape Escape