グラフ理論とネットワーク（2026年度）の採点が終わりました
グラフ理論とネットワーク（2026年度）の採点が終わりました
3年春学期に開講されている「グラフ理論とネットワーク」では、「データ構造とアルゴリズムI・II」の続きとして、グラフの構造や連結度、最短経路、最大フロー問題などについて扱ってきました。2006年度に開講して以来、21年間の長きに渡り講義を行ってきましたが、課程制開始に伴い、今年度が最後となります。
まず、本授業は「講義」と「演習」から構成されており、講義時間中，あるいは講義実施後に実施する小テスト（20％）、講義で学んだアルゴリズムなどをプログラミングで実現する演習レポート（40％）、「期末試験」（40％）により評価しています。
小テスト
小テストは、Scombzを使って講義時間中や講義実施後に提出していただきました。平均点は74.86点（未提出の0点を含む）でした。また、平均提出回数は4.85回（全6回）でした。
演習レポートは、講義で学修したアルゴリズムなどをプログラムで実現するプログラミングレポートを提出していただきました。平均点は91.05点（未提出の0点を含む）でした。また、平均提出回数は3.73回（全4回）でした。
近年のLLMの発達により、プログラムを作成すること自体は比較的簡単になっています。LLMが出力したコードを検証できる能力を付けておくことが重要です。
期末試験は、紙の資料の持ち込みを可として実施しました。試験範囲は授業の全範囲でした。
問題1は、グラフの特徴を問う問題でした。平面グラフや同形グラフなど、やや「ひっかけ問題」に近いものが含まれていましたが、比較的よくできていたようです。得点率は75.6％でした。
問題2は、平面グラフの点彩色に関する問題でした。彩色問題は当科目の定番であり、白地図から隣接関係を示す平面グラフを作成して点彩色をしますが、ミスさえなければ簡単に得点できる問題でした。ただ、かなりの学生が「四色定理」（平面グラフは4色で点彩色可能であるという定理）を間違えており、残念でした。得点率は84.2％でした。
問題3は、連結度に関する関係式と、講義で学修した定理やアルゴリズムの用途を問う問題でした。ダイクストラ法やフォードファルカーソン法など、定番のアルゴリズムの正解率は高かったですが、少しマイナーなメンガーの定理やクルスカル法の誤答が少しありました。得点率は84.4％と高かったです。
問題4は、ダイクストラ法の詳細な動作を問う問題でした。配布資料のアルゴリズムでは、(s,d)間の最短経路を求めて終了するようになっていましたが、講義で説明したとおりダイクストラ法はすべてのdに対して最短経路を求めることが可能です。この部分が少し拡張された問題でしたが、得点率は79.4％と比較的よくできていたようです。
問題5は、最大フローに関する出題でした。与えられた重み付き有向グラフから最大フローを算出する問題でしたが、パスを発見できずに計算ミスをした答案が多く見られました。得点率は72.9％でした。
最終的な点数は、79.124点（未受験者0点を含まない）となりました。2025年度が85.98点であることから、7点ほど低下したことになります。
これらを総合して得られる点数を最終得点として成績報告をしました。平均点は81.40点で、単位取得者数（S、A、B、C）は57名（60名中）となりました。単位取得率は95.0％で、21年間で最も高い単位取得率となりました（次点は2019年度の94.7％）。本科目は選択科目であることから、小テストの受験率やプログラミング課題の提出率が低くなる傾向があり、これまでは期末試験の点数が高くても不合格となる学生がやや多かったのですが、今年度が最後の開講年となることから、多くの履修者が積極的に授業に参加してくれたものと思います。
なお、今回不可（F）となった履修者は、3名とも期末試験を受験しなかった学生でした。小テストの受験率も低く、プログラミングレポ―トの提出率も低かったです。もし次年度に再履修をされる場合には、小テスト、プログラミングレポート、期末試験のすべてにおいて、積極的に提出するようにしましょう。
Copyright (c) 2007-2021 Multimedia Information Network Laboratory, SIT, All rights reserved.