頂点 (グラフ理論)のソースを表示

[[Image:6n-graf.svg|thumb|6 つの頂点と 7 つの辺を含むグラフ。左端の番号 6 の頂点は、葉頂点あるいはペンダント頂点と呼ばれる。]]

[[数学]]の[[グラフ理論]]の分野における'''頂点'''（ちょうてん、{{Lang-en-short|vertex}}）あるいは'''節点'''（せってん、{{Lang-en-short|node}}）とは、グラフを形成する基本的な構成単位である。頂点の数を[[位数]]（{{Lang-en-short|order}}）と呼ぶ。

[[無向グラフ]]は頂点の集合と辺（{{Lang-en-short|edge}}、向き付けのされていない頂点のペア）の集合で構成され、有向グラフは頂点の集合と弧（arc、向き付けのされている頂点のペア）の集合で構成される。グラフを図示する際、頂点は通常ラベル付けのされた円で表され、辺は各頂点から別の頂点へと伸びる直線あるいは矢で表される。

グラフ理論において、頂点は決まった形の無いそれ以上分割の出来ない物体として扱われるが、それらが応用される場面においては他の構造が付け加えられることもある。例えば、[[意味ネットワーク]]のグラフにおいては、頂点は概念やオブジェクトの類を表す。

辺を形成する二つの頂点は、その辺の端点（endpoint）と呼ばれ、その辺はそれらの頂点に接続（incident）していると言われる。ある頂点 ''w'' が別の頂点 ''v'' に隣接（adjacent）しているとは、グラフが辺 (''v'',''w'') を含むことを言う。ある頂点 ''v'' の{{仮リンク|近傍 (グラフ理論)|label=近傍|en|neighborhood (graph theory)}}とは、''v'' に隣接するすべての頂点によって形成される[[誘導部分グラフ]]のことを言う。

== 頂点の種類 ==
ある頂点の[[次数 (グラフ理論)|次数]]とは、その頂点に接続する辺の数のことである。'''孤立点'''（isolated vertex）とは、次数がゼロの頂点のことである。'''葉頂点'''（leaf vertex）あるいは'''ペンダント頂点'''（pendant vertex）とは、次数が 1 の頂点のことである。有向グラフにおいては、入次数（indegree、入ってくる辺の数）と出次数（outdegree、出ていく辺の数）が区別される。'''源点'''（source vertex）とは入次数がゼロの頂点のことであり、'''沈点'''（sink vertex）とは出次数がゼロの頂点のことである。

{{仮リンク|切断点|en|cut vertex}}（cut vertex）とは、それを除くと残されたグラフが非連結となるような頂点のことである。{{仮リンク|頂点分離|en|vertex separator}}（vertex separator）とは、それらを除くと残されたグラフがそれぞれ小さな断片へとなることで非連結となるような頂点の集まりのことである。k-頂点連結グラフとは、''k'' より少ない数の頂点を除くだけでは依然として連結であるようなグラフのことである。[[独立集合]]とは、どの二つの頂点も隣接していないような頂点の集合のことであり、[[頂点被覆]]とは、グラフの各辺の端点を含むような頂点の集合のことである。グラフの{{仮リンク|頂点空間|en|vertex space}}とは、グラフの頂点に対応する基底ベクトルの集合を備えるベクトル空間のことである。

任意の頂点を他の任意の頂点へと写すような対称性が存在するとき、そのグラフは[[頂点推移グラフ|頂点推移的]]であると言われる。{{仮リンク|グラフの列挙|en|graph enumeration}}や[[グラフ同型]]の文脈において、ラベル付けされた頂点とされていない頂点を区別することは重要である。ラベル付けされた頂点は、それを他のラベル付けされた頂点と区別することを可能にするような外的な情報を備えるものである。二つのグラフは、それらの頂点が等しいラベルを備えるもの同士でペアとされるような対応性が存在している状況に限り、同型であると見なされる。ラベル付けのされていない頂点は、そのグラフ内での隣接関係にのみ依存し、他の外的な情報には依存せず、他のラベル付けのされていない頂点と交換することが可能である。

グラフにおける頂点は、[[頂点|多角形の頂点]]と同様なものであるが、同一ではない。多角形の{{仮リンク|スケルトン (位相幾何学)|label=スケルトン|en|skeleton (topology)}}は、その頂点がグラフの頂点となるようなグラフを形成する。しかし、多角形の頂点は、グラフ理論では存在しないものとされるような付帯的な構造（幾何的な配置）も備えている。多角形の頂点の{{仮リンク|頂点図形|en|vertex figure}}は、グラフにおける頂点の近傍と相似である。

[[有向グラフ]]において、ある頂点 <math>u</math> の forward star は、その外向きの辺として定義される。頂点の集合 <math>V</math> と辺の集合 <math>E</math> を備えるグラフ <math>G</math> において、<math>u</math> の forward star は
:<math>\{(u, v) \in E\}\ </math><ref>{{harv|Gallo|Pallotino|1988|p=4}}</ref>
と表される。

== 脚注 ==
{{reflist|2}}

== 関連項目 ==
* {{仮リンク|節点 (計算機科学)|en|Node (computer science)}}

== 参考文献 ==
* {{cite journal
  | last = Gallo
  | first = Giorgio
  | authorlink = :en:Giorgio Gallo
  | last2 = Pallotino
  | first2 = Stefano
  | authorlink2 = :en:Stefano Pallottino
  | title = Shortest Path Algorithms
  | journal = Annals of Operations Research
  | volume = 13
  | issue = 1
  | pages = 1–79 <!-- the inline reference refers to page 4 -->
  | year = 1988
  | doi = 10.1007/BF02288320
  | ref=harv
  }}
* [[:en:Claude Berge|Berge, Claude]], ''Théorie des graphes et ses applications''. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
* {{Cite book | last=Chartrand | first=Gary | authorlink=:en:Gary Chartrand | coauthors= | title=Introductory graph theory | date=1985 | publisher=Dover | location=New York | isbn=0-486-24775-9 | pages=}}
* {{Cite book | author=Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. | authorlink= | coauthors= | title=Graph theory, 1736-1936 | date=1986 | publisher=Clarendon Press | location=Oxford [Oxfordshire] | isbn=0-19-853916-9 | pages=}}
* {{Cite book | last=Harary | first=Frank | authorlink=Frank Harary | coauthors= | title=Graph theory | date=1969 | publisher=Addison-Wesley Publishing | location=Reading, Mass. | isbn=0-201-41033-8 | pages=}}
* {{Cite book | author=Harary, Frank; Palmer, Edgar M. | authorlink= | coauthors= | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | location= | isbn=0-12-324245-2 | pages=}}

== 外部リンク ==
* {{mathworld | title = Graph Vertex | urlname = GraphVertex}}

{{Graph Theory-footer}}

{{DEFAULTSORT:ちようてん}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]