部分グラフと拡大グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/02 08:06 UTC 版)
「グラフ理論」の記事における「部分グラフと拡大グラフ」の解説
2つのグラフ G {\displaystyle G} と G ′ {\displaystyle G'} について、 G ′ {\displaystyle G'} の頂点集合と辺集合が共に G {\displaystyle G} の頂点集合と辺集合の部分集合になっているとき、 G ′ {\displaystyle G'} は G {\displaystyle G} の部分グラフである、または G {\displaystyle G} は G ′ {\displaystyle G'} の拡大グラフであるといい、 G ′ ⊆ G {\displaystyle G'\subseteq G} と表す。特に、 G {\displaystyle G} と G ′ {\displaystyle G'} の頂点集合が等しいとき、 G ′ {\displaystyle G'} は G {\displaystyle G} の全域部分グラフであるという。また、 G {\displaystyle G} の頂点集合 V {\displaystyle V} の部分集合 U {\displaystyle U} を取り出して、両端点が U {\displaystyle U} に属する全ての辺を辺集合とする G の部分グラフ G [ U ] {\displaystyle G[U]} を、誘導部分グラフという。グラフ G {\displaystyle G} からある辺 e {\displaystyle e} を取り除き、その辺の両端点を一つの頂点にまとめることを（辺の）縮約といい、縮約の結果得られるグラフを G / e {\displaystyle G/e} と表す。 なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」がある。このため、誘導部分グラフのことを生成部分グラフということもある。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。
※この「部分グラフと拡大グラフ」の解説は、「グラフ理論」の解説の一部です。
「部分グラフと拡大グラフ」を含む「グラフ理論」の記事については、「グラフ理論」の概要を参照ください。
- 部分グラフと拡大グラフのページへのリンク
