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

今回は、「グラフ理論におけるグラフ構造」を紹介します。グラフといえば、分析やプレゼンテーション、レポートなど、一般のビジネスの現場でも幅広く活用されています。ただし、今回のテーマであるグラフ構造は、中学校や高校で学ぶ関数のグラフとは別の概念です。そんなグラフ構造が私たちの日常生活に利用されている例について、テクニカルな視点から紹介します。最後まで読めば、あなたも世界がグラフ構造として見えるようになること間違いなしです!
そもそもグラフ(構造)とは何なのか?
具体的なグラフ構造の例を紹介する前に、そもそもグラフとは何なのか?その定義から説明します。
グラフ構造は、数学的構造を扱うグラフ理論に基づいています。考察する対象を頂点で表し、対象と対象の関係を辺で結んで図で表示するという、実にシンプルなアイデアで描かれています。グラフは、ネットワーク分析や最適化問題、アルゴリズム、データ構造など、さまざまな分野で広く利用されていて、情報科学や工学にも欠かせない、重要な数学的概念です。
グラフ理論における「グラフ」とは、頂点(ノード)とその間の辺(エッジ)で作られる構造を指します。冒頭で説明したように、中学校や高校で学んだ関数のグラフとは別の概念なので、そこは注意してください。 具体例を挙げながら説明しましょう。まず下の図は、5つの頂点と5本の辺で作られる「(重みなし無向)グラフ」です。
無向グラフと有向グラフ
辺に方向がないグラフを無向(むこう)グラフ、方向があるグラフを有向(ゆうこう)グラフといいます。先の図の辺に方向を加えた下の図は、5つの頂点と5本の辺で作られる有向グラフです。
重みなしグラフと重み付きグラフ
次に、辺に「重み」を加えてみます。重みとは時間や距離などの付加情報のことです。辺に重みがないグラフを重みなしグラフ、重みがあるグラフを重み付きグラフといいます。下の図は、5つの頂点と5本の辺で作られる「重み付き(無向)グラフ」です。
日常生活で使われているグラフ構造の例
ここからは、日常生活で使われているグラフ構造の例を紹介します。グラフ理論でグラフを図示するときは頂点を数字で表すことが多いですが、今回はイメージしやすいように、頂点をイラストで表していきます。
1.会社の組織図
会社のメンバーを頂点、上司と部下の関係を辺で結ぶと、会社の組織図はグラフ構造になっています。代表取締役社長から経営層、各部署、チーム、平社員までを表すことができます。辺でつながっていて枝のように広がっていく形は、グラフ理論の用語で「木(ツリー)」と呼ばれます。グラフとして表すことで、所属や指揮の関係が一目瞭然でわかるようになりますね。
2.ソーシャルメディアのフォロー関係
ソーシャルメディアのフォロー関係は、アカウントを頂点、アカウントとアカウントのフォロー関係を辺とすると、グラフ構造として表せます。AさんがBさんをフォローしていることを「A→B」と表す方がわかりやすいので、有向グラフで定義します。
例として、次の3つのフォロー状況を考えてみます。 まず、見るのが専門のアカウントだと、次の図のような一方通行の矢印が多くなるでしょう。
逆に、著名人やインフルエンサーのような人気アカウントだと、たくさんのアカウントからフォローされて、自分向きの矢印がいっぱいになります。
仲良し同士のアカウントを並べてみると次の図のように、双方向に矢印が伸びる関係になりますね。
このように、フォロー関係をグラフ構造で表示することで、アカウントの特性を可視化することができます。
3.乗換案内アプリ
乗換案内アプリは、出発地と目的地を入力すると、条件に合ったルートを案内してくれる便利なサービスです。頂点を出発地と目的地、辺を出発地から目的地までのルートとすると、グラフ構造で表すことができます。ルートによって所要時間や運賃が異なるので、重み付き有向グラフとして表した方がよさそうです。
例えば、東京駅から神保町まで向かうルートを例として考えます。ルート1は電車(乗換1回)、ルート2 は電車(乗換1回)と徒歩、ルート3は徒歩のみの移動となっています。
この状況を、所要時間と運賃の、それぞれによる重み付けをしたグラフとして表すと次のようになります。
移動は常に、所要時間と運賃、快適さの重み付けによるバランス
ルート3は、お金がかかりませんが、24分間歩くのは大変そうです。ルート2は、ルート1よりも2分遅く着く上に割高です。ルート1が、所要時間も運賃も一番バランスのいい選択肢な気がしますね。
このように、数あるルート(経路)の中から最適なものを選ぶ問題を「経路問題」といいます。経路問題は、グラフ理論の応用である「最適化問題」の一つになっています。
今回は2点間の交通手段について考えましたが、経由地や条件を増やすとルートの選択肢は一気に増えて、解くのが難しくなるのはおわかりでしょう。
4.マッチングアプリ
婚活に限らず、ビジネスでもパートナー企業選びに使われるのが、マッチングアプリやサービスです。各ユーザーを頂点とし、互いに「いいね」を送ったユーザーを結ぶと、グラフとして表現することができます。
例えば、4人の女性と5人の男性のマッチング状況の例は次のようになります。
このグラフを観察すると、BさんはEさんとしかマッチしていなかったり、Cさんは4人の男性とマッチしていることが見えてきます。
このようにグラフ化することで、ユーザー間の関係の分析や、ネットワーク全体の構造解析が可能になったり、新たなマッチングを促進する必要性に気づいたり、さまざまな情報の抽出や考察につながります。
グラフ構造が使われているその他の例
上記で挙げた以外にも、日常生活でのグラフ構造として認識できる例をいくつか挙げてみます。
交通ネットワーク:都市や地点を頂点、それらをつなぐ道路や鉄道路線を辺と見なすことができます。例えば、地下鉄の路線図や航空会社のフライトマップは具体的なグラフ構造の一例です。
インターネット:Webページを頂点とし、それらのページ間のリンクを辺として考えることができます。SEO(検索エンジン最適化)で、読者にとって有益だと認められるのは、まさにこの仕組みが使われています。
電力網:発電所や変電所、家庭や企業などの電力を消費する場所を頂点、電力の流れる経路を辺として表現することができます。
世の中の関係には、方向と重みがある!
今回の記事では、グラフの基本概念について解説し、日常生活で使われているグラフ構造の例をいくつか紹介しました。グラフとして捉えることで、対象の特徴を可視化し、重要な情報を抽出することが可能となります。さらに、最適化問題へのアプローチとしても役立ちます。
今回の記事で紹介した以外にも、実は日常生活の中には数多くのグラフ構造が隠れています。一見複雑に見える状況でも、それをグラフとして捉えることで、新たな発見や解決につながるかもしれません。ぜひ、身の回りのグラフ構造を探し、自己の視野を広げてみてください。
参考文献
- 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本(米田優峻著、技術評論社)
https://www.amazon.co.jp/dp/B09NXFQRD3
- グラフ理論入門(R. J. ウィルソン著、西関隆夫・西関裕子共訳、近代科学社)
https://www.amazon.co.jp/dp/B07J1X51TD