演習問題 1 解答 7-1 Δ(T) が最大の木は，スターグラフ K1, n – 1 K1,3 頂点数 n の木の辺の数は n – 1 であるから， 握手補題より，頂点の次数の合計は 2(n – 1) である． 連結グラフであるから，各頂点の次数は１以上． したがって，n – 1 個の頂点の次数が１で，１つの頂点のみ次数が n – 1 の場合がΔ(T) が最大の木である．これはスターグラフであ る． 7-2 演習問題 2 解答 3 2 4 3 9 6 1 7 9 1 2 演習問題 3.a（命題３⇒命題４）解答 7-3 （命題３） T は連結で，（頂点数 – 1）本の辺を持つ． （命題４） T は連結で，すべての辺は橋である T の頂点数を n とし，T は連結で，n – 1 本の辺を持つとする． まず，Tが単純グラフであることを証明する．T が単純グラフでない と仮定する．T のそれぞれの多重辺を構成する辺の内の任意の１ 本の辺を残して他の辺を除去し，さらにループを除去する．除去し た辺の本数を l とする（Tが単純グラフでないので l > 0） ．こうして できるグラフ T’ は，連結で単純グラフであり，n – 1 – l 本の辺を持 つ．しかし，定理5-2より，T’ の辺の数は n – 1 以上であるから，矛 盾である．したがって，T は単純グラフである． T の任意の辺を除去してできるグラフ G の点数は n，辺数は n – 2 である．G の成分数を k とすると，定理5-2より，n – k ≦ n – 2 であ るから，k ≧ 2，つまり，T の任意の辺を除去すると非連結になるの で，T の任意の辺は橋である． 演習問題 3.b（命題５⇒命題６）解答 7-4 （命題５） T の 2 つの頂点を結ぶ道はちょうど 1 本である ． （命題６） T には閉路がないが, 新しい辺をどのように付け加えて もちょうど 1 個の閉路ができる． T の 2 つの頂点を結ぶ道はちょうど 1 本であるとする． T に閉路があるならば，その閉路上の任意の2点は2本以上の道 で結ばれている．これは仮定に矛盾する．∴ T に閉路はない． 任意に 1 本の辺 e を T に付け加えると，仮定より e の両端点は T においてすでに結ばれているので閉路ができる．もし，e を付け加 えることで，2つ以上閉路ができる（すなわち，e を含む閉路が2つ 以上できる）ならば，e を付け加える前の T に閉路が存在すること になり（前回演習問題１参照），仮定に矛盾する．したがって，新し い辺をどのように付け加えてもちょうど1個の閉路ができる． 演習問題 4 解答 7-5 a. 林 F の各連結成分の点数を n1, n2, …, nk とすると，定理7-1よ り，各連結成分の辺の数は， n1 – 1, n2 – 1, …, nk – 1 であるか ら，F の辺数は k ∑ (n − 1) = n − k i =1 i b. n 点の木の辺数は n – 1 であるから，握手補題により，次数の 合計は，2n – 2． n ≥ 2 の場合，連結であるから孤立点はないので，端点以外の 次数は 2 以上である．端点の個数を t とすると，次数の合計は， t + 2(n – t) 以上である． 以上より，t + 2(n – t) ≤ 2n – 2．これから t ≥ 2 を得る． 演習問題 5.a 解答 7-6 a. 「S に ek を付加すると閉路が 1 つでき，この閉路には T に ない辺 e がある．」の証明 証明に利用する前提を挙げておく． T は資料7-12 のアルゴリズムで得られた木であり，重みの 昇順で辺を並べたものが e1, e2, …, en-1 とする． S は T より 重みの小さい全域木で，e1, e2, …, ek-1 までは，T と共通． ek は全域木 S にないGの辺であるから，定理 7-1 の命題 1 と 6 の同値性より，S に ek を加えると閉路が 1 つできる． この閉路が T にない辺を含んでいないとすると， ek はT の辺で あるから，この閉路は T に存在することになり，T が木であるこ とと矛盾する．したがって，この閉路は T にない辺を含む． 演習問題 5.b 解答 7-7 b. 「S の e を ekで置換したものを S’ とすると S’ も全域木」の証明 証明に利用する前提を挙げておく． S は全域木． e は S に ek を付加したときできる（唯一の）閉路の上の辺で， T にない辺． S に ek を付加したときできる唯一の閉路の上の辺で， T にない 辺がe で， S の e を ekで置換したものが S’ であるから，S’ は S に ek を付加し，これによりできる唯一の閉路上の辺 e を除去し たものである．S は全域木であるから，S に ek を付加したグラフ は G の点をすべて含む．したがって，ek を付加したことでできる 唯一の閉路の上の辺 e を除去したグラフ S’ は， G のすべての点を含み，閉路はなく，連結グラフである． したがって，S’ は G の全域木．
© Copyright 2024 ExpyDoc
