グラフ属性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/12 14:26 UTC 版)
「グラフ (離散数学)」の記事における「グラフ属性」の解説
「:en:Glossary of graph theory」および「:en:Graph property」も参照 グラフの2辺が共通の頂点を共有する場合は、2辺が「隣接する (adjacent)」という。有向グラフの2辺は、1番目の終点が2番目の始点になっている場合に「連続する (consecutive)」という。同様に、2頂点が1辺を共有する場合は、2頂点が「隣接」する(有向グラフで、片方の頂点が始点、もう一方が終点ならば「連続」)といい、この場合に共通の1辺が2頂点を「結ぶ (join)」と言う。辺とその頂点とは「接続する (incident)」という。 頂点が1つだけで辺のないグラフは「自明なグラフ (trivial graph)」という。頂点だけからなるグラフは「辺のないグラフ (edgeless graph)」と呼ばれる。頂点も辺もないグラフは「空グラフ (null graph, empty graph)」と呼ばれたりもするが、この用語は一貫しておらず数学者全員がこの対象を容認しているわけではない。 通常、グラフの頂点は集合の元としての性質から互いに識別可能である。この種のグラフは「ラベル付き頂点を持つ (vertex-labeled)」と呼ぶ場合もある。ただし、多くの設問では頂点を識別不能として扱う方が都合が良い(もちろん、頂点はグラフ自体の属性によって、例えば接続辺の数などで、依然として識別できる場合もある)。同じことが辺にも適用されるため、ラベル付けされた辺を持つグラフは「ラベル付き辺を持つ」と呼ばれる。辺または頂点にラベルが与えられているグラフは「ラベル付き」と呼ばれるのが一般的である。したがって、頂点にも辺にも区別がないグラフを「ラベルなし (unlabeled)」と呼ぶ。 全てのグラフの圏はコンマ圏( S e t ↓ D {\displaystyle \mathbf {Set} \downarrow D} )である。ここで D : S e t → S e t {\displaystyle D:\mathbf {Set} \rightarrow \mathbf {Set} } は、集合 s {\displaystyle s} を s × s {\displaystyle s\times s} に対応付ける関手である。
※この「グラフ属性」の解説は、「グラフ (離散数学)」の解説の一部です。
「グラフ属性」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。
- グラフ属性のページへのリンク