基礎理論
基本情報技術者試験｜6個の頂点すべてが互いに1本ずつ辺で結ばれた無向の完全グラフがある。辺の総数はいくつか
6個の頂点すべてが互いに1本ずつ辺で結ばれた無向の完全グラフがある。辺の総数はいくつか。
ア15本である
イ30本
ウ36本ある
エ全部で12本
正解
ア．15本である
完全グラフは異なる2頂点の組すべてに1本の辺がある。辺数は2頂点の選び方6C2=6×5/2=15本となり正しい。
?選択肢ごとの解説
ア ○完全グラフは異なる2頂点の組すべてに1本の辺がある。辺数は2頂点の選び方6C2=6×5/2=15本となり正しい。
イ ×30本はn(n−1)=6×5の値で、無向グラフなのに同じ辺を両方向で二重に数えた(2で割り忘れた)誤りである。
ウ ×36本はn^2=6×6であり、自分自身への辺や重複を含めて数えた誤りである。完全グラフに自己ループはない。
エ ×全部で12本は2nなど辺数の公式と無関係な計算による値で、組合せの考え方を使っていない。
基礎理論の他の問題
ある無向グラフの各頂点の次数が 2,3,3,4,4 であった。このグラフの辺の本数はいくつか。頂点数が20個である1つの木(連結で閉路を持たないグラフ)の辺の本数はいくつか。入力された0と1の並びについて、これまでに読み込んだ1の個数が偶数か奇数かを判定する有限オートマトンを設計する場合、最低限必…正規表現 ab*c が表す文字列パターンの説明として最も適切なものはどれか。ここで *…BNFで <数字列> ::= <数字> | <数字列><数字> 、<数字> ::= 0|1|2…中置記法の式 (A + B) * C を逆ポーランド記法(後置記法)に変換したものはどれか。次の論理式のうち、PやQの真理値に関わらず常に真となる恒真式(トートロジー)はどれか。4個の要素から成る集合 {a, b, c, d}…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0089