入次数とは？グラフ理論における基本概念を解説
入次数（いりじすう）とは、
グラフ理論においてある頂点に向かって入ってくる辺の本数を表す指標です。
特に有向グラフで重要な概念として扱われ、
情報処理やアルゴリズム、ネットワーク解析など幅広い分野で利用されます。
ITパスポート試験や基本情報技術者試験などでも頻出の用語であり、
正確な理解が求められます。
目次
入次数と出次数の違い
有向グラフでは、辺には向きがあり、
次数は次の2種類に分けられます。
- 入次数：頂点に入ってくる辺の数
- 出次数：頂点から出ていく辺の数
例えば、ある頂点Aに向かって3本の矢印が入り、
2本の矢印が出ている場合、
Aの入次数は3、出次数は2となります。
無向グラフとの関係
無向グラフでは辺に向きが存在しないため、
入次数や出次数という区別はありません。
その代わり、単に「次数」として
その頂点に接続されている辺の本数を数えます。
この点は、有向グラフ特有の概念であることを
理解しておくことが重要です。
入次数が使われる代表的な場面
入次数は、次のような場面で活用されます。
- タスクの依存関係分析
- トポロジカルソート
- ネットワーク構造の解析
特にトポロジカルソートでは、
入次数が0の頂点から順に処理を行うことで、
依存関係を守った順序付けが可能になります。
情報システム分野での具体例
業務フローや処理手順を有向グラフで表現すると、
ある処理に入次数が多い場合は、
「多くの前提条件を持つ処理」であることが分かります。
これにより、ボトルネックの特定や
業務改善の検討にも役立ちます。
まとめ
入次数とは、
有向グラフにおいて頂点に入ってくる辺の数を表す重要な概念です。
出次数との違いを正しく理解することで、
アルゴリズムやネットワーク構造の理解が深まります。
情報処理試験対策だけでなく、
実務での設計や分析にも役立つため、
ぜひ基礎として押さえておきましょう。