大阪大学 情報科学研究科 情報工学 2023年8月実施 離散構造
Author
祭音Myyura
Description
本問題で取り扱われるすべてのグラフ (graph) は無向グラフ (undirected graph) であり、多重辺 (parallel edge) や自己ループ (self loop) を持たないものである。グラフ
二つのグラフ
は全単射 (bijective). - 任意の
について、 ならば、かつそのときに限り .
(1)

-
(1-1)
かつ を満たす対 (pair) をすべて挙げよ。 -
(1-2)
は同値関係 (equivalence relation) であるため、 を に基づく複数の同値類 (equivalence class) に分割することができる。それらすべての同値類からなる集合 の要素数 (number of elements) を答えよ。
(2) 部分集合
-
(2-1)
の値はいくつになるか。理由とともに答えよ。 -
(2-2) 任意の
について、高々 個の異なるグラフ が を満たすことを証明せよ。 -
(2-3)
の値はいくつになるか。理由とともに答えよ。 -
(2-4) 以下の不等式 (inequality) が成立することを証明せよ。
Kai
(1)
(1-1)
(1-2)
集合
(2)
(2-1)
が分かるから、
(2-2)
同型の定義によれば、
(2-3)
グラフ
(2-4)
(2-2)、(2-3) より
である。