路のうち、同じ頂点を二度通らないものをパスとよびます。路のうち、始点と終点が等しいものをサイクルとよびます。連結であるといいます。強連結であるといいます。グラフの例グラフは非常に強力な数理科学的ツールです。世の中の多くの問題は、グラフを用いてモデル化することで、グラフに関する問題として定式化することができます。様々な分野における問題が、グラフに関する問題として統一的に扱うことができるのです。ここでは対象物をグラフを用いて定式化する例をいくつか挙げます。(下図は下記記事より引用)。日本の中心はどの県だ?グラフ理論(ネットワーク)の基本的な諸概念これは、日本の各都道府県を頂点とし、県境が隣接している都道府県同士を辺で結んだグラフとなっています。沖縄は孤立点となっていますね。もっちょさんのブログでも触れられていますが、実際の県の位置は関係なく「どのように繋がっているか」について様々な考察を与えることができるのがグラフを用いた定式化のメリットになります。(ネットワークフロー理論につながります)といった問題意識が沸き起こります。これらは本記事の範囲外ですが、グラフを学ぶことでこれらの問題意識に対して有意義な知見を獲得することができます。論文の共著者関係などがあります。回くらいで世界中のほとんどの人に行き渡るという話を聞いたことのある方は多いかもしれません。お馴染みの「知り合いかも?」をレコメンドするコミュニティを検出する影響力の高い人を検出したり、ネットワークの情報伝播力を解析したりするといった問題意識が大変重要です。ような形をしており、上にあげた「都道府県の隣接関係」や下にあげる「道路ネットワーク」とは根本的に異なる性質を有することが多いです。ソーシャルネットワークに特有の構造について関心のある方は、以下の記事たちが大変面白いです。下図はこのページより引用しています。見た目からして、道路ネットワークはソーシャルネットワークとは大きく性質が異なります。道路ネットワークに特徴的な性質として、平面的であることが挙げられます。平面グラフに近い性質を持つことを活かしたアルゴリズムなどに関心のある方は以下の資料が大変面白いです。将棋やオセロといったゲームの解析も、グラフ探索の重要な例になっています。(このページから引用)。各局面が頂点、局面遷移が辺に対応する有向グラフです。作成したりできるようになります。ゲームの解析に関する話は以下の記事にまとめたので是非読んでいただけたらと思います。「このタスクが終わらなければ、このタスクを始められない」といったタスクの依存関係もグラフで表すことができます。クラス図における継承関係といったものもグラフで表すことができます。タスクの依存関係を整理したり、依存関係を制約条件として物事を最適化したりする場面において、グラフが有効に用いられることが多々あります。計算機上でのグラフの表し方グラフ探索アルゴリズムを実装する前に、計算機上でグラフを表現するデータ構造について簡単に述べます。つがありますが、本記事では隣接リスト表現のみを取り上げます。多くのグラフアルゴリズムは、隣接リスト形式の方が効率良く実現できることが多いです。