隣接している頂点同士をたどった v0, e0, v1, e1, ... , en?1, vn の系列を長さ n の歩道(鎖・ウォーク)という。辺の重複を許さない歩道を路(小径・トレイル)という[16]。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道(パス)、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路(回路・循環 ・サーキット、サイクル)、始点と終点が同じ道(つまり e1, e2, ... , en, e1 という路で ei が相異なるもの)のことを閉道(サイクル)という[17]。
完全グラフとクリーク3頂点からなる完全グラフ:三角形
任意の 2 頂点間に枝があるグラフのことを完全グラフ(完備グラフ)という[8][18]。n 頂点の完全グラフは、Kn で表す。K3 は三角形と呼ばれる。また、完全グラフになる誘導部分グラフのことをクリークという。大きさ(サイズ) n のクリークを含むグラフは「n-クリークである」という。辺をもつグラフは必ず2頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランという。
その他の用語body:not(.skin-minerva) .mw-parser-output .columns-list__wrapper{margin-top:0.3em}body:not(.skin-minerva) .mw-parser-output .columns-list__wrapper>ul,body:not(.skin-minerva) .mw-parser-output .columns-list__wrapper>ol{margin-top:0}body:not(.skin-minerva) .mw-parser-output .columns-list__wrapper--small-font{font-size:90%}
オイラー路(オイラー閉路・オイラーグラフ)
ハミルトン路(ハミルトン閉路・ハミルトングラフ)
木 (根つき木・森)
全域木
シュタイナー木
直径
カット
2部グラフ (n 部グラフ・彩色)
同型グラフ
連結グラフ (連結成分・連結度)
平面グラフ (平面的グラフ)
隣接行列
接続行列
次数行列
対称グラフ
マッチング
閉路グラフ
有向非巡回グラフ
独立集合
ランダム・グラフ
グラフは物理学的、生物学的[20][21]、社会的、および情報システムにおける多くの種類の関係と過程をモデル化するために使うことができる。多くの現実的問題はグラフによって表すことができる。現実世界のシステムへの応用を強調する時には、「ネットワーク」という用語がグラフを意味するために定義されることがある。このグラフでは、属性(例えば名前)が頂点および辺と関連付けられる。現実世界のシステムをネットワークとして表現し理解する主題はネットワーク科学(英語版)と呼ばれる。 計算機科学において、グラフはコミュニケーション、データ編成、計算装置、計算の流れ等のネットワークを表すために使われる。例えば、ウェブサイトのリンク構造は有向グラフとして表すことができる。ここでは、頂点がウェブページを表し、有向辺があるページから別のページへのリンクを表す。同様のアプローチを、ソーシャルメディア[22]、旅行、生物学、コンピュータチップ設計、神経変性疾患の進行のマッピング[23][24]、そしてその他多くの分野における課題について取ることができる。
計算機科学