補遺_詳細解答例（pdf）

問・章末問題の解答例

第１章 問1.1 「あの山は高い」，「<sub>x ` 2 “ 1</sub>」など 問1.2 真：b), c) 偽：a), d) 問1.3 「3 ˆ 2 ą 32<sub>」かつ「x</sub>2 ´ 2x ` 1 “ 0の解は1である」,「42は3で割り切れる」ま たは「3は10約数である」,「3は10約数」でない 問1.4 論理式: pp ^ pq _ rqq, pp ^ pq 問_{1.5 a) ((p ^ qq _ r), b) ((␣rq _ s), c) ((((p ^ qq _ rq ñ sq ô p␣v)),} d) ((p ^ qq ô ppp␣rq _ sq ñ v)) 問1.6 pと qがともに真であるとき，␣pp _ qq は偽，␣p _ q は真となり，真理値が異なる ため． 問1.7 真理表は次のとおり． p q r a) b) c) d) e) T T T F T F T T T F T F T F T T F T T T F F T T F F T F T T T T T T F – – – F F T F F – – – F T F T F – – – F F F F F – – – T F 問1.8 a)偽(反例: 4は12の倍数でない), b)偽(反例_{: a “ 1, b “ ´1),} c)偽(反例_{: a “ 2, b “ ´1),} d)真 問1.9 a)真，必要条件：pかつqは真である，十分条件：pとqがともに真である，逆も真． b)真，必要条件：ある自然数は10以下である，十分条件：ある自然数が10の約数で ある，逆は偽． c)偽， 必要条件と十分条件はなし．逆は偽． 問1.10 次の真理値表より, a)恒真, b)恒偽, c)恒真，恒偽のいずれでもない p q r a) b) c) T T T T F T T F T T F T F T T T F T F F T T F T T T F – – F T F F – – T F T F – – F F F F – – T 問1.11 次の真理値表より，各式の左辺と右辺の真理値が等しいことがわかる． a) 左辺 a) 右辺 b) 左辺 b) 右辺 c) 左辺 c) 右辺 p q p ñ q p␣pq _ q ␣pp ^ qq ␣p _ ␣q ␣pp _ qq ␣p ^ ␣q T T T T F F F F T F F F T T F F F T T T T T F F F F T T T T T T

問1.12 a) aőbまたはbőc, b) a‰0かつb‰0, c) (a“0かつb“0)かつab‰0 （ヒン

ト_{: ␣pp ñ qq ô ␣p␣p_qq ô p^␣q}が成り立つ）

問1.13 p^pp ñ qq ô p ^ p␣p_qq ô pp^␣pq _ pp^qq ô F_pp^qq ô p^q

問_{1.14 pp ñ ␣qq ñ pr^sq ô p␣p_␣qq ñ pr^sq ô ␣p␣p_␣qq_pr^sq ô pp^qq_pr^sq}

ô ppp^qq_rq ^ ppp^qq_sq ô pp_rq^pq_rq^pp_sq^pq_sq

問_{1.15 Step.1 C “ tpu, Step.2 q “ p, C “ H, Step.3}処理なし,

Step.4 p3“T と p3“F に し た と き の q を, そ れ ぞ れ q1 と q2 と す る と, q1 “ pp1_p2q^p␣p1_␣p2q^pp1_Fq^pp2_Tq “ pp1_p2q^p␣p1_␣p2q^p1, q2 “ pp1_p2q^p␣p1_␣p2q^pp1_Tq^pp2_Fq “ pp1_p2q^p␣q1_␣q2q^p2, C “ tp1, p2u, Step.2 q “ q1, C “ tp2u, Step.3 規 則 I よ り, p1 “ T と し, q “ pT_p2q^pF_␣p2q ^ T “ ␣p2,さらに規則IIより, p2“ Fとし, q1“ T. よっ て, YESを出力して終了. 問_{1.16 (a) y “ ␣px}1^x2q, (b) y “ p␣px1^x2qq^px3_x4q, (c) y1 “ x1^x2, y2 “ p␣px1^x2qq^px1_x2q 章末問題 1.1 n種類の命題p1, p2, ¨ ¨ ¨ , pnの真理値の組合わせを考えると,各pipi “ 1, 2, ¨ ¨ ¨ , nqに ついて真,偽の2通りであり,全部で2n_{通りとなる. したがって, n種類の命題が含ま} れていれば真理値表は2n 行になる. (数学的帰納法による証明)初期段階_n“1のとき，真理値表には真と偽のために21 行 必要である．帰納段階_n“kのとき，真理値表の行数は2kであると仮定する．_{n“k`1</sub> のときの真理値表は，<sub>n“k</sub> の真理値表に命題を１つ付け加えたものとなる．その命題 が真の場合のときのために2k <sub>行必要であり，偽の場合のためにも2</sub>k <sub>行必要である．</sub> よって，<sub>n“k`1}の真理値表は全部で2k`2k“2 ¨ 2k“2k`1行となる.以上のことから, n種類の命題が含まれていれば真理値表は2n_{行になる.} 1.2 ␣pp_qq_p␣p^qq ô p␣p^␣qq_p␣p^qq ô ␣p^p␣q_qq ô ␣p^T ô ␣p 1.3 a) p_pp ñ qq ô p_p␣p_qq ô pp_␣pq_q ô T_q ô T b) p^pp_qq ô pp_Fq^pp_qq ô p_pF^qq ô p_F ô p c) pp ñ qq^pp ñ ␣qq ô p␣p_qq^p␣p_␣qq ô ␣p_pq^␣qq ô ␣p_F ô ␣p 1.4 括弧の略記なし論理式：pppp^qq ñ rq ô ppp^p␣rqq ñ p␣qqqq 真理値表は恒真となる（真理値表は省略）. 1.5 恒真：aとc，恒偽：b，充足可能：aとc（真理値表は略）

1.6 NANDゲートによるNOT，AND，ORゲートの構成

1.7 (a)は，2つのANDゲートで実現できる．

(b) は，x1, x2, x3 のうち，少なくとも2つが真である場合に yが真であればよく，

論理式はpx1^x2q_px2^x3q_px3^x1qと変形することができる． 第２章 問2.1 たとえば，「大きい石の集まり」 問_{2.2 a) (2) t0, 1, 2, 3, 4, 5, 6, 7, 8, 9u, (3) ts, c, i, e, nu} b) (2) tx|xは整数，かつ _{0 ő x ă 10u,} (5) tx|xは整数，かつ x2“ 2u s c i e n 8 E 問2.3 b), d), e) 問_{2.4 A “ ts, c, i, e, nu}，ベン図は右図のA． 問2.5 E “ t1, 3, 5, 7, 9u，ベン図は右図のU, E． 問2.6 有限集合: (1),(2),(3),(5) 無限集合: (4) 問2.7 (1) 4 (2) 10 (3) 5 (5) 0 問2.8 a) 4 b) 1 c) 0 d) 2 問2.9 「自然数の集合」は，たとえば，_{t2, 4, 6u}や_{t10, 20u}のようにいくつも考えられるが， 「自然数全体の集合」は_Nただ一つだけである．また，「自然数全体の集合」は無限集 合であるが，「自然数の集合」は有限集合の場合もありえる． 問2.10 NĎN, NĎZ, NĎQ, NĎR, ZĎZ, ZĎQ, ZĎR, QĎQ, QĎR, RĎR

問_{2.11 a) H, t1u, t2u, t3u, t1, 2u, t1, 3u, t2, 3u, b) tH, tHu, ttHuu, tH, tHuuu,}

c) |tx, y, z, wu|“4より_{|Pptx, y, z, wuq|“2}4 “16 問_{2.12 t}そば,うどん,ラーメンu, tそば,うどんu, tそば,ラーメンu, tうどん,ラーメンu, tそばu, tうどんu, tラーメンu, H 問2.13 a)とb) 問2.14 BとC，CとD 問2.15 A X pA Y Bq Ă Aの証明: x P A X pA Y Bqであるとき，xはAかつA Y Bの要素 であり，_{x P A}が成り立ち，_{A X pA Y Bq Ă A}．

AXpAYBq Ą Aの証明: x P Aのとき，AかつAYBの要素であり，AXpAYBq Ą A． よって，_{A X pA Y Bq “ A}が成り立つ． 問_{2.16 a) t}アu, b) tイ,ウ,エ,オu c) tアu 問_{2.17 a) pA Y Bq ´ C}の領域は右図 b)領域_⃝1は，_{pB ´} Aq ´ C, 領域⃝2は，C ´ pC ´ Bq 問_{2.18 a) t}月,火,土,日_{u, b) t}水,木,金,土,日_{u, c) H, d) t}水,木_u 問2.19 a) pA Y Bq ´ C, b) Ac X BcX C, c) A Y pB X Cq 問2.20 a) 6, b) tp0, 0q, p0, 1q, p0, 2q, p1, 0q, p1, 1q, p1, 2q, p2, 0q, p2, 1qu, c) A2“tp0, 0q, p0, 1q, p1, 0q, p1, 1qu，A3“tp0, 0, 0q, p0, 0, 1q, p0, 1, 0q, p0, 1, 1q, p1, 0, 0q, p1, 0, 1q, p1, 1, 0q, p1, 1, 1qu, d) C“AあるいはC“H 問_{2.21 ipxq ^ dpxq,} ITX DT 問2.22 a)すべてのハンバーガーはおいしい: @x:pHpxqñDpxqq, ハンバーガーの中にはお いしいものもある_{: Dx:pHpxq^Dpxqq , b) @x:RpxqñpDy:pRpyq^Lesspx, yqqq}

問2.23 a)偽（xが0以外で成立しない）, b)偽（¨ ¨ ¨ ^px`1“0q^px`2“0q^px`3“0q^ ¨ ¨ ¨

を満たすxは存在しない）

問2.24 qpxq ñ dpxq , QTĂ DT

問_{2.25 Dx@y:␣P px, yq}全称記号を存在記号に,存在記号を全称記号にかえて命題を否定する.

章末問題

2.1 xPAのとき，_{AĂB ^ BĂC}であれば，_{xPB ^ xPC}．よって，すべての_xPAは_xPC．

このことから，_{AĂB ^ BĂC ñ AĂC}が成り立つ． 2.2 pA X Bq Y pD ´ CqまたはppA X Bq Y Dq ´ C またはpA Y Dq ´ C 2.3 「_{pP X Qq}c “ PcY Qc」の証明： xPpP X Qqc _{であるとき，xはP とQの共通部分の補集合(共通部分以外)に属し} ている．すなわち，P に属さない要素,またはQに属さない要素のいずれかであり, PcY Qc．つまり，pP X QqcĂ PcY Qc．一方，xPpPcY Qcq であるとき，xはP に属さない要素,またはQに属さない要素のいずれかである. すなわち，P とQの共 通部分以外に属しており，_{xPpP X Qq}c_{．つまり，} pP X QqcĄ PcY Qc．以上のこと より，pP X Qqc“ PcY Qc． 「_{pP Y Qq}c “ PcX Qc」の証明： xPpP Y Qqc _{であるとき，xはP とQの和集合の補集合(和集合以外)に属してい} る．すなわち， P に属さない要素,かつ Qに属さない要素であり, PcX Qc．つま り，_{pP Y Qq}c Ă PcX Qc．一方，xPpPcX Qcq であるとき，xは P に属さない要 素,かつ Qに属さない要素である. すなわち，P と Qの和集合以外に属しており， xPpP Y Qqc．つまり，_{pP Y Qq}c Ą PcX Qc． 以上のことより，pP Y Qqc“ PcX Qc． X Y _Z b d g h j k l p q u v x y z w s e o r_{f a} t m _{ni c}

2.4 a) X´Y “ te, s, wu, b) Y XZ “ ti, nu, c) Z´pXYY q “ tcu, d) XXY XZ “ H, e) Xc XY XZc “ tmu, f) Xc XpY YZq “ tc, i, m, nu （ヒント: ベン図は右図である） 2.5 a) x“1のとき成立させるyが存在しないから,偽 _{b) x“2}のとき_{(x“3, 4}のとき も)すべてのyで成立するから,真 第3章 問3.1 初期段階n “ 0のとき，左辺=右辺=0．帰納段階n “ kのとき，12 ` 22` ¨ ¨ ¨ ` n2“ npn ` 1qp2n ` 1q ¨ 1 6 が真であると仮定する．n “ k ` 1のとき，左辺“ 1 2 ` 22` ¨ ¨ ¨ ` k2` pk ` 1q2“ kpk ` 1qp2k ` 1q ¨ 1 6 ` pk ` 1q 2 “ 1 6 ¨ pk ` 1qpk ` 2qp2k ` 3q． 一方，右辺“ pk ` 1qpk ` 2qp2 ¨ pk ` 1q ` 1q ¨ 1 6 “ pk ` 1qpk ` 2qp2k ` 3q ¨ 1 6．よっ て，両辺は等しいことから<sub>n “ k ` 1</sub>で成り立つ. 問3.2 初期段階 n “ 7 のと き，37 “ 2187 ă 5040 “ 7!．帰納段階 n “ k のとき， 3k “ k! であると仮定する．両辺に３を掛ければ，_{3 ¨ 3}k ă 3 ¨ k!．右辺はさらに， 3 ¨ k! ă pk ` 1q・k! “ pk ` 1q!よって，n “ k ` 1のもとで，3n ă n!が成り立つ． 問3.3 初期段階8円のとき，１枚の3円と１枚の5円で払える．帰納段階_{k ą 8}円のときに 支払えると仮定する．このとき，k 円をすべて3円で払った場合と，k円を少なくと も１枚の5円を含めて払った場合が考えられる．k円をすべて3円で払った場合には，

そのうちの3枚の3円を2枚の5円に代えれば，k ` 1円が支払える．一方，後者の 場合には，１枚の5円を2枚の3円に代えれば，<sub>k ` 1</sub>円が支払える．よって，_{k ` 1} 円が支払える．

問3.4 初期段階 実数は，Aexpの要素である．帰納段階xとyがAexpの要素（算術式）と

仮定（帰納法の仮定）したとき，_{px ` yq, px ´ yq, px ˚ yq, px{yq}はAexpの要素（算術

式）である． 問3.5 a)初期段階4は, 4の倍数の正整数の集合の要素である. 帰納段階xが4の倍数の正 整数の集合の要素と仮定(帰納法の仮定)したとき, x ` 4は4の倍数の正整数の集合の 要素である. b)初期段階1は, 3で割り切れない正整数の集合の要素である. 帰納段 階 xが3で割り切れない正整数の集合の要素と仮定(帰納法の仮定)したとき, x ` 3 は3で割り切れない正整数の集合の要素である. 問3.6 初期段階 実数の場合は括弧の数は0である（左右の括弧が0で同数）．帰納段階xが 算術式で左括弧の数xlと右括弧の数xr が同じxl“xrであり，同様にyが算術式で 左右の括弧の数が同じyl“yrであると仮定する．このとき，px ` yqの左右の括弧の数 は xl`yl`1“xr`yr`1で同じである．同様に，px ´ yq，px ˚ yq，px{yqもまた左右 の括弧の数はxl`yl`1“xr`yr`1で同じである． 問3.7 初期段階 空列 λ は, λ´1 “ λであり,反転した文字列であるpλ´1 P Σ˚q. 帰納段 階 <sub>u P Σ</sub>˚ , x P Σについて，<sub>w “ u ¨ x</sub> が Σ˚ の要素であるとき（帰納法の仮定）， w´1 “ pu ¨ xq´1“ x ¨ u´1は, wを反転した文字列である<sub>pw</sub>´1 P Σ˚q. 問3.8 構文要素名は任意 x数字y ::“ 0 | 1 | . . . | 9 x正数y ::“ 1 | . . . | 9 x自然数y ::“ x数字y | x正数yx自然数y 問3.9 初期段階 v, w の一方がλ の場合，例えばv “ λ のとき左辺lpλwq “ lpwq ,右辺 lpλq ` lpwq “ lpwqであり，成り立つ. 帰納段階 v, wについて_{lpvwq “ lpvq ` lpwq</sub> が成り立つと仮定する．<sub>x P Σ</sub> を用いて, vw よりも1 文字多い文字列 vwx を つ く る. こ の と き ，仮 定 よ り<sub>, lpvwxq “ lpvwq ` 1 “ lpvq ` lpwq ` 1} で あ り, lpvq ` lpwxq “ lpvq ` lpwq ` 1であるから，<sub>lpvwxq “ lpvq ` lpwxq</sub>が成り立つ． 問3.10 対偶をとり「nが偶数ならば，5n ´ 7が奇数である」を証明する．nが偶数のとき， n “ 2m, m PZ．よって，_{5p2mq ´ 7 “ 10m ´ 7 “ 2p5m ´ 4q ` 1}．_{5m ´ 4}は整数 であり, 5n ´ 7は奇数になる． 問3.11 ⃝月×日△時に犯行現場にいないのならば，犯人 (容疑者)でない． 問3.12 「?2が有理数である」と仮定する．このとき，?2は有理数なので，正整数m, nを 用いて，?2 “ m n と表される．ここで，mとnは互いに素(両者の最大公約数は１) と仮定しても一般性は失われない．両辺にnを掛けて，両辺を2乗すると，2n2“ m2 が得られる．mを素因数分解したとき，右辺を考えると，左辺に2が含まれているた め，mの素因数にも2が含まれていることがわかる．つまり，mは2で割りきれる． そこで，_{k “} m 2 とすると，2k 2 “ n2が成立する．先ほどと同様の議論により，この n もまた2で割りきれることがわかる．m とnがともに2で割りきれるということ は，mとnが互いに素であることに矛盾する．よって，「?2が有理数である」とした 仮定が間違っており，「?2は無理数である」ことが証明された.

章末問題

3.1 初期段階Aの濃度が1のとき(たとえば，_{A “ txu)}，_{PpAq “ tH, Au}であり，_PpAq の濃度は21_{．帰納段階 Aの濃度がk のとき，PpAqの濃度は2}k _{であると仮定する．}

１つの要素 xをAに加え_{, A Y txu}とすると,この集合の濃度は_{, k ` 1</sub>である. この とき，<sub>PpA Y txuq</sub>は，<sub>PpAq</sub>の各要素にxを含めてできる集合と，<sub>PpAq</sub>の各要素 とをすべて集めてできあがる．仮定より，それらの総数は2k` 2kであり，2k`1が成 り立つ． 3.2 初期段階n “ 1について，13 ` 2 “ 3であり，3で割り切れる．帰納段階n “ kにつ いて，k3` 2kが3で割り切れると仮定する．<sub>n “ k ` 1}のとき，_{pk ` 1q</sub>3 ` 2pk ` 1q “ pk ` 1qtpk ` 1q2` 2u “ pk ` 1qpk2` 2k ` 3q “ k3` 2k2` 3k ` k2` 2k ` 3 “ pk3` 2kq ` 3pk2` k ` 1qである．pk3` 2kq ` 3pk2` k ` 1qのうち第1項pk3` 2kq は仮定より3で割りきれる．また，第2項<sub>3pk</sub>2 ` k ` 1qもまた3で割りきれる．よっ て，<sub>n “ k ` 1}でも成り立つ． 3.3 「n が偶数ならば，n2 が偶数」の証明: nが偶数ならば_{, n “ 2m} に対して,n2 “ 4m2 “ 2× 2m2_{．よって，n}2 _{は偶数である. 「n}2 _{が偶数ならば，nが偶数」の証明:} 対偶「nが奇数ならば，n2が奇数」を証明する. nが奇数のとき，_{n “ 2m ` 1</sub>に対し て，n2 “ p2m ` 1q2“ 2× p2m2` 2mq ` 1．よって，n2 _{は奇数である．} 3.4 背理法による. 奇数nが，3つの偶数x, y, zの和によって表されると仮定する．3つの 偶数を_{x “ 2a, y “ 2b, z “ 2c pa, b, c PZq}とすると_{, n “ x ` y ` z “ 2a ` 2b ` 2c “} 2pa ` b ` cq. a ` b ` cは整数であり, nは偶数になる．矛盾が生じる． 3.5 初期段階_{n “ 2}のときは，2は素数．帰納段階_{2 ő k ő n}で，kは素数あるいは，合 成数(素数の積)とする．このとき，n ` 1は素数または合成数のいずれかであり，合 成数であるかどうかを考える．<sub>n ` 1}が素数でなければ，ある数_{q p1 ă q ă n ` 1q</sub>で 割りきれる．n ` 1 q ő nかつ，q ő nであることから，仮定より， n ` 1 q およびq はともに素数または合成数で表せる．よって，<sub>n ` 1 “} n ` 1 q ˆ qもまた素数または 合成数で表すことができる． 3.6 初期段階<sub>n “ 5</sub>のとき，25“ 32 ą 52“ 25．帰納段階n “ kのとき，2ką k2 が成 り立つと仮定する．両辺に2を掛けると，2 ¨ 2k ą 2 ¨ k2．さらに右辺について，k ą 4 の場合を考えればよく，<sub>2 ¨ k</sub>2 “ k2` k2ą k2` 4k ŕ k2` 2k ` 1 “ pk ` 1q2．よっ て，_{2 ¨ 2}k “ 2pk`1qą pk ` 1q2 が成立するため，n “ k ` 1のもとで2ną n2 が成り 立つ． 3.7 初期段階 空列λはDの要素である<sub>pλ P Dq.</sub> 帰納段階wがDの要素<sub>pw P Dq</sub>であ り,かつxがΣの要素px P Σqであるとき，xwxはD の要素であるpxwx P Dq. 3.8 初期段階 命題を表す文字の場合は括弧の組の数と論理結合子の数はともに0である． 帰納段階pが論理式で括弧の組の数ppと論理結合子の数 po が同じpp“po であり， 同様に q が論理式で括弧の組の数qp と論理結合子の数qo が同じ qp“qo であると 仮定する．このとき，<sub>p␣pq</sub> の括弧の組の数と論理結合子の数は, pp`1“po`1で同じ である．pp ^ qqの括弧の組の数と論理結合子の数は, pp`qp`1“po`qo`1で同じで ある．同様に，<sub>pp _ qq</sub>，<sub>pp ñ qq</sub>，<sub>pp ô qq</sub>もまた括弧の組の数と論理結合子の数は pp`qp`1“po`qo`1で同じである．

第４章 問4.1 5通り _{(“ 2ˆ2`1)</sub> 問4.2 26P4“ 26! p26´4q! “ 26ˆ25ˆ24ˆ23 “ 358800 問4.3 53` 54` 55 “ 125 ` 625 ` 3125 “ 3875 問4.4 σ1¨σ2“ ˜ 1 2 3 2 3 1 ¸˜ 1 2 3 3 2 1 ¸ “ ˜ 1 2 3 1 3 2 ¸ σ1¨σ2“ ˜ 2 3 3 2 ¸ 問4.5 左辺“ n! r!pn´rq!，右辺“ n! pn´rq!pn´pn´rqq! “ n! pn´rq!r! より，成り立つ． 問4.6 8C3“ 8! 3! ¨ 5! “ 56 問4.7 n`1Cr“nCr´1`nCr の証明： 左 辺 <sub>“</sub> pn`1q! r!pn`1´rq!．右 辺 “ n! pr´1q!pn´r`1q!` n! r!pn´rq! “ n! ¨ r r!pn´r`1q! `n! ¨ pn´r`1q r!pn´r`1q! “ n!pn`1q r!pn´r`1q! “ pn`1q! r!pn`1´rq!．よって，成り立つ． nCr “n´1Cr´1`n´1Crの証明： 左 辺 “ n! r!pn´rq!．右 辺 “ pn´1q! pr´1q!pn´rq!` pn´1q! r!pn´1´rq! “ pn´1q! ¨ r r!pn´rq! `pn´1q! ¨ pn´rq r!pn´rq! “ pn´1q!n r!pn´rq! “ n! r!pn´rq!．よって，成り立つ． 問4.8 3個のバッグに5個の荷物を入れる場合， 少なくとも１個のバッグに2個以上の荷物 が入っている. すなわち,複数個の荷物が入れられるバッグは,少なくとも１個ある. 10台の車が交差点の3つの方向（左折，右折，直進）に進んだ場合,少なくとも1つ の方向に4台以上の車が進んでいる(どの方向にも偏りなく進んだ場合, 3方向それぞ れに3台が進み,もう1台がどれかの方向に進むため,1つの方向に4台進んだことが 分かる.偏りがある場合には,これ以上になるため,少なくとも1つの方向に4台以上 進んだことが分かる). 問4.9 ４輪駆動, カーナビ装備, シートヒータ装備の車の集合をそれぞれ W, C, S とする と, |W Y C Y S| “ |W |`|C|`|S|´|W X C|´|W X S|´|C X S|`|W X C X S| “ 12`18`6´|W X C|´|W X S|´|C X S|`3 “ 39´|W X C|´|W X S|´|C X S|．こ こで，|W X C| ŕ |W X C X S|，|W X S| ŕ |W X C X S|，|C X S| ŕ |W X C X S| なので，|W Y C Y S| ő 39´3´3´3 “ 30．したがって，１つ以上の装備を含んでい る車はたかだか30台であり，どの装備も含んでいない車は少なくとも_{33´30 “ 3}台 である． 問4.10 10円玉が3枚， 50円玉が2枚， 100円玉が 1枚は，それぞれ，_p1`x`x2 `x3q， p1`x`x2q，p1`xqで表され，これらの積は1`3x`5x2 `6x3`5x4`3x5`x6となる． したがって，2枚，3枚，4枚，5枚の組合せ方の総数は，それぞれ5, 6, 5, 3である． 問4.11 50 円 玉 が 3 枚 ， 100 円 玉 が 2 枚 は ，そ れ ぞ れ ，p1`ax50`a2x100 `a3x150 q， p1`bx100`b2x200q と 表 せ ば よ く ，こ れ ら の 積 は <sub>1`ax}50 `pa2 ` bqx100`pa3 ` abqx150`pa2b`b2qx200`pa3b`ab2qx250`a2b2x300`a3b2x350と な る ．し た が っ て ，50円p50円１枚q，100円p50円2枚，100円1枚q，150円p50円3枚，50円1枚 と100円1枚_q，200円_p50円2枚と100円1枚，100円2枚_q，250円_p50円3枚 と 100 円 1枚，50 円 1枚と 100円 2枚 q，300 円 p50円 2 枚と100円 2 枚 q

，350円p50円3枚と100円2枚q． 章末問題 4.1 64 p4P1`4P2`4P3`4P1“ 4 ` 12 ` 24 ` 24 “ 64q 4.2 ２項定理pa`bqn “ n ÿ r“0 nCran´rbr において，a“b“1 とすれば，p1`1qn “ 2n “ n ÿ r“0 nCran´rbr“ n ÿ k“0 nCr であり，nC0`nC1` ¨ ¨ ¨ `nCn“ 2nが得られる． 4.3 8 桁 の 中 に 1 が r=0,2,4,6,8 個 の 場 合 の 数 <sub>8</sub>Cr の 総 和 を 求 め れ ば よ く ， 8C0`8C2`8C4`8C6`8C8“1`28`70`28`1“128通りある． 4.4 1) T1 のメンバー，すなわち，12名の中から4名の選び方は 12C4．次のT2 のメン バーは，残りの8名から4名を選ぶので8C4．最後にT3のメンバーは，残りの4名か ら4名を選ぶので4C4．以上のことより，12C4ˆ8C4ˆ4C4“ 12! 4!8! ˆ 8! 4!4! ˆ 4! 4! “ 12! 4!4!4! “ 34650．2)一人の学生Aがあるチーム(T1, T2, T3いずれでもよい)のとき， 同じチームに属する３名の学生の選び方は <sub>11</sub>C3．残り8名のうちで，(Aとは異なる もう一人の)学生Bと同じチームに属する３名の学生の選び方は7C3．残りの４名は 同じチームになる．よって，３チームへの分け方は，11C3ˆ7C3“ 165 ˆ 35 “ 5775． 別解：チームT1, T2, T3の順列は3!．チームを区別しないので，前問の順序分割より， 34650 3! “ 5775． 4.5 Xm´1 n \`1または， Pm n T 4.6 床の1m2の正方形のスペースには, 1段目に最大100個の商品を並べることができる. その上に,P1111 100 T “ 12 個を少なくとも積み上げることができるため(鳩の巣原理)， 120cm. 4.7 |A Y B Y C| “ |A| ` |B| ` |C| ´ |A X B| ´ |A X C| ´ |B X C| ` |A X B X C| 第５章 問5.1 一握の砂b石川啄木, 銀河鉄道の夜b宮沢賢治, 坊ちゃんb夏目漱石, 注文の多い料 理点_b宮沢賢治 問5.2 131, 231, 331, 431, 232, 432, 333, 434 問_{5.3 Gp3q“tp1, 1q, p2, 1q, p3, 1q, p4, 1q, p2, 2q, p4, 2q, p3, 3q, p4, 4qu,} Gp3´1 q“tp1, 1q, p1, 2q, p1, 3q, p1, 4q, p2, 2q, p2, 4q, p3, 3q, p4, 4qu 問5.4 x, y, z の組がp1, 3, 2q, p2, 1, 3q, p3, 2, 1qのとき_{, Q “ Q}´1_を満たす . 問_{5.5 ’“ tp1, 2q, p1, 3q, p1, 4q, p2, 3q, p2, 4q, p3, 4qu} 1 2 3 4 問5.6 関係₃の行列表現 ¨ ˚ ˚ ˚ ˝ 1 0 0 0 1 1 0 0 1 0 1 0 1 1 0 1 ˛ ‹ ‹ ‹ ‚ 問_{5.7 P “tp1, 2q, p2, 2q, p3, 2qu, P}´1 “tp2, 1q, p2, 2q, p2, 3quより, P YP´1 “tp1, 2q, p2, 1q, p2, 2q, p2, 3q, p3, 2qu 問_{5.8 ŕ“ tp2, 2q, p3, 2q, p3, 3q, p4, 2q, p4, 3q, p4, 4qu,} ŕ ˝ ŕ“ tp2, 2q, p3, 2q, p3, 3q, p4, 2q, p4, 3q, p4, 4qu

問5.9 R ˝ IA “ Rの証明：px, yq P R ˝ IA であるとき, xIAxかつ xRy が成立するから, px, yq P R. 一方, px, yq P Rであるとき, xIAxが成立するから, xIAxかつxRyであ り, px, yq P R ˝ IA. よって, R ˝ IA“ R. IA˝ R “ Rの証明：px, yq P IA˝ R であるとき, xRy かつ yIAy であるから, px, yq P R. 一方, px, yq P Rであるとき, yIAyが成立するから, xRyかつyIAyであ り_{, px, yq P I}A˝ R. よって, IA˝ R “ R. 問5.10 131, 232, 333, 434 であるから, 反射的である. 432 ^ 231 ñ 431 であり, 232 ^ 231 ñ 231 や231 ^ 131 ñ 231 など自己ループを含む推移も成立するか ら,推移的である_{. 231}であるが_{, 132}が成立しないから,対称的でない. 問5.11 p1, 1q R ’ であるから, 反射的でない. pp1, 2q P ’ ^p2, 4q P ’q ñ p1, 4q P ’， pp1, 3q P ’ ^p3, 4q P ’q ñ p1, 4q P ’，pp1, 2q P ’ ^p2, 3q P ’q ñ p1, 3q P ’， pp2, 3q P ’ ^p3, 4q P ’q ñ p2, 4q P ’ であるから推移的である. p1, 2q P ’である が_{, p2, 1q R ’}であるから対称的でない.

問5.12 C1“tt0u, t1, 2u, t4uuは, 3が含まれていないため,分割でない. C2“tt0, 1u, t1, 2u, t3, 4uu は, 1が重複して含まれているため,分割でない. C3“tt0, 1u, t3, 4u, t2uuは,条件をす べて満すため分割である. 問5.13 p1, 1q P △, p2, 2q P △, p3, 3q P △, p4, 4q P △であり,反射的である. p4, 2q P△ ^ p2, 3q P△ ñ p4, 3q R △であるため,推移的でない_{. p1, 2q P△}であるが_{, p2, 1q R△} であるから，対称的でない. したがって,同値関係でない. 問_{5.14 x b y} を x と y が等しいと定義すると, F “ !1, 2, 3, 4 2, 6 3, 9 3, 4 4 ) 上の関係 _b 1 2 3 4 4 4 2 6 3 9 3 の図表現は右図のようになる. F の要素は, 3つに分けられ,各要素には自己ループがあ り,すべての要素間に関係_bが成立している. このため,それぞれにおいて,反射律，対 称律，推移律をすべて満たす. したがって,同値関係であり, 3つの分割が同値類となる. 商集合は次のようになる_{. F {b “ tr1s, r2s, r3su “}!!1, 4 4 ) ,!2, 4 2, 6 3 ) ,!3, 9 3 )) 章末問題 5.1 まず, S ˝ pQ ˝ Rq Ă pS ˝ Qq ˝ Rを示す. pa, dq P S ˝ pQ ˝ Rqとすると,関係の合成の定 義より_{, pa, cq P Q ˝ R}かつpc, dq P Sを満す_{c P C}が存在する. さらに_{, pa, cq P Q ˝ R} について,関係の合成の定義より_{, pa, bq P R}かつ_{pb, cq P Q}を満す_{b P B}が存在する. ここで, pb, cq P Q, pc, dq P S であるから, pb, dq P S ˝ Qとなる関係の合成が定義で き,これと_{pa, bq P R}より_{, pa, dq P pS ˝ Qq ˝ R}となる関係の合成が定義できる. よっ て, S ˝ pQ ˝ Rq Ă pS ˝ Qq ˝ R. 次に_{, S ˝ pQ ˝ Rq Ą pS ˝ Qq ˝ R} を示す_{. pa, dq P pS ˝ Qq ˝ R}とすると,関係の合 成の定義より, pa, bq P Rかつ pb, dq P pS ˝ Qq を満す b P B が存在する. さらに, pb, dq P S ˝ Q について, 関係の合成の定義より_{, pb, cq P Q} かつ pc, dq P S を満す c P C が存在する. ここで_{, pa, bq P R, pb, cq P Q}であるから_{, pa, cq P Q ˝ R}となる関 係の合成が定義でき,これとpc, dq P Sより, pa, dq P S ˝ pQ ˝ Rqとなる関係の合成が 定義できる. よって_{, S ˝ pQ ˝ Rq Ą pS ˝ Qq ˝ R.} 以上より, S ˝ pQ ˝ Rq “ pS ˝ Qq ˝ R. 5.2 GpRq “ tp1, 2q, p1, 3q, p1, 4q, p3, 2q, p4, 3qu

5.3 反射律: IAĂ Rであるならば, R Ą R Y IA かつR Ă R Y IA である. したがって, IAĂ R ñ R “ R Y IA. 一方, R “ R Y IA であるならば, IAĂ Rである. 以上よ り, IAĂ R ô R “ R Y IA. 推移律: R2Ă Rであるならば, R1 “ Rより, R1Ă R, R2Ă R が成り立ち,任意の n ŕ 1に対して, RnĂ Rであるならば, Rn`1“ Rn˝ R Ă R ˝ R “ R2Ă Rが成り 立つ. したがって数学的帰納法より,任意の<sub>n ŕ 1</sub>に対して, RnĂ Rが成り立つから, R`“ R1Y R2Y R3Y ¨ ¨ ¨ Ă R. 一方, R`“ R1Y R2Y R3Y ¨ ¨ ¨ Ą Rであるから, R2 Ă R ñ R “ R`. 逆に, R “ R`<sub>であるならば, R</sub>2 Ă R`“ R1YR2YR3Y¨ ¨ ¨ “ R となるから_{, R “ R}` ñ R2Ă R. 以上より, R2Ă R ô R “ R`. 対称律: R´1 Ă Rであるならば, R Ą R Y R´1 _{かつR Ă R Y R}´1 _{であるから,} R´1Ă R ñ R “ R Y R´1. 逆に_{, R “ R Y R}´1_{であるならば} , R´1Ă Rである. 以 上より, R´1 Ă R ô R “ R Y R´1. 5.4 反射律：_{n “ n}1 _のとき， n ´ n1“ 0であり，_{n »}mnが成り立つ．対称律：n ´ n1 と n1´ n の絶対値は等しく，一方が割りきれるときには，もう一方も割りきれる． よって，n »m n1 ならば，n1 »mnである．推移律：n »m n1 かつ n1 »m n2 の 場合を考える．_{n »}m n1 より，Dk P Z : n “ n1` km．さらに，n1 »m n2 より， Dk1PZ : n1“ n2`k1m．これらより，n “ n1 `km “ n2`k1m`km “ n2 `pk1`kqm であり，_{n »}mn2が成り立つ． 5.5 グラフを3つに分割でき,それぞれが反射的かつ対称的かつ推移的であるため同値関係

である．商集合_{: X{R “ trvs, rws, rxsu “ ttv, yu, tw, zu, txuu} 第６章 問6.1 fbは右図のとおり． r b s t w v u 問6.2 negp3q“ ´ 3, negp1q“ ´ 1, negp0q“0, negp´1q“1, negp´3q“3

問_{6.3 a) r2.73s “ 3 b) t2.73u “ 2 c) 100 mod 3 “ 1} 問6.4 hpAq “ thp1q, hp2q, hp3qu “ t4, 5, 6u 問6.5 X1XX2 の要素 xの f による値 y すなわち, x P pX1XX2q のときの y“f pxqは， xPX1 より, y“f pxqPf pX1q であり, なおかつxPX2 より, y“f pxqPf pX2q である. よって, yPf pX1qXf pX2qであり, f pX1XX2q Ă f pX1qXf pX2qが成り立つ. 問6.6 天井関数（定義域 _{tx | 0 ő x ő 5u}）は右図のとおり． 5 5

問_{6.7 a) f pAq “ tf p1q, f p2q, f p3q, f p4qu “ t1, 2, 3u, gpBq “}

tgp1q, gp2q, gp3qu “ t1, 2, 3u, hpBq “ thp1q, hp2q, hp3qu “ t1, 2, 3u b)全射：f, h（_{gpBq ‰ A}であり, gは全射ではない）, 単射：g, h（_{f p2q“f p3q“1}であり, fは単射ではない）,全単射：h 問_{6.8 a) pidN ˝ sqrqpxq“idNpsqrpxqq“idNpx}2 q“x2 _{b) idN} の終域とsqrの定義域が一 致しないため定義されない．ただし_{, idN}の値域_{idNpNq “ N}がsqrの定義域_Zの部 分集合であるためpN Ă Zq, psqr ˝ idNqpxq “ sqrpidNpxqq “ sqrpxq “ x2 が定義で きるとする場合もある. c) psqr ˝ plusqpx, yq“sqrppluspx, yqq“sqrpx`yq“px`yq2

d) sqrの終域とplusの定義域が一致しないため定義されない． 問6.9 任意のx, x1P Xに対し_{, pg ˝ f qpxq“pg ˝ f qpx}1 qとすると_{, gpf pxqq“gpf px}1 qqであり, gが単射だから_{, f pxq“f px}1 qとなる. さらに, fも単射だから_{, x“x}1_{となる. よって,} pg ˝ f qpxq“pg ˝ f qpx1qとなるのは, x“x1_{のときだけであるから, g ˝ fは単射である.}

問6.10 n“0のときsumpnq“0, ną0のときsumpnq“n`sumpn ´ 1q,

sump3q“3`sump2q“3`2`sump1q“3`2`1`sump0q “3`2`1`0“6, sump4q

“4`sump3q“4`6 “ 10, sump6q“6`sump5q“6`5`sump4q“6`5`10“21

問_{6.11 Ap0, 0q“1, Ap0, 1q“2, Ap1, 0q“Ap0, 1q“2, Ap1, 1q“Ap0, Ap1, 0qq“Ap0, 2q“3,}

Ap1, 2q“Ap0, Ap1, 1qq“Ap0, 3q“4

章末問題

6.1 g ˝fが単射であれば，「x1, x2P Xについて，x1‰ x2ならばpg ˝f qpx1q ‰ pg ˝f qpx2q」 である．いま，x1‰ x2 のときにf px1q“y1, f px2q“y2としたとき，gpy1q ‰ gpy2qで あることから，y1‰ y2 である．つまり，「x1‰ x2 ならば，f px1q ‰ f px2q」. よっ て，f は単射である． 6.2 A上の2項関係Rが，∀ x, y, z∈ A：xRyかつxRzであるとき，_y“zであれば定め ることができる．そうでなければ，1対多の関係になるため，関数は定義されない．た とえば，_{A “ ta}1, a2, a3uのとき，pa1, a1q P Rかつpa1, a2q P Rならばf pa1q “ a1 かつ_{f pa1q “ a2} となる関数fを定めることができない． 6.3 問 6.5の解答で, f pX1X X2q Ă f pX1q X f pX2qの証明をしたので, f が単射である とき_{, f pX}1X X2q Ą f pX1q X f pX2qを証明する. y P f pX1q X f pX2qとする. この とき, y P f pX1qかつy P f pX2qである. すなわち,あるx1P X1 がありy “ f px1q であり, 同様に, ある x2 P X2 があり y “ f px2q である. f は単射であるから, y “ f px1q “ f px2qのときは, x1“ x2 となり, x1, x2 はX1, X2 のどちらにも属する 同一の要素となる. よって, x1, x2P X1X X2 であり, y P f pX1X X2qとなる. 以上 より, f が単射であるとき_{, f pX1X X2q “ f pX1q X f pX2q}である. 6.4 3! “ 6通り．u P AにはB の要素への3通りの対応があり, v P Aにはuで対応さ せた要素以外の2通りの対応がある_{. w P A}は 残り1つの要素への対応となる. 6.5 (a) pS˝Sqp2q“SpSp2qq“Sp3q“4, (b) pS˝Sqpxq“SpSpxqq“Spx`1q“x`2,

(c) pS˝U12qp2, 3q “SpU12p2, 3qq“Sp2q“3, (d) pS˝U23qpx, y, zq“SpU23px, y, zqq

“Spyq“y`1 6.6 f pxq “ yが全単射であれば，Y の任意の要素yについてX のただ１つの要素xを対 応づける関数，すなわち，逆関数_{Y Ñ X} を構成できる．逆に，_{f : X Ñ Y} の逆関数 f´1_{: Y Ñ Xが存在するとき，Y の任意の要素yについて X のただ１つの要素x} を対応づけることができるため，fは全単かつ単射である．したがって，「_{f : X Ñ Y} の逆関数f´1_{: Y Ñ Xが存在する」ことと「fが全単射である」ことは，互いに他の} 必要十分条件である． 6.7 関数gは全射であるから,任意の_{z P Z} に対し_{, z“f pyq}となる_{y P Y} が存在する. さ らに,関数f も全射であるから, y に対し, y“f pxqとなるx P X が存在する. した がって,任意のz に対し_{, z“gpyq“gpf pxqq“pg˝f qpxq}となるxが存在することにな り, g˝f は全単射となる． 第7章 問7.1 V2“ t東京,大宮,高崎,新潟,長野,金沢u E2“ tt東京,大宮u, t大宮,高崎u, t高崎,新潟u, t高崎,長野u, t長野,金沢uu 問7.2 (a)高崎， 次数: 3 (b)高崎と金沢 _{(c) t}東京,大宮_{u, t}大宮,高崎_u

問7.3 V3“ ta, b, c, d, e, f u

E3“ tta, bu, ta, cu, tb, cu, tb, du, tb, eu, tc, eu, tc, f u, td, eu, te, f uu

deg_G3paq “ 2, deg_G3pbq “ 4, deg_G3pcq “ 4, deg_G3pdq “ 2, degG3peq “ 4, degG3pf q “ 2

問7.4 ř

vPV3degG3pvq “ 2 ` 4 ` 4 ` 2 ` 4 ` 2 “ 18 2 ¨ |E3| “ 2 ˆ 9 “ 18

問7.5 P1 は小道および道である．P2は道ではないが，小道ではある．P3 は道でもなく，小

道でもない． 「P4: c, b, a, e, c」は長さ4の閉路である． 問7.6 (a) 3 (b) 2 (c) 3 (d) v2, v1, v3, v4, v7, v6, v5pv9q, v8

問7.7 部分グラフG37: V “ td, e, gu, E “ ttd, eu, te, guu, 誘導部分グラフ G47 : V “

td, e, gu, E “ ttd, eu, td, gu, te, guu

問7.8 反射律：u↠ u は，長さ0の道があるとして成り立つ．対称律：無向グラフであるこ とから，u↠ vならば，v↠ uは成り立つ．推移律：u↠ vかつv↠ wであれば，v に接続している辺からなる道を通じて，u↠ wは成り立つ． 問7.9 切断点d (右図), 橋はなし 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 問7.10 右図のようなグラフを描ける. 次数が奇数である頂点が6個 あり,オイラー小道が存在するための必要十分条件を満さない (次数は○の中の数). 各道路を1度の走行で除雪できない. 問7.11 (a)オイラー小道：c, b, a, d, e, c, f, b, e, f など (b)オイラー 回路:なし (c)ハミルトン路:a, d, e, b, c, f など (d) b (羽 田)を始点とするハミルトン閉路:b, a, d, e, f, c, bなど 問7.12 完全グラフK2, K3, K6 2 3 6 問7.13 辺と頂点の接続はそのままで,頂点の位置を移動すると同じグラフとなる頂点の対応を 見つける. ϕ1paq“x, ϕ1pbq“w, ϕ1pcq“y, ϕ1pdq“zなど 問7.14 「ス,イ,ム」と「コ,フ」 問7.15 G10“ pV10, E10q V10“ ta, b, c, d, eu

E10“ tpa, bq, pb, aq, pb, cq, pc, dq, pd, eq, pe, bq, pe, cqu

deg`G10paq“1， deg

` G10pbq“2， deg ` G10pcq“2， deg ` G10pdq“1， deg ` G10peq“1 deg´_G 10paq“1， deg ´ G10pbq“2， deg ´ G10pcq“1， deg ´ G10pdq“1， deg ´ G10peq“2 問7.16 (a) a, b, c, d, eまたはc, d, e, b, aなど (b) b, c, d, e, bまたはc, d, e, cなど (c) a, b, c, d, e, b, a またはc, d, e, b, a, b, cあるいはb, c, d, e, b, a, bなど 問7.17 どの頂点においても他の3つの頂点への道があり,強連結である．

問7.18 G1 の隣接行列は次のとおり. a b c d e f g AG1“ » — — — — — — — — – 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 fi ffi ffi ffi ffi ffi ffi ffi ffi fl a b c d e f g 問7.19 pAK4q xmy_の要素が pm ŕ 2qですべて1となるから,任意の2頂点（自身も含む）に おいて,長さ2の歩道が存在する． a b c d a b c d Ak4“ » — — – 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 fi ffi ffi fl a b c d pAk4q x2y_“ » — — – 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 fi ffi ffi fl , pAk4q x3y_“ » — — – 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 fi ffi ffi fl 問7.20 次式のように_{, pA1q}x˚y_{の成分がすべて} 1であることから,「東京,福島,山形,盛岡,秋 田,新青森」の任意の2つの駅は,たかだか3つの路線を利用することで移動できるこ とがわかる_{. pA}1qx˚y“ I ` A1` pA1qx2y` pA1qx3y` pA1qx4y` pA1qx5yであるが, I ` A1` pA1qx2y` pA1qx3yまでですべての成分が1となる.

pA1qx˚y “ I ` A1` pA1qx2y` pA1qx3y“ » — — — — — — – 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 fi ffi ffi ffi ffi ffi ffi fl 東 福 山 盛 秋 新 A1“ » — — — — — — – 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 fi ffi ffi ffi ffi ffi ffi fl 東 福 山 盛 秋 新 東 福 山 盛 秋 新 pA1qx2y“ » — — — — — — – 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 fi ffi ffi ffi ffi ffi ffi fl 東 福 山 盛 秋 新

東 福 山 盛 秋 新 pA1qx3y“ » — — — — — — – 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 fi ffi ffi ffi ffi ffi ffi fl 東 福 山 盛 秋 新 東 福 山 盛 秋 新 pA1qx˚y“ » — — — — — — – 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 fi ffi ffi ffi ffi ffi ffi fl 東 福 山 盛 秋 新 問7.21 G1 は, 頂点集合ta, b, c, d, euと tf, guの2つの連結成分からなり, 隣接行列の積 においても, これら2つの連結成分は独立している. pAG1qx4y 以降は 偶数のとき, pAG1q x2y_{と同じ行列であり} ,奇数のとき_{, pA}G1q x3y_{と同じ行列である} . a b c d e f g AG1“ » — — — — — — — — — — – 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl a b c d e f g a b c d e f g pAG1q x2y “ » — — — — — — — — — — – 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl a b c d e f g a b c d e f g pAG1qx3y“ » — — — — — — — — — — – 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl a b c d e f g

a b c d e f g pAG1q x6y “ » — — — — — — — — — — – 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl a b c d e f g 章末問題 7.1 辺の本数の数学的帰納法による_{. n “ 1}の場合，頂点は端点の2個であり，それぞれ の次数は1であるため，すべての頂点の次数の和は2で, 2 ¨ |E| “ 2より,成り立つ． n “ k の場合成り立つとする. 辺が1本増えると，その辺の端点の次数がそれぞれ1 増える．すなわち,すべて頂点の次数の和は2増加し_{, 2 ¨ pn “ k}のときの辺の数<sub>` 1q</sub> となる. よって，n “ k ` 1でも成り立つ． 7.2 (a) すべて頂点の次数が奇数であるため,オイラー小道, オイラー回路どちらもなし (b) 次数が奇数である頂点が2個(頂点b, dの次数が3)であるため,オイラー小道が 存在する. オイラー回路はなし. オイラー小道: b, a, e, c, a, d, b, c, dなど(次数が 奇数である頂点が始点,終点となる). (c)すべて頂点の次数が奇数であるため,オイ ラー小道,オイラー回路どちらもなし. 7.3 完全グラフKnでは,すべての頂点の次数は同じで, n ´ 1である. したがって,すべて の頂点の次数の和は, npn ´ 1qであり,握手補題より, それは辺の総数の2倍となる. よって,完全グラフKnの辺の総数は, npn ´ 1q 2 である. 7.4 完全グラフKnでは,すべての頂点の次数は同じで, n ´ 1であるから, nが奇数であれ ば,すべての頂点の次数は偶数となり,オイラー回路が存在する.よって_{, n mod 2 “ 1.} 7.5 この隣接行列Aおよび,Ax2y_{, A}x3y_{は次のとおりである.} 1 ⃝ 2⃝ 3⃝ 4⃝ 5⃝ 6⃝ A “ » — — — — — — – 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 fi ffi ffi ffi ffi ffi ffi fl 1 ⃝病院前 2 ⃝バスセンター 3 ⃝中央公園 4 ⃝図書館 5 ⃝県庁前 6 ⃝駅東口 Ax2y“ » — — — — — — – 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 fi ffi ffi ffi ffi ffi ffi fl Ax3y“ » — — — — — — – 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 fi ffi ffi ffi ffi ffi ffi fl ここで，A の要素aij “ 1は，「バス停i」 から1つ目(長さ1でたどれる頂点)の 「バス停j」 を表す. すなわち，a2j“ 1は，「バスセンター」から次のバス停jを表す.

そして, Ax2y_の要素a ij“ 1は,「バス停i」 から2つ目(長さ2でたどれる頂点)の 「バス停j」 を表すので，a2j“ 1は，「バスセンター」から2つ目のバス停jを表す. 同様にAx3y_の要素a ij“ 1は，「バス停i」 から3つ目の「バス停j」 を表す. この ことから,「バスセンター」からn番目のバス停をみつけるには, Axnyの要素a2j “ 1 となる jを求めればよい. なお，Ax4y “ Ax5y“ 0(零行列)であり,どのバス停からも 4番目以降のバス停は存在しない.

Ax˚y“I ` A ` Ax2y` Ax3y` Ax4y` Ax5y“ » — — — — — — – 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 fi ffi ffi ffi ffi ffi ffi fl 連結行列より,「バスセンター」から他のバス停に移動できるが,他のバス停からは,移 動できないバス停があることがわかる. 特に,降りるだけのバス停が2つあることがわ かる. 7.6 (1,2)成分： 頂点aからbへの長さ3の歩道が，「a, b, a, b」，「a, b, d, b」，「a, c, a, b」， 「a, c, d, b」の4通りあることから成分p1, 2qは4である． (2,4)成分： 頂点bからdへの長さ3の歩道が，「b, a, c, d」，「b, a, b, d」，「b, d, c, d」， 「b, d, b, d」の4通りあることから成分<sub>p2, 4q</sub>は4である． 第8章 問8.1 C, E, F (閉路のないグラフ) g g (a) (b) 問8.2 (a)頂点aの入次数は0であり（頂点aを終点とす る辺はない）,他の頂点への道が存在するから,根 となる. 根付き木は右図のように,辺の方向を,上 から下へと定め省略して描く. (b) 頂点cを根として,右図のように無向木の根付 き木を描く. 問8.3 (a)頂点 aの子孫である頂点: a, c, d, e, g (b) 頂点bの真の 子孫である頂点: f, h, i (c)頂点f を根とする部分木: 右図 問8.4 同型ではない，位数5の木は,右図の3種類である. 問8.5 Gの隣接しない任意の2頂点をu, vとする. Gに辺 u, v を加えると閉路ができるなら，uとvを結ぶ道が存在して いるため，Gは連結している．したがって，Gは閉路がな い連結グラフであり，木にほかならない． 問8.6 頂点の総数は,初項1,公比2の等比数列の和となる. したがって, 1 ` 2 ` 22 ` ¨ ¨ ¨ ` 2k´1` 2k“ 2k`1´ 1 問8.7 1), 2-1), 2-2)には,全部で木が5種類あり,それらをTl, Trとした場合, 5 ˆ 5 “ 25 種類となる. このうち,高さ2未満の木が4種類あるからこれらを除くと,高さ2の木 は, 25 ´ 4 “ 21種類である. したがって,残りは21 ´ 11 “ 10種類である. 問_{8.8 prepT}15q “ 1, 2, 3, 4, 5, 6, 7 inpT15q “ 3, 2, 4, 1, 6, 5, 7 postpT15q “ 3, 4, 2, 6, 7, 5, 1

問8.10 同型でない全域木(T18以外)には,次のものなどがある. 問8.11 問8.10の解答の全域木のコストは,次のようになる. 18 19 20 18 19 19 14 3 2 3 2 3 3 2 3 3 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 2 2 5 53 3 5 5 1 1 1

T

問8.12 Step.1辺の重みを昇順に整列すると，次のようになる．

tb, du, ta, cu, te, gu, tb, cu, tc, du, td, f u, te, f u, ta, bu，tc, f u, td, eu，tb, eu.

各辺を先頭から順にe1, ¨ ¨ ¨ , e11とし, EM“H，i“1とする．

Step.2„Step.3 i “ 1, ¨ ¨ ¨ , 7 について繰り返す：e1, e2, e3, e4 を順にEM に含め

る．しかし，e5は閉路が生じてしまうので含めない．そして，e6, e7 はT に含める． Step.3 i“7のとき，V のすべての要素pa, b, c, ¨ ¨ ¨ , gqがいずれかの辺の端点になっ

たので終了．この結果，最小木T1

19 が得られる． 最小コストは, 14である.

問8.13 Step.1辺の重みを昇順に整列すると,次のようになる．

tc, f u, tb, cu, tc, du, td, eu, te, f u, ta, bu,

T

ta, hu, tb, hu，td, f u，tc, gu, tg, hu，tf, gu.

各辺を先頭から順にe1, ¨ ¨ ¨ , e12とし, EM“H，i“1とする．

Step.2„Step.3 i “ 1, ¨ ¨ ¨ , 11について繰り返す：e1, e2, e3, e4を順にEM に含め

る．しかし，e5 は閉路が生じてしまうので含めない．そして，e6, e7 はT に含める． しかし,e8, e9 は閉路が生じてしまうので含めない．そして，e10 はT に含める． Step.3 i“10のとき，V のすべての要素_{pa, b, c, ¨ ¨ ¨ , gq}がいずれかの辺の端点になっ たので終了．この結果，最小木T20 が得られる． 最小コストは, 17である. 問8.14 T9: 1.1, 1, 0, 2 T10: 1, 0, 2, 2.1 章末問題 8.1 Gが閉路Cを持つとする. 閉路Cに含まれる頂点の集合V1 によるGの誘導部分 グラフG1 “ pV1, E1 qにおいては,閉路であるため, |E1 | ŕ |V1|である. V1 _以外の 頂点tv|v R V1, v P V uも連結であるから, 少なくともその1つの頂点は, G1 の点 に隣接している. これを1つ加えたGの誘導部分グラフG2 “ pV2, E2qにおいて も, |E2 | “ |E1| ` 1 ŕ |V1| ` 1 “ |V2|となる. 同様に残りの頂点も加えていくと, |E| ŕ |V |が得られ, |E| “ |V | ` 1と矛盾する.したがって, Gに閉路はない. 次に, G は連結であるから,隣接しない2頂点u, vには道が存在する. u, vに辺を加えると,そ の道と辺tu, vuで閉路Cを形成する. 同時に,他の閉路C1を形成したとすると, Gに は閉路がないから,閉路C1<sub>は辺</sub> tu, vuを含む. このとき, 2頂点u, vに,辺tu, vuを 通らない2つの道があり,それらをつなげるとGに閉路が存在することになる. これ はGに閉路がないことに矛盾する. したがって,隣接しない2頂点に辺を加えると, 1 つの閉路ができる. 8.2 2 分木の頂点の総数は, 1(根<sub>)`2</sub>1 (深さ1の頂点の総数<sub>)`2</sub>2 (深さ2の頂点の総数) `23(深さ3の頂点の総数)` ¨ ¨ ¨ となる. 木の高さがk ´ 1のとき, 頂点の総数は, 1 ` 21` 22` ¨ ¨ ¨ ` 2k´1“ 2k´ 1である. 木の高さがkのときは,木の高さが_{k ´ 1}

のときよりも深さが１つ増えるから,最小の頂点の総数は,木の高さがk ´ 1のときの 頂点の総数に1つ頂点が増えたときであり,歳大の頂点の総数は, 2k`1´ 1となる. し たがって,木の高さがkのときの頂点の総数をnとすると, 2k ´ 1 ` 1 ő n ő 2k`1´ 1 となり, 2kő n ő 2k`1´ 1 ă 2k`1より, 2k ő n ă 2k`1である. ここで，各辺の対 数をとっても大小関係は変らないため，_{k ő log} 2n ă k ` 1となる．kは高さであるか ら自然数であり，log2nの小数点以下を切り捨てた整数tlog2nuは，k に等しい．し たがって，高さ<sub>k “ tlog2nu</sub>である． 8.3 右図は, Tの一例である. このT を前順で走査すると, prepT q “ ` ˚ 2 x ´ y 1となる. x y 2

*

+ -1 8.4 全域木はグラフGのすべての頂点を含んだ閉路のない連結グラフ であるから,グラフGが全域木を含めば連結グラフである. 連結グ ラフGに閉路がなければ, Gが全域木であり,閉路があれば,その閉路を構成する辺を 1つ取り除く操作を,閉路がなくなるまで繰り返せばGの全域木が得られる. したがっ て,グラフGが連結グラフであれば全域木を含む. 閉路から辺を取り除いても連結であ ることは次のように証明される. 連結グラフGにある閉路Cから辺eを取り除いたと する. 連結グラフGには任意の2頂点u, v間に道が存在するが,辺eを通っていた場 合,辺eの端点間では,閉路Cを構成していた辺（辺eを取り除いた残り）を迂回路と して通る道を作れる. したがって,閉路から辺を取り除いても連結である. 8.5 Gに含まれる長さ最大の道をPとし,その始点,終点をそれぞれx, yとする. xの次数 を2以上とすると, xから新たに別の頂点pに接続する辺が存在する. P は最長の道で あるから,このpはPに含まれ,閉路があることになる. Gには閉路がないことと矛盾 するため, xは次数1である. 同様にyも次数1である. よって, Gには次数1の頂点 が2つ以上ある. 第9章 問9.1 a, b, c, d : 200 ` 240 ` 100 “ 540 a, b, e, d : 200 ` 200 ` 300 “ 700 a, f, e, d : 150 ` 180 ` 300 “ 630 a, f, e, b, c, d : 150 ` 180 ` 200 ` 240 ` 100 “ 870 問9.2 札幌，仙台,伊丹，沖縄 コスト_{: 335 ` 396 ` 739 “ 1470} (札幌，羽田，沖縄は,コスト: 510 ` 984 “ 1494であり最短距離ではない) 問9.3 制約条件: 「グラフ中の路のうち，始点s と終点_{g P V} を端点とする路」,目的関数: 「路のコスト」

問9.4 3回目_{: U “ ts, b, a, du, V ´ U “ tc, eu, v}min“ u “ d, T “ tps, bq, pb, aq, pb, dqu, 4回目: U “ ts, b, a, d, cu, V ´U “ teu, vmin“ u “ c, T “ tps, bq, pb, aq, pb, dq, pa, cqu, 5回目_{: U “ ts, b, a, d, c, eu, V ´ U “ H, v}min“ u “ e,

T “ tps, bq, pb, aq, pb, dq, pa, cq, pd, equ

問9.5 G7 とG8は,右図のような同型があるため, 2部グ ラフである。 ' ' 4 s s s s s C C C 1 2 3 4 5 1 2 3 問9.6 完全2部グラフK3,4の図表現は右図のようになる. 問9.7 2部グラフは右図のようになる. マッチングの例 ttC1, s3u, tC2, s1u, tC3, s2uuを太線で示す. 問9.8 グラフGのすべての頂点で，M 飽和なM を完全 マッチングという． 問9.9 K3,3 とK4,3は平面描画できない.

G₈ 問9.10 右図より, G5の領域は5である. 問9.11 G8 の平面描画は右図である. 問9.12 K5 は平面描画できないため,領域の個数を求めら れない(オイラーの公式は満さない). また_{, | E |“} 10, | V |“ 5より，平面グラフの辺の総数の不等式 10 ő 3 ˆ 5 ´ 6 “ 9は成り立たない． 問_{9.13 | V |“ 5}の極大平面的グラフは右図である. 問9.14 K3,3 では, | E |“ 32 “ 9, | V |“ 6なので,不等 式 _{9 ő 2 ˆ 6 ´ 4 “ 8}が成り立たない. 問9.15 G13とG14は, K5 あるいはK3,3 と同相な部分グ ラフを含まない. 平面描画は右図である.

問9.16 4色で彩色可能なので，120分である. たとえば同色にする頂点を_{, t1, 6u, t2u, t3, 5u, t4, 7u} の4つにすることができる. 問9.17 Step.1: AG17, LG17, L xRy G17 “ L x7y G17 はそれぞれ次式となる． 1 ⃝ 2⃝ 3⃝ 4⃝ 5⃝ 6⃝ 7⃝ 8⃝ AG17 “ » — — — — — — — — — — – 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl 1 ⃝ 2 ⃝ 3 ⃝ 4 ⃝ 5 ⃝ 6 ⃝ 7 ⃝ 8 ⃝ 1 ⃝ 2⃝ 3⃝ 4⃝ 5⃝ 6⃝ 7⃝ 8⃝ LG17 “ » — — — — — — — — — — – 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl 1 ⃝ 2 ⃝ 3 ⃝ 4 ⃝ 5 ⃝ 6 ⃝ 7 ⃝ 8 ⃝ 1 ⃝ 2⃝ 3⃝ 4⃝ 5⃝ 6⃝ 7⃝ 8⃝ Lx7yG17 “ » — — — — — — — — — — – 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 fi ffi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl 1 ⃝ 2 ⃝ 3 ⃝ 4 ⃝ 5 ⃝ 6 ⃝ 7 ⃝ 8 ⃝ Step.2: LG17 xRy _{より，頂点} 1,6が入口，頂点7が出口になる．それぞれを強連結成 分とする. Step3: 入口と出口にあたる，1行目，1列目，6行目，6列目,7行目，7列 目をすべて削除する．再度Step.2: 1つ前のStep.3で得られた行列をLG17 xRy_とす

る. 頂点2,3,4,8が入口，頂点5が出口となり,終了となる. 以上より,強連結成分は, t1, 6u, t2, 3, 4, 8u, t5u, t7u となり, G117が得られる.

2 ⃝ 3⃝ 4⃝ 5⃝ 8⃝ Step-3 » — — — — – 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 fi ffi ffi ffi ffi fl 2 ⃝ 3 ⃝ 4 ⃝ 5 ⃝ 8 ⃝ i=0 j=1 z=x+y y=i+1 z=x+1 x=j+i 問9.18 先行グラフは右図のようになる. 1行目と2行目に有向辺 がなく,実行順は問わない. その後の3行目と4行目, 3行 目と5行目に有向辺がなく,実行順は問わない. 実行順を 問わない文は並列的に実行できる. 章末問題 9.1 ダイクストラ法により，G6 のすべての頂点v P V について，d˚pvq が求められる過程を次の表に示 す．右図の太線が， 頂点sから各頂点への最短路 からなる最短路木である． s a b c d e f g h vzk 0 1 2 3 4 5 6 7 8 s 0 0 0 0 0 0 0 0 0 a 8 3 (s) 3 3 3 3 3 3 3 b 8 2 (s) 2 2 2 2 2 2 2 c 8 8 8 (b) 7 (a) 7 7 7 7 7 d 8 8 7 (b) 7 7 7 7 7 7 e 8 8 8 8 8 (c) 8 8 8 8 f 8 8 8 8 14 (c) 14 11 (e) 11 11 g 8 8 8 8 8 13 (d) 10 (e) 10 10 h 8 8 8 8 8 8 8 14 (g) 14 9.2 2項定理より, pI ` Aqn “nC0In`nC1In´1A1`nC2In´2A2` ¨ ¨ ¨ `nCnAnが成 り立つ. 0-1行列においては,係数nCk pk “ 0 ¨ ¨ ¨ nq は1となる. 単位行列の積も

まとめると次のようになる. pI ` Aqxny“ I ‘ A ‘ Ax2y‘ ¨ ¨ ¨ ‘ Axny したがって, Lxny“ I ‘ A ‘ Ax2y‘ ¨ ¨ ¨ ‘ Axny また,到達可能行列Lxnyの要素は,頂点viP V

から頂点 vj P V へちょうど長さ n の歩道が存在することを表している. 頂点の総

数が n の連結グラフでは, 2頂点間の距離の最大値はn ´ 1 (頂点が一列に並んだグ

ラフの両端の頂点間の距離)であるから,少なくとも_{n ´ 1} の辺を通ればすべての頂

点に到達できる. よって, n ´ 1以上では, 到達可能行列に変化はない. したがって, Lxn´1y“ Lxny“ Lxn`1y

9.3 グラフの内側のすべての領域が3本の辺で囲まれていれば,どの領域も3角形となる.

3角形の領域の内部には,新たな辺を加えることができないため,グラフのどの領域も