Homomorphisms of Graphs

準同型同値性とcore

このように準同型の存在性を議論する上で，次のような概念がある．

定義：
グラフG₁とG₂に対して，G₁→G₂とG₂→G₁の両方の準同型が存在するとき，G₁とG₂は準同型同値である(homomorphically equivalent)という．

準同型同値性が名前の通り同値関係になっていることは簡単に確認できる．

例えば，次の2つのグラフは準同型同値である．

準同型同値性が準同型の存在性に役立つのは，次の性質である．

性質：
グラフG₁とG₂が準同型同値であるとき，別のグラフHに対して，

準同型 H→G₁があることと，準同型 H→G₂があることは同値である．
準同型 G₁→Hがあることと，準同型 G₂→Hがあることは同値である．

(証明は準同型の合成が準同型になることから直ちに出来る．)
つまり，準同型の存在性を議論する場合，準同型同値なグラフに関しては区別する必要がないということである．

上の準同型同値なグラフの例をよく観察してみると，あることに気づくだろう．それは，G₁もG₂も2頂点1辺からなるグラフ(K₂)と準同型同値であり，実はK₂を介して2つのグラフが準同型同値になっている，とういことである．(そして，K₂はG₁,G₂両者の部分グラフでもある．)

以下，この現象を一般的に説明してみよう．

まず，coreという概念を定義する．

定義：
グラフXがcoreグラフであるとは，Xから自分自身への準同型が必ず全単射になることである．
また，グラフXの部分グラフYがcoreグラフであり，XからYへの準同型が存在するとき，YはXのcoreである，という．

(注：coreグラフXから自分自身への準同型は同型になる．(∵ この準同型は全単射であることから，辺に関して単射であることが分かる．写像の前と後で辺数が一致するためには，同型写像(辺がない2頂点の写される先には辺がない)になっていなければならない．))

例えば，上のグラフの例だと，G₁もG₂もcoreグラフではないが，K₂はcoreグラフである．そして，K₂はG₁およびG₂のcoreとなっている．
(注：ここでは分かりやすいように「coreグラフ」と「core」と使い分けているが，通常は両方とも「core」と呼ばれる．)

まず，coreグラフが次のような強い性質を持つことが分かる．

補題１：
XおよびYがcoreグラフとする．このとき，XとYが準同型同値であれば，XとYは同型である．

(証明)
準同型f:X→Yとg:Y→Xが存在するとすると，fｏgおよびgｏfはそれぞれX→XとY→Yの準同型になる． XとYはそれぞれcoreグラフであるから，fｏgとgｏfは両方とも全射となり，fもgも全射ということになる．すると，ここから，XとYが同型であることはすぐに出てくる． (∵ まず，(X,Yの頂点集合が有限集合であることから) f,gが共に全単射であることが分かる．すると，各辺も単射で写ることになるため，f:X→Yに注目するとYの辺数はXの辺数以上になり，g:Y→Xに注目すると，Xの辺数はYの辺数以上いなる．したがって，両者の辺数は等しくなるが，これは，Xの頂点u,vに対して，uvが辺でない場合に必ずf(u)f(v)が辺でないという場合に限る．) □

次に，グラフGのcoreが基本的に一意に定まることを見る．

補題２：
任意のグラフGに対して，Gはcoreを誘導部分グラフとして持ち，また，X₁とX₂という2つのcoreがある場合は，それらは互いに同型である．

(注：Xが「誘導部分グラフ」とは，u,vがXの頂点のとき，uvがGで辺になっていたらXでも辺になっているような部分グラフのこと．(「頂点集合によって誘導される部分グラフ」という意味．))

(証明)
まず，Gの部分グラフでGからの準同型があるものをすべて考えると，(頂点集合の)部分集合の包含関係で極小なものが得られる．(G自身がGからの準同型を持つので，必ず存在する．) すると，それらがcoreである．(もしそれらが全射でない自己準同型を持つと極小性に反する．)

Gからそのcore Xへの準同型fを考えると，fのXへの制限f|XはXからXへの準同型になる． Xはcoreグラフなので，f|Xは同型．f|Xの逆写像をhとすると，fｏhはGからXへの準同型で，Xへの制限は定値写像となる．しかし，ここでXが誘導部分グラフでないとすると，fｏhは準同型にならず，矛盾となる．したがって，coreは誘導部分グラフである．

X₁とX₂がGのcoreとする．f₁:G→X₁, f₂:G→X₂を準同型とすると， f₁のX₂への制限はX₂からX₁への準同型となり， f₂のX₁への制限はX₁からX₂への準同型となる．したがって，上の補題１からX₁とX₂は同型であることになる． □

この補題２によって，「グラフGのcore」という呼び方で1つのグラフ(の同型類)が特定されることになる．そして，次の定理によって，このcoreが準同型同値性を特徴付けるものであることが分かる．

定理：
グラフG₁とG₂のcoreがそれぞれX₁とX₂とする．このとき， G₁とG₂が準同型同値であることと，X₁とX₂が同型であることは同値．

(証明)
G₁→X₁，g:G₂→X₂それぞれに準同型が存在するので，

G₁とG₂が準同型同値であれば，
X₁→G₁→G₂→X₂
X₂→G₂→G₁→X₁
という準同型が存在するので，上の補題から，X₁とX₂は同型．
X₁とX₂が同型であれば，
G₁→X₁→X₂→G₂
G₂→X₂→X₁→G₁
という準同型が存在するので，G₁とG₂は準同型同値．

□

<7章へ | 目次 |