三角形を作る《グラフ理論・木》

木のメニュー【木の入力の受け取り（隣接行列・隣接リスト）辺の有無の判定・ 葉の判定・木の中心・三角形を作る】

問題【STEP: 1】木の入力の受け取り（隣接行列）
Task
木の頂点・辺についての情報が与えられるので 隣接行列を出力してね。

【木の入力の受け取り(隣接行列)】コード

reader.on('close', () => {
   const adjacency_Matrix = (a, b) => {
      Matrix[a][b]++;
      Matrix[b][a]++;
   };
   const Matrix = [];  // 隣接行列
   const N = Number(lines[0]);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
// console.log(Matrix);
   Matrix.forEach(m => {
      console.log(m.join(' '));
   });
});
hogeちゃんの画像
用語がよくわからなかったのでyoutube動画参照しました。

Wikipedia様 の解説♪

top
問題【STEP: 2】木の入力の受け取り（隣接リスト）
Task
木の頂点・辺についての情報が与えられるので 隣接リストを出力してね。

【木の入力の受け取り(隣接リスト)】コード

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

隣接リストの解説はこちら(Wikipedi様)。

top
問題【STEP: 3】辺の有無の判定
Task
木の頂点・辺の情報与えられます。K 組の頂点に 辺が存在するか否か判定してね。

【辺の有無の判定】コード 1/2《隣接行列》

reader.on('close', () => {
   const adjacency_Matrix = (a, b) => {
      Matrix[a][b]++;
      Matrix[b][a]++;
   };
   const Matrix = [];  // 隣接行列  
   const [N, K] = lines[0].split(' ').map(Number);  // 頂点 N 個 判定したい辺 K 個
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);     
   }
   for (let i = N; i < N + K; i++) {
      const [qA, qB] = lines[i].split(' ').map(e => e - 1);
      console.log(Matrix[qA][qB]?'YES':'NO');
   }
});
hogeちゃんの画像

隣接行列を使ったらこんな感じ。

top

【辺の有無の判定】コード 2/2《隣接リスト》

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b + 1);
      List[b].push(a + 1);
   };
   const List = [];  // 隣接リスト
   const [N, K] = lines[0].split(' ').map(Number);  // 頂点 N 個 判定したい辺 K 個
   for (let i = 0; i < N; i++) {
      List[i] = [];
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   for (let i = N; i < N + K; i++) {
      const [qA, qB] = lines[i].split(' ').map(e => e - 1);
      console.log(List[qA].includes(qB + 1) ? 'YES' : 'NO');
   }
});
hogeちゃんの画像

隣接リストを使ったらこんな感じになりました。

top
問題【STEP: 4】葉の判定
Task
木の頂点・辺についての情報が与えられるので 葉の頂点の番号を出力してね。

【葉の判定】コード 1/2《隣接行列》

reader.on('close', () => {
   const adjacency_Matrix = (a, b) => {
      Matrix[a][b]++;
      Matrix[b][a]++;
   };
   const Matrix = [];  // 隣接行列
   const N = Number(lines[0]); 
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill(0);
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_Matrix(A, B);
   }
   for (let i = 0; i < N; i++) {
      if (Matrix[i].reduce((acc, cur) => acc + cur) === 1) {
         console.log(i + 1);
      }
   }
});
hogeちゃんの画像
葉は接続する辺が 1 本のみであるような頂点。だそうです。
top

【葉の判定】コード 2/2《隣接リスト》

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b + 1);
      List[b].push(a + 1);
   };
   const List = []; // 隣接リスト
   const N = Number(lines[0]);
   for (let i = 0; i < N; i++) {
      List[i] = [];
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   for (let i = 0; i < N; i++) {
      if (List[i].length === 1) {
         console.log(i + 1);
      }
   }
});
hogeちゃんの画像
隣接リストで葉の頂点番号を出力。
top
問題【STEP: 5】木の中心
Task
木の頂点・辺についての情報が与えられるので 木の中心である頂点の番号を出力してね。

【木の中心】コード 1/2《隣接行列》

reader.on('close', () => {
   const adjacency_matrix = (a, b) => {
      Matrix[a][b]++;
      Matrix[b][a]++;
   };
   const N = Number(lines.shift());
   const Matrix = [];  // 隣接行列
   const row = new Array(N).fill(0);
   for (let i = 0; i < N; i++) {
      Matrix.push([...row]);  // 隣接行列の行(N行)
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_matrix(A, B);
   }
   const points = new Array(N).fill(1);  // 添字 = 頂点番号 頂点が残っていれば 1
   let points_num = N;  // 頂点の数
   while (points_num > 2) {
      const leef = [];  // 葉に該当する頂点
      for (let i = 0; i < N; i++) {
         const L = Matrix[i].reduce((acc, cur) => acc + cur);  // 隣接行列の行の値を足し算した値
         if (L === 1) {  // L (i 行目の値のトータル) が 1 なら…
            leef.push(i);  // i は 葉に該当する      
            points[i] = 0;  // 葉に該当する頂点を除く
            points_num--;  // 頂点の総数が減る
         }
      }
      leef.forEach(y => {  // y は葉に該当する頂点
         const x = Matrix[y].indexOf(1);  // x は葉の枝でつながる頂点
         Matrix[y][x] = 0;  // y → x の枝を除く
         Matrix[x][y] = 0;  // x → y の枝を除く
      });
   }
   points.forEach((value, index) => {
      if (value) {
         console.log(index + 1);
      }
   });
});
hogeちゃんの画像

葉となっている頂点を木から順番に取り除く。。

top

【木の中心】コード 1/2《隣接リスト》

reader.on('close', () => {
   const adjacency_list = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const N = Number(lines.shift());
   const List = [];
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_list(A, B);
   }
   const points = new Array(N).fill(1);  // 添字 = 頂点番号 頂点が残っていれば 1
   let points_num = N;  // 頂点の数
   while (points_num > 2) {  // 頂点の数が 2 より多い間繰り返し…
      const leef = [];  // [[葉の頂点番号, i],…]
      for (let i = 0; i < N; i++) {
         if (List[i].length === 1) {  // List[i] の要素数が 1 なら…
            leef.push([List[i].pop(), i]);  // [List[i] から削除した要素, i] を leef に保存
            points[i] = 0;  // 頂点が減
            points_num--;  // 頂点数が減
         }
      }
      leef.forEach(elm => {  // 削除した各頂点について…
         List[elm[0]].splice(List[elm[0]].indexOf(elm[1]), 1);  // 頂点から続いていた枝を削除
      });
   }
   points.forEach((value, index) => {
      if (value) {  // 添字 = 頂点番号 が 1 なら…
         console.log(index + 1);  // 添字 + 1 を出力
      }
   });
});
hogeちゃんの画像

speech-balloonコメント

top
問題【FINAL】三角形を作る
Task
木の中の 3 つの頂点の端の 2 つの頂点を結び三角形を作るゲーム。勝者は?

【三角形を作る】コード

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const N = Number(lines[0]);
   let num_of_triangles = 0;  // 三角形の数
   const List = [];  // 隣接リスト
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
  // console.table(List);
   for (let i = 0; i < N; i++) {  // 各頂点について…
      const egde = List[i].length;  // 枝の数を egde に代入
      num_of_triangles += egde * (egde - 1) / 2;
  // 各頂点を中心に作成できる三角形の数 = 枝の数 * (枝の数 - 1) / 2
   }
   console.log(num_of_triangles % 2 ? 'paiza' : 'erik');
  // 三角形の数 % 2 = 1 なら  'paiza' 0 なら 'erik' を出力
});
hogeちゃんの画像

三角形の総数が偶数ならerik 君(後攻)の勝ち。

top

コメント