- graph
vertexとedgeの集合。
- vertex
点。
- edge
二つのvertexの非順序対。辺。
- adjacent
edgeで繋がれている二つのvertex間の関係。もしくは、veterxを共有している二つのedgeの関係。隣接。
- incident
edgeにvertexが含まれているときの「edgeとvertex」の関係。接続。adjacentとの混同に注意。
- degree
あるvertexにincidentしているedgeの数。
- isolated vertex
degreeが0のvertex
- end vertex
degreeが1のvertex
- loop
同じvertexによるedge。
- simple graph
loopやmultiple edgeを含まないgraph。
- directed graph (digraph)
edgeが非順序対ではなく、順序対になったgraph。
- walk
あるvertexからあるvertexへの行き方。vertexの有限列。ただし、隣り合う項の対はedge setに含まれていなければならない。walkに含まれるedgeの数が長さとして定義される。歩道。
- trail
含まれるedgeが全て異なるwalk。小道。
- path
どのvertexも高々一つしか現れないwalk。道。
- cycle
出発と終着が同じpath。walkでもcycleと言うのか不明。
- Eulerian graph
全てのedgeを一回ずつ通って出発点に戻るwalkを持つgraph。
- Hamiltonian graph
全てのvertexを通るcycleがpathになっているgraph。
Eulerian graphのvertex version。
- connected graph
どのvertexもwalkで繋げることのできるgraph。
- disconnected graph
walkで繋げることのできないgraphを含むgraph。connected graphのunion。
- subgraph
vertex setおよびedge setが部分集合になっていて、それら部分集合がgraphを成しているもの。
- complement
vertex setは同じで、adjecentでなかったvertexを繋いだgraph。補グラフ。
- tree
どのvertex間もpathが一つしかないgraph。
- planar graph
交差が無いように書き直せるgraph。
- regular graph
どのvertexのdegreeも等しいsimple graph。
- complete graph
相異なるvertexが全てadjacentにあるsimple graph。と書き、edgeの数は
。
degree のregular graphとも言える。
- cycle graph
degree 2のregular graph。vertexの数がのcycle graphを
と書く。
- path graph
cycle graphからedgeを一つ取り除いたgraph。と書く。
- wheel
にvertexを一つ足し、他の全てのvertexとadjacentになるようにedgeを追加したgraph。
と書く。
- bipartite graph
graphのvertex setを互いに素な二つのvertex setに分け、graphの全てのedgeが分割したvertex set間を繋いでいるとき、このgraphはbipartite graphと呼ばれる。
- complete bipartite graph
分割したvertex set間の各点が相手のvertex setのvertex全てと隣接しているとき、このgraphはcomplete bipartite graphと呼ばれる。
- contraction
あるedgeを消去し、それにincidentしていた二つのvertexを統合して一つのvertexにすること。縮約。
- isomorphic
二つのgraph間でvertexとedgeが一対一対応する状態。同形。
- self complementary
complementが元のgraphとisomorphicな状態。自己補対。
- automorphism
vertex setに対して全単射でかつedge setの構造を保存している写像。自己同形写像。
参考文献：グラフ理論入門
