大阪大学 情報科学研究科 情報工学 2026年8月実施 3. 【選択問題】離散構造 Author xxxuuu
Description 配点：(1-1) 30，(1-2) 20，(1-3) 20，(2-1) 20，(2-2) 20，(2-3) 15
本問題で取り扱われるすべてのグラフ（graph）は無向グラフ（undirected graph）であり，多重辺（parallel edge）や自己ループ（self-loop）を持たないものとする。グラフ G G G V V V E E E G = ( V , E ) G=(V,E) G = ( V , E ) ∅ \emptyset ∅ G = ( V , E ) G=(V,E) G = ( V , E ) G ′ = ( V ′ , E ′ ) G'=(V',E') G ′ = ( V ′ , E ′ ) V ′ ⊆ V V'\subseteq V V ′ ⊆ V E ′ ⊆ E E'\subseteq E E ′ ⊆ E G ′ G' G ′ G G G G ′ ⊆ G G'\subseteq G G ′ ⊆ G V ′ ⊆ V V'\subseteq V V ′ ⊆ V E ′ = { { x , y } ∣ x , y ∈ V ′ かつ { x , y } ∈ E } E'=\{\{x,y\}\mid x,y\in V'\text{ かつ }\{x,y\}\in E\} E ′ = {{ x , y } ∣ x , y ∈ V ′ かつ { x , y } ∈ E } G ′ = ( V ′ , E ′ ) G'=(V',E') G ′ = ( V ′ , E ′ ) V ′ V' V ′ V ′ V' V ′ G G G I G ( V ′ ) I_G(V') I G ( V ′ )
すべての頂点の次数（degree）が2の連結な（connected）グラフを閉路グラフ（cycle graph）と呼び，C C C G G G C C C G G G
G = ( V , E ) G=(V,E) G = ( V , E ) H = ( V ′ , E ′ ) H=(V',E') H = ( V ′ , E ′ ) { x , y } ∈ E \{x,y\}\in E { x , y } ∈ E { x , y } \{x,y\} { x , y } H H H
{ x , y } ∈ E \{x,y\}\in E { x , y } ∈ E { x , y } ∉ E ′ \{x,y\}\notin E' { x , y } ∈ / E ′ x , y ∈ V ′ x,y\in V' x , y ∈ V ′
グラフ G G G G G G
(1)
以下の各小問に答えよ。
(1-1)
G = ( { a , b , c , d , e , f , g , h , i , j } , E ) G=(\{a,b,c,d,e,f,g,h,i,j\},E) G = ({ a , b , c , d , e , f , g , h , i , j } , E ) G G G
(a) 頂点数3の部分集合により誘導される G G G
(b) 頂点数3の部分集合により誘導される G G G
(c) 弦を持つ部分閉路グラフ。
図1 頂点 a から j までを持つグラフ G
g
e
f
d
c
h
a
b
i
j
図1
(1-2)
図2に示すグラフ G 1 G_1 G 1 G 2 G_2 G 2 G 3 G_3 G 3 G 4 G_4 G 4
図2 グラフ G1，G2，G3，G4
G₁
G₂
G₃
G₄
図2
(1-3)
以下の論理式が，命題「G = ( V , E ) G=(V,E) G = ( V , E )
∀ S ⊆ V : ( I G ( S ) ∈ C ⇒ (A) ) \forall S\subseteq V:\left(I_G(S)\in C\Rightarrow\boxed{\text{(A)}}\right) ∀ S ⊆ V : ( I G ( S ) ∈ C ⇒ (A) ) (2)
二つの実数（real number）x , y x,y x , y x ≤ y x\leq y x ≤ y x x x y y y [ x , y ] [x,y] [ x , y ] S = { [ a 0 , b 0 ] , [ a 1 , b 1 ] , … , [ a n − 1 , b n − 1 ] } S=\{[a_0,b_0],[a_1,b_1],\ldots,[a_{n-1},b_{n-1}]\} S = {[ a 0 , b 0 ] , [ a 1 , b 1 ] , … , [ a n − 1 , b n − 1 ]} n ≥ 1 n\geq1 n ≥ 1 V V V E E E G = ( V , E ) G=(V,E) G = ( V , E ) S S S
E = { { [ a i , b i ] , [ a j , b j ] } ∣ i ≠ j かつ [ a i , b i ] ∩ [ a j , b j ] ≠ ∅ } . E=\left\{\left\{[a_i,b_i],[a_j,b_j]\right\}\mid i\ne j\text{ かつ }[a_i,b_i]\cap[a_j,b_j]\ne\emptyset\right\}. E = { { [ a i , b i ] , [ a j , b j ] } ∣ i = j かつ [ a i , b i ] ∩ [ a j , b j ] = ∅ } . このとき，以下の各小問に答えよ。
(2-1)
S = { [ 1 , 3 ] , [ 2 , 5 ] , [ 4 , 7 ] , [ 6 , 8 ] , [ 2 , 7 ] } S=\{[1,3],[2,5],[4,7],[6,8],[2,7]\} S = {[ 1 , 3 ] , [ 2 , 5 ] , [ 4 , 7 ] , [ 6 , 8 ] , [ 2 , 7 ]}
(2-2)
S = { [ p 0 , q 0 ] , [ p 1 , q 1 ] , … , [ p n − 1 , q n − 1 ] } S=\{[p_0,q_0],[p_1,q_1],\ldots,[p_{n-1},q_{n-1}]\} S = {[ p 0 , q 0 ] , [ p 1 , q 1 ] , … , [ p n − 1 , q n − 1 ]} n ≥ 1 n\geq1 n ≥ 1 S S S G = ( V , E ) G=(V,E) G = ( V , E )
[ ( min 0 ≤ i ≤ n − 1 p i ) , ( max 0 ≤ i ≤ n − 1 q i ) ] = ⋃ 0 ≤ i ≤ n − 1 [ p i , q i ] . \left[\left(\min_{0\leq i\leq n-1}p_i\right),\left(\max_{0\leq i\leq n-1}q_i\right)\right]
=\bigcup_{0\leq i\leq n-1}[p_i,q_i]. [ ( 0 ≤ i ≤ n − 1 min p i ) , ( 0 ≤ i ≤ n − 1 max q i ) ] = 0 ≤ i ≤ n − 1 ⋃ [ p i , q i ] . (2-3)
任意の連結な区間グラフは弦グラフであることを証明せよ。ただし，必要ならば小問（2-2）の事実を用いてもよいものとする。