2023.06.29 2023.12.27

組織図やSNS、マッチング関係も！数学的に可視化するグラフ構造

理人

今回は、「グラフ理論におけるグラフ構造」を紹介します。グラフといえば、分析やプレゼンテーション、レポートなど、一般のビジネスの現場でも幅広く活用されています。ただし、今回のテーマであるグラフ構造は、中学校や高校で学ぶ関数のグラフとは別の概念です。そんなグラフ構造が私たちの日常生活に利用されている例について、テクニカルな視点から紹介します。最後まで読めば、あなたも世界がグラフ構造として見えるようになること間違いなしです！

そもそもグラフ（構造）とは何なのか？

具体的なグラフ構造の例を紹介する前に、そもそもグラフとは何なのか？その定義から説明します。

グラフ構造は、数学的構造を扱うグラフ理論に基づいています。考察する対象を頂点で表し、対象と対象の関係を辺で結んで図で表示するという、実にシンプルなアイデアで描かれています。グラフは、ネットワーク分析や最適化問題、アルゴリズム、データ構造など、さまざまな分野で広く利用されていて、情報科学や工学にも欠かせない、重要な数学的概念です。

グラフ理論における「グラフ」とは、頂点（ノード）とその間の辺（エッジ）で作られる構造を指します。冒頭で説明したように、中学校や高校で学んだ関数のグラフとは別の概念なので、そこは注意してください。具体例を挙げながら説明しましょう。まず下の図は、5つの頂点と5本の辺で作られる「（重みなし無向）グラフ」です。

無向グラフと有向グラフ

辺に方向がないグラフを無向（むこう）グラフ、方向があるグラフを有向（ゆうこう）グラフといいます。先の図の辺に方向を加えた下の図は、5つの頂点と5本の辺で作られる有向グラフです。

重みなしグラフと重み付きグラフ

次に、辺に「重み」を加えてみます。重みとは時間や距離などの付加情報のことです。辺に重みがないグラフを重みなしグラフ、重みがあるグラフを重み付きグラフといいます。下の図は、5つの頂点と5本の辺で作られる「重み付き（無向）グラフ」です。

日常生活で使われているグラフ構造の例

ここからは、日常生活で使われているグラフ構造の例を紹介します。グラフ理論でグラフを図示するときは頂点を数字で表すことが多いですが、今回はイメージしやすいように、頂点をイラストで表していきます。

1.会社の組織図

会社のメンバーを頂点、上司と部下の関係を辺で結ぶと、会社の組織図はグラフ構造になっています。代表取締役社長から経営層、各部署、チーム、平社員までを表すことができます。辺でつながっていて枝のように広がっていく形は、グラフ理論の用語で「木（ツリー）」と呼ばれます。グラフとして表すことで、所属や指揮の関係が一目瞭然でわかるようになりますね。