グラフ理論
計算機科学において、グラフはコミュニケーション、データ編成、計算装置、計算の流れ等のネットワークを表すために使われる。例えば、ウェブサイトのリンク構造は有向グラフとして表すことができる。ここでは、頂点がウェブページを表し、有向辺があるページから別のページへのリンクを表す。同様のアプローチを、ソーシャルメディア、旅行、生物学、コンピュータチップ設計、神経変性疾患の進行のマッピング、そしてその他多くの分野における課題について取ることができる。したがって、グラフを取り扱うためのアルゴリズムの開発が計算機科学における主要な興味である。グラフの変換(英語版)はグラフ書換え系によってしばしば定式化され、表現される。グラフ変換系と相補的なグラフの規則に基づくメモリー内操作に注目したシステムが、グラフ構造を持つデータのトランザクションセーフで永続的な格納と問い合わせに対応したグラフデータベース(英語版)である。
グラフ構造は、グラフのそれぞれの辺に重みを割り当てることによって拡張することができる。重み付きグラフは、対ごとのつながりが何らかの数値を持つ構造を表わすために使われる。例えば、グラフが道路網を表わすとすると、重みは各道路の長さを表わすことができるだろう。それぞれの辺に関連した複数の重み(距離、旅行時間、金銭的コストなど)が存在するかもしれない。このような重み付きグラフはGPSおよび飛行時間と費用を比較する旅行計画探索エンジンをプログラムするために一般的に使われる。
隣接している頂点同士をたどった v 0 , e 0 , v 1 , e 1 , . . . , e n − 1 , v n {\displaystyle v_{0},~e_{0},~v_{1},~e_{1},...,~e_{n-1},~v_{n}} の系列を長さ n (≥ 0) の歩道(鎖・ウォーク)という。辺の重複を許さない歩道を路(小径・トレイル)という。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道(パス)、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路(回路・循環 ・サーキット、サイクル)、始点と終点が同じ道(つまり e 1 , e 2 , . . . , e n , e 1 {\displaystyle e_{1},~e_{2},~...,~e_{n},~e_{1}} という路で e i {\displaystyle e_{i}~} が相異なるもの)のことを閉道(サイクル)という。
2頂点間(隣接している必要はない)を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフ G の最大頂点間距離を直径と呼び、diam(G) と表す。