グラフ理論
根上生也『離散構造』共立出版〈情報数学講座 3〉、1993年。ISBN 4-320-02653-5。
秋山仁、ロナルド・ルイス・グラハム『離散数学入門』朝倉書店〈入門有限・離散の数学 1〉、1993年。ISBN 4-254-11419-2。
秋山仁 『グラフ理論最前線』朝倉書店 ISBN 978-4-254-11420-1.
加納幹雄 『情報科学のためのグラフ理論』朝倉書店 ISBN 978-4-254-11424-9.
ハラリー, フランク 著、池田貞雄 訳『グラフ理論』共立出版、1971年。ISBN 978-4-320-01073-4。
茨木俊秀『アルゴリズムとデータ構造』昭晃堂、1986年。ISBN 4-7856-0119-1。
鈴木晋一編著 『数学教材としてのグラフ理論』, 早稲田教育叢書 31, 学文社, ISBN 978-4-76202-253-1
ノラ・ハーツフィールド&ゲーハード・リンゲル著 鈴木晋一訳,『グラフ理論入門』,サイエンス社, ISBN 978-4-78190-654-6
ボロバシュ・ベーラ著 斎藤伸自, 西関隆夫訳,『グラフ理論入門』,培風館, ISBN 978-4-56300-544-3
オイラー路(オイラー閉路・オイラーグラフ)
ハミルトン路(ハミルトン閉路・ハミルトングラフ)
木 (根つき木・森) 全域木 シュタイナー木
直径
カット
2部グラフ (n 部グラフ・彩色)
同型グラフ
連結グラフ (連結成分・連結度)
平面グラフ (平面的グラフ)
隣接行列
接続行列
次数行列
対称グラフ
マッチング
閉路グラフ
有向非巡回グラフ
独立集合
ランダム・グラフ(英語版)
マイナー (グラフ理論)(英語版)
グラフ代数(英語版)
空グラフ
量子グラフ
辺 e {\displaystyle e} の両端の点を端点といい、端点は辺 e {\displaystyle e} に接合(または接続)しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接しているという。
数学では、グラフは幾何学ならびに結び目理論といったトポロジーの特定の分野において有用である。代数的グラフ理論は群論と密接なつながりを持つ。代数的グラフ理論は動的系や複雑性を含む多くの分野に応用されている。
様々な形式のグラフ理論的手法は言語学において特に有用であることが証明されている。これは、自然言語がしばしば離散構造へとよく適しているためである。伝統的に、統語論と合成意味論は木構造に従い、それらの表現力は、階層的グラフによってモデル化される構成性の原理(英語版)に密接に関係する。主辞駆動句構造文法といったより現代的な手法は型付き素性構造(これは有向非巡回グラフである)を用いて自然言語の構文をモデル化する。語彙意味論内、特に計算機へ応用としては、単語の意味のモデル化は、与えられた単語が関連する単語の観点から理解される時により容易である。したがって意味ネットワークは計算言語学において重要である。今で、哲学(例えば、格子グラフ(英語版)を用いる最適性理論)や形態論(例えば有限状態トランスデューサ(英語版)を用いる有限状態形態論)におけるその他の手法は、グラフとしての言語の解析において一般的である。実際、この数学の分野の言語学への有用性は、TextGraphs、WordNetやVerbNet(英語版)といった様々な "Net" プロジェクトのような組織を生んできた。
P(V) を V の冪集合とする。E の元に V の 部分集合を対応させる写像
g : E → P ( V ) {\displaystyle g\colon \ E\to P(V)}
があって、E の任意の元 e について、e の像 g(e) の濃度が1または2であるとき、三つ組
G := ( g , V , E ) {\displaystyle G:=(g,V,E)}
を無向グラフという。V の元を G の頂点、E の元を G の辺と呼ぶ。 g(e)の濃度が1となるe∈Eはループに対応し、g(a)=g(b)となるa,b∈Eは多重辺に対応する。
単純グラフに限って言えば、E を最初からある集合の部分集合と考え、写像を用いずにグラフを定義することもできる:有向グラフでは、E を V×V の部分集合、無向グラフでは、E を P(V) の部分集合で、2つの元の集合だけからなるものとすればよい。