講義メモ

Ｇ１課題：グラフ構造３例

出題時補足

• 参考にした文献等あれば明記すること。 （図書の場合、著者名、書名、出版社、発行年などの情報）
• WWWページの場合、単に URL を示すだけではなく、 分かる範囲で、著者名（あるいは組織名など）とページのタイトルを 明記すると良い。

レポートについて

• ノードやエッジの重みで表現できるもの （化学グラフでいうと原子や結合の種類の区別） があれば、それについても言及すると良い。
• また、それぞれの対象について、 ノード数やエッジ数、次数、サイクル、部分グラフなどに対応する 「意味」があれば、それについても考えてみるとより良い。
• サイクル（閉路）を持たないグラフを、特にツリー（木）と呼ぶ。

• 課題内容、クラスとグループ番号、 グループ内での役割分担、ページ番号、図表番号等を明記すること。
  → レポート作成時の注意を良く読むこと。

Ｐ１課題：部分グラフ抽出

出題時補足

• 作成するプログラムでは、 グラフおよび部分グラフの入出力は隣接行列表現とすること。＜要求仕様＞
• また可能であれば、 部分グラフのノード集合を「元のグラフのノード番号」のリストを用いても 表示すると良い。（その方が結果を検証しやすいはず）
  （→ 「解説」のページの図２を参照）

• 「隣接行列」を入力する際は、最初に 行列のサイズ（＝グラフの構成ノード数）を与えると楽。
  （→ サンプルデータ）
• また、（隣接）行列は二次元配列を用いて表現するのが自然。
  通常、化学グラフの場合、化学構造式中の構成原子数（＝ノード数）が ある程度の範囲に収まることが多いので、例えば「最大ノードサイズ１００」、 と定義（制約条件）しても良い。
• 詳細な入出力仕様等は、各自で設計・定義すること。

• クラス番号を明記すること。
  
• 用紙に横向きで印刷した場合（２ページ印刷した場合など）、 左側が上になるようにクリップで綴じること。 （用紙を文字の方向に合わせて横向きに持ったとき、右上が綴じ位置に あたるようにする）
  
  

レポートについて

• 「隣接行列」が持つ情報（意味）について確実に理解すること。
• 「サイズ２」以上への拡張は、 「隣接行列」の代わりに「距離行列」を導入すると楽。 （「パス探索」による方法と比較・考察すると良い）
  （→ 距離行列の生成）
• 部分グラフの隣接行列表現では、利用しない（存在しない）ノードの 情報は除外すること。サイズ１０の行列では構成ノード数は１０となる。 （次数ゼロのノードも存在する）
• なお、本実験では、与えられるグラフは連結グラフのみとする。 （非連結グラフ（分離グラフ）は考慮しなくても良い）

• 実行結果に対するコメント（想定どおりの結果なのか？、 問題点等はないか）を必ず記入すること。
• グラフを図示（手書きで構わない）して検証すると分かりやすい。
• 解説で例として挙げたグラフだけでなく、 他のグラフ構造でも試してみると良い。

プログラミングについて

• 作成するプログラムは、 隣接行列の読み込み、条件（サイズや出発点）の指定、探索、 及び 結果の出力、などに処理を大別できる。 必要に応じて、機能ごとにモジュール化（関数化）すると良い。
• 静的配列を用いる場合は、入力したグラフ（行列）のサイズの チェックを必ず行なうこと！
  （サイズをチェックするときには、上限だけでなく下限も確認すると良い）
• もちろん、動的処理の場合も メモリ割り当ての正否の確認や 使用後の後片付け（領域解放）が必要。
• Ｃ言語では配列添字が０から始まる （例で用いた「ノード番号」は１から）であることに注意せよ。
  （コンピュータにとっては０からの方が好都合であるが、 人間にとっては１から数える方が自然）

• 定数（配列サイズなど）は「記号定数」として define すること。 （こうすることで、どういう利点があるか？）
• コメント文を用いて、各変数等の意味（役割）を簡潔に説明すること。
• 適度に字下げ（インデント）を行なったり、空行を入れたりして、 プログラムの「構造」が分かりやすくなるように工夫すること。
• グローバル変数を乱用しないように！！
  データの流れが分かりづらく、各関数間の独立性も低くなる。 （プログラムの安全性も低下する）
• プログラム中で「コメント文」を用いて、適宜「機能」説明を行なうこと。

• printf() 関数では、例えば "%2d" などのフォーマット指定が 利用できる。 これを利用し、「隣接行列」情報などを整形出力するとより良い。
• 抽出した部分グラフのノード情報を変数（一次元配列）に格納する場合、 (a) 探索した順に該当するノード番号を格納していく （ついでに、その個数もカウントする）、 (b) あらかじめノード数分だけのフラグを用意し、 該当したノード番号のフラグを立てていく、 の大きく２とおりの実装方法が考えられる。 それぞれのメリット・デメリットも考えてみると面白い。
• 変数（構造体のタグやメンバー、定数、関数なども） の名前の付け方を工夫せよ。 できるだけ役割が分かるような名前を付けること。 （もちろん、コメント文を使って解説も書くこと）
  なお、記号定数は一般の変数と区別するため大文字で書くのが慣例です。
• 本課題で想定した部分グラフ（エッジ）の定義については、 補足説明を参 照せよ。 これとは別の定義を用いる場合には、その旨、レポート （あるいはプログラム）に明記すること。