8\]となり、矛盾する。よって平面グラフとは言えない。始点としてダイクストラのアルゴリズムを適応して得られる最短路木と各点までの距離を求めなさい。距離は点の〇の中にそれぞれ記すこと。10)★解答★アルゴリズムを適用させていく様子をアニメーションで出しているので参考までに。6.正誤問題つぎの(a)~(e)のうち、正しい記述をすべて選びなさい。あるグラフとその補グラフが同型なグラフが存在する。回路と閉路をちょうど1つずつ含むグラフが存在する。オイラーグラフでかつハミルトングラフであるようなグラフは存在しない。正解の選択肢を選んでいないもの1つにつき1ミス)(a):1つ辺を足すと、次数の和は必ず2つずつ増えるので辺の数にかかわらず次数の和は偶数となる。(握手定理)(b):例えば下のグラフは、元のグラフと補グラフが同型になる。(c):例えば下のグラフが回路、閉路を1つずつもつ。(d):下のグラフはオイラーグラフでもハミルトングラフである。(e):あるグラフが完全グラフであれば必ず正則グラフとなるが、正則グラフは必ずしも完全グラフになるとは限らない。よって十分条件であるが必要条件ではない。(誤り)7.最大フローつぎのグラフの最大フローを記しなさい。このグラフの最小カット容量を求めなさい。[4点]何も追加してない状態の残余ネットワークは下のようになります。ここから、スタート点(一番左側の点)からゴール点(一番右側の点)まで流せなくなるまで流していきます。残余ネットワークも変化するのを忘れずに。実はまだ1流せるので忘れずに流しましょう。ここで残余ネットワークを見てみると、スタート点からゴール点まで流せる点がないことがわかりますね。よってこの状態が最大フロー(6流した状態)となることがわかります。最小カットの容量は最大フローにおける流した数(今回の場合は6)と一致するので最小カットの容量は6となります。下のようになるので参考までに。8.応用問題16つの点を2色の辺で結ぶグラフを考える。このとき、以下の問いに答えなさい。6つの点のうち、1つに注目する。このとき、他の5つの点と結ばれている辺のうち、常に最大何本以上が同じ色であるといえるか。6人いると互いに知り合いである3人組か互いに知らない3人組が必ず存在する。[4点]6つの点を結ぶ場合、自分以外の5つの点と辺をつなげるので、5本の辺を赤・青の2色でわけることになる。ここで、5つの辺を2色(赤と青とします)で塗り分けるパターンとしては、(赤5本・青0本)、(赤4本・青1本)、(赤3本・青2本)、(赤2本・青3本)、(赤1本・青4本)、(赤0本・青5本)の6パターンで塗り分ける方法がある。よって、少なくとも3本以上が同じ色となる。[6点]ここで、知り合いである組を青色の辺、知り合いでない組を赤色の辺で表すこととする。すると、(1)より、5つの結ばれている辺のうち3つ以上は同じ色となる。このとき、知り合いの3人組ができることはグラフ内に青色の三角形が存在すること、知り合いではない3人組ができることはグラフ内に赤色の三角形が存在することと同値である。Dさんの3人と知り合いとする。このとき、つぎの(1)~(4)の場合を考えられる。Cで三角形ができるので題意を満たす。Dで三角形ができるので題意を満たす。Dで三角形ができるので題意を満たす。Dで赤色の三角形ができるので題意を満たす。よって、(1)~(4)すべての場合において題意を満たす。知り合いでない人が3人で知り合いの場合が2人の場合は、上の部分の青色の辺を赤色に、赤色の辺を青色にすれば題意を満たす。一部が含まれることを示すことができます。9.応用問題2一般工業大学生のA男は何を血迷ったのか大学メンバーで合コンを企画した。参加者は次の通りである。E子、F香、G美、パジュラ・H・モジュラまた、事前アンケートで異性がアリかナシかの調査を行っている。調査結果は表のとおりである。A男とF香はお互いにアリだと思っている(〇)が、A男とG美はどちらかもしくは双方がなし(×)と思っている。このとき、次の問いに答えなさい。参加者を点、お互いにアリだと思っている人の組を辺として、この状態をグラフで書きなさい。この合コンではどう頑張ってもカップルが4組できない。その理由を説明しなさい。[6点]下のような2部グラフで書くことができる。Hの点集合をWとする。題意を示すためには、MからWへの完全マッチングがないことを示せばよい。ここで、MからWへの完全マッチングがあると仮定する。1\]となってしまい、ホールの定理が成立しない。よって仮定は矛盾するため、完全マッチングが存在しないことが示された。わかりやすく言うと、AくんとDくんの2人の中でカップルになりえる候補はFさん1人だけですよね。2人のうちどちらか1人は絶対にカップルになれません。完全マッチング(男性側全員がカップルを作ること)は無理~ってことをグラフ理論用語で示そうよ~って問題でした。本番レベル模試」の解説記事を作成しました。システムオートマトンPrologCLOSEサイト内検索を行います。はてなブログPro数学と情報が得意な大学生です。累計:リアルタイム現在の閲覧者数:。