しりとり《オイラーグラフ》

グラフ構造の入力メニュー【頂点の出現回数・オイラーグラフ・準オイラーグラフ・(入出)次数・しりとり】

問題【STEP: 1】頂点の出現回数・無向グラ
Task
無向グラフ内の指定された頂点 v が m 個の辺のうちいくつの辺に現れるか求めてね。

【STEP: 1】コード 1 ( 隣接行列 )

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
      Matrix[b][a]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M, V] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
  // console.log(Matrix);  // [ [ 0, 1, 0 ], [ 1, 0, 1 ], [ 0, 1, 0 ] ]
   const num_of_Apex = Matrix[V -1].reduce((acc, cur) => acc + cur);
   console.log(num_of_Apex);
});
hogeちゃんの画像

配列 Matrix (N ✕ N の 2次元配列) は 無向グラフの隣接行列です。

Matrix[V -1] の値を足し算すれば 頂点の出現回数 と一致しました。

top

【STEP: 1】コード 2 ( 隣接リスト )

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b);
      List[b].push(a);
   }
   const List = [];  // 隣接リスト
   const [N, M, V] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
   const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   console.log(List[V - 1].length);
});
hogeちゃんの画像

配列 List (N 行 の 2次元配列) は 無向グラフの隣接リストです。

頂点の出現回数は各行の要素数と一致しました。

top
問題【STEP: 2】次数・無向グラフ
Task
無向グラフ の 各頂点の 次数 を出力してね。

【STEP: 2】コード 1 ( 隣接行列 )

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
      Matrix[b][a]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
  // console.table(Matrix);
   const degree = new Array(N);  // 各頂点の次数
   for (let i = 0; i < N; i++) {
      degree[i] = Matrix[i].reduce((acc, cur) => acc + cur);
   }
   console.log(...degree);
});
hogeちゃんの画像

次数…各頂点を接続している辺の数。
隣接行列の行の値を足し合わせて次数を求めています。

top

【STEP: 2】コード 2 ( 隣接リスト )

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b);
      List[b].push(a);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
   const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   const degree = new Array(N);  // 各頂点の次数
   for (let i = 0; i < N; i++) {
      degree[i] = List[i].length;
   }
   console.log(...degree);
});
hogeちゃんの画像

List[i].lengthで 次数 を 求めることができました。

top
問題【STEP: 3】オイラーグラフ・無向グラフ
Task
連結な無向グラフ で 全ての辺を一筆書きして最初の頂点に戻ることができるか判定してね。

【STEP: 3】コード 1

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
      Matrix[b][a]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
  // console.table(Matrix);
   let Eulerian_graph = true;
   for (let i = 0; i < N; i++) {
      const edges = Matrix[i].reduce((acc, cur) => acc + cur);
      if (edges % 2) {
         Eulerian_graph = false;
      }
   }
   console.log(Number(Eulerian_graph));
});
hogeちゃんの画像

連結なグラフ…どの 2 つの頂点間も辺をたどって行き来ができるグラフ。

一筆書き(閉じた線)できる…すべての頂点の次数が偶数。

top

【STEP: 3】コード 2 ( 隣接リスト )

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b);
      List[b].push(a);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }

   for (let i = 1; i <= M; i++) {
   const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   let Eulerian_graph = true;
   for (let i = 0; i < N; i++) {
      const edges = List[i].length;
      if (edges % 2) {
         Eulerian_graph = false;
      }
   }
   console.log(Number(Eulerian_graph));
});
hogeちゃんの画像

頂点 I の次数は List[i].length。

top
問題【STEP: 4】準オイラーグラフ・無向グラフ
Task
連結な無向グラフ で 全ての辺を一筆書きできるか判定してね。(最初≠最後でもOK)

【STEP: 4】コード

reader.on('close', () => {
   function adjacency_Matrix(a, b) {  // 隣接行列の値を更新
      Matrix[a][b]++;
      Matrix[b][a]++;
   }
   const Matrix = [];  // 隣接行列
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
  // console.table(Matrix);
   let degree = 0;
   for (let i = 0; i < N; i++) {
      edges = Matrix[i].reduce((acc, cur) => acc + cur);
      if (edges % 2) {
         degree++;
      }
   }
   console.log(degree === 2 || degree === 0 ? 1 : 0);
});
hogeちゃんの画像
一筆書きできる…次数が奇数である頂点数が 0 または 2 。
top
問題【STEP: 5】頂点の出現回数・有向グラフ
Task
有向グラフ の頂点 a_1 〜 a_m と b_1 〜  b_m の頂点 v に等しいものの個数 を 出力してね。

【STEP: 5】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M, V] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
  // console.table(List);
   const outdegree = List[V - 1].length;
   let indegree = 0;
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (List[i][j] === V) {
            indegree++;
         }
      }
   }
   console.log(outdegree, indegree);
});
hogeちゃんの画像

有向グラフ…辺に向きがつけられているグラフ。

top
問題【STEP: 6】入出次数・有向グラフ
Task
有向グラフ の 入次数 と 出次数を出力してね。

【STEP: 6】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
  // console.table(List);
   const outdegree = new Array(N);
   const indegree = new Array(N).fill(0);
   for (let i = 0; i < N; i++) {
      outdegree[i] = List[i].length;
      for (let j = 0; j < List[i].length; j++) {
         for (let k = 1; k <= N; k++) {
            if (List[i][j] === k) {
               indegree[k - 1]++;
            }
         }
      }
   }
   console.log(...indegree);
   console.log(...outdegree);
});
hogeちゃんの画像

入次数…頂点 i に向かっている辺の個数。

出次数…頂点 i から出ている辺の個数。

top
問題【STEP: 7】オイラーグラフ・有向グラフ
Task
有向グラフの すべての辺を一筆書きして最初の頂点に戻ってくることができるか判定してね。

【STEP: 7】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
  // console.table(List);
   const outdegree = new Array(N);
   const indegree = new Array(N).fill(0);
   let weakly_connected = true;
   for (let i = 0; i < N; i++) {
      outdegree[i] = List[i].length;
      for (let j = 0; j < List[i].length; j++) {
         for (let k = 1; k <= N; k++) {
            if (List[i][j] === k) {
               indegree[k - 1]++;
            }
         }
      }
   }
   for (let i = 0; i < N; i++) {
      if (outdegree[i] !== indegree[i]) {
         weakly_connected = false;
      }
   }
   console.log(Number(weakly_connected));
});
hogeちゃんの画像

一筆書き(条件)…全ての頂点の入次数と出次数が一致する。

top
問題【STEP: 8】準オイラーグラフ・有向グラフ
Task
弱連結な有向グラフで すべての辺を一筆書きできるか判定してね。

【STEP: 8】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
  // console.table(List);
   const outdegree = new Array(N);
   const indegree = new Array(N).fill(0);
   let one_stroke = true;
   for (let i = 0; i < N; i++) {
      outdegree[i] = List[i].length;
      for (let j = 0; j < List[i].length; j++) {
         for (let k = 1; k <= N; k++) {
            if (List[i][j] === k) {
               indegree[k - 1]++;
            }
         }
      }
   }
   const obs_1 = [0, 0];
   for (let i = 0; i < N; i++) {
      if (outdegree[i] !== indegree[i]) {
         one_stroke = false;
      }
      if (outdegree[i] - indegree[i] === 1) {
         obs_1[0]++;
      }
      if (indegree[i] - outdegree[i] === 1) {
         obs_1[1]++;
      }
   }
   if (obs_1[1] === 1 && obs_1[1] === 1) {
      one_stroke = true;
   }
   console.log(Number(one_stroke));
});
hogeちゃんの画像

弱連結…無向グラフとしてみた場合どの頂点間も辺をたどって行き来できる。

top
問題【FINAL】しりとり
Task
与えられたすべての文字列を 1 回ずつ使用して しりとりを 完結できるか判定してね。

【FINAL】コード

reader.on('close', () => {
   function Word_Chain(a, b) {
      alphabet[a].push(b);
   }
   const alphabet = [];  // 隣接リスト
   for (let i = 0; i < 26; i++) {
      alphabet.push([]);
   }
   const a = 'a'.codePointAt();
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      const S = lines[i];
      const L = S.length - 1;
      const s_f = S[0].codePointAt() - a;
      const s_l = S[L].codePointAt() - a;
      Word_Chain(s_f, s_l);
   }
   const outdegree = new Array(26);
   const indegree = new Array(26).fill(0);
   let chain = true;
   for (let i = 0; i < 26; i++) {
      outdegree[i] = alphabet[i].length;
      for (let j = 0; j < alphabet[i].length; j++) {
         for (let k = 0; k < 26; k++) {
            if (alphabet[i][j] === k) {
               indegree[k]++;
            }
         }
      }
   }
   const obs_1 = [0, 0];
   for (let i = 0; i < 26; i++) {
      if (outdegree[i] !== indegree[i]) {
         chain = false;
      }
      if (outdegree[i] - indegree[i] === 1) {
         obs_1[0]++;
      }
      if (indegree[i] - outdegree[i] === 1) {
         obs_1[1]++;
      }
   }
   if (obs_1[1] === 1 && obs_1[1] === 1) {
      chain = true;
   }
   console.log(Number(chain));
  // console.log(indegree);
  // console.log(outdegree);
});
hogeちゃんの画像

アルファベットの文字コードナンバーを取得して 有向グラフ化しています。

top

コメント