平滑化することにより、与えられたグラフに同相の最小のグラフを作成します
同相写像クラス $ \mathcal{H}(G) $ グラフの $G$ は、トポロジー的に同型であるグラフの同型クラスのセットです。 $G$。尋ねるのは自然です：同相写像のクラスに「最小の」代表はありますか？はいの場合、それを見つける方法は？残念ながら、グーグルですばやく検索したところ、この問題について有用な結果は見つかりませんでした。
それにもかかわらず、直感に導かれて、私は次の仮説を立てています。
グラフに同相の最小のグラフは、すべての最大の耳を滑らかにすることによって得られます。
この投稿では、証明をスケッチしようとしていますが、証明にギャップがあるため、私の仮説が実際に正しいかどうかはわかりません。私の間違いを指摘し、ギャップを埋めてくれた人に感謝します。
警告：これは長い投稿になります
まず、いくつかの用語を明確にしましょう。「耳」という用語は、さまざまなグラフ理論の教科書でさまざまなことを意味します。この投稿では、次の定義を採用しています。
定義1
グラフの耳は次のいずれかです。
- おそらく1つの頂点を除くすべてが次数であるサイクル $2$、または
- すべての内部頂点が次数であるパス $2$。
最大の耳は、大きな耳の適切なサブグラフではない耳です。同様に、最大の耳は次のいずれかです。
- それ自体が連結成分全体であるサイクル
- ちょうど1つの頂点が次数であるサイクル $ \geq 3 $、他のすべての頂点は次数ですが $2$
- すべての内部頂点が次数であるパス $2$、両端の頂点は次数ですが $ \neq 2 $
グラフのトポロジーを保持する2つの一般的な操作は、細分割と平滑化です。
定義2
エッジを細分化するということは、それを耳に置き換えることを意味します。もっと正確に言えば、$e = uv$ エッジになります。
場合 $u = v$、次に自己ループを細分化します $e$ サイクルで置き換えることを意味します $C$、および $u = v$ 上の頂点になります $C$、程度がある場合とない場合があります $2$、かどうかに応じて $e$ 分離されています。
一方、 $u \neq v$、次に細分化 $e$ パスに置き換えることを意味します $P$、および $u, v$ の終了頂点になります $P$。
グラフを細分割するということは、エッジで細分割するシーケンスを実行することを意味します。
定義3
耳を滑らかにするということは、耳を単一のエッジに置き換えることを意味します。もっと正確に言えば、$C$ 耳になりなさい。
場合 $C$ サイクルであり、その後スムージング $C$ セルフループに置き換えることを意味します $e$、および次数の頂点 $ \neq 2 $ オン $C$ に入射する唯一の頂点になります $e$ （すべての頂点がオンの場合 $C$ 程度です $2$、任意の頂点を選択するだけです）。
一方、 $C$ 実際にはパスです $P$、次にスムージング $P$ ループレスエッジに置き換えることを意味します $e$、およびの終了頂点 $P$ の終了頂点になります $e$。
グラフの平滑化とは、耳の平滑化のシーケンスを実行することを意味します。
次に、グラフのトポロジーに関する次の古典的な結果が得られます。
定理1
2つのグラフは、一方が他方の細分割および平滑化操作のシーケンスから取得できる場合にのみ、同相です。
証明：この投稿を参照してください。
定理2
しましょう $G$ そして $H$2つの同相グラフになります。次に$ |V(G)| = |V(H)| $ 場合に限り $ |E(G)| = |E(H)| $。
証明のスケッチ：細分割（またはスムージング）は常に頂点とエッジの数を同じ数だけ増やします（または減らします）。$\square$
定理2に照らして、グラフの同相写像クラスの順序を定義できます。
定義4
しましょう $ \mathcal{H}(G) $ グラフの同相写像クラスである $G$。順序を定義する$\preceq$ オン $ \mathcal{H}(G) $ 沿って： $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ のために $ G_1, G_2 \in \mathcal{H}(G) $。
場合 $ G_1 \preceq G_2 $ そして $ G_2 \preceq G_1 $、次に $ G_1 \sim G_2 $。
注文 $\preceq$は完全な前順序です。つまり、推移的であり、任意の2つの同相グラフが比較可能です。残念ながら、それは完全な注文ではありません。$ G_1 \sim G_2 $ 意味しません $ G_1, G_2 $ 定理2が意味する場合でも、同型である $ |E(G_1)| = |E(G_2)| $。
定理3
孤立した頂点のないグラフは、最大の耳のエッジ非交和に一意に分解できます。
証拠のスケッチ：
しましょう $G$孤立した頂点のないグラフである。関係を定義する$R$ オン $E(G)$ 沿って： $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ のために $ e, f \in E(G) $。
次に $R$ の同値関係です $E(G)$、各同値類には、ちょうど1つの最大耳のエッジが含まれています。したがって、$R$ の分解を誘発します $G$最大の耳のエッジ非交和に。逆に、そのような分解は、$R$、したがって、分解は一意です。 $\square$
上記の分解に基づいて、次のように定義できます。
定義5
すべての最大の耳が長さである場合、孤立した頂点のないグラフはスムーズと呼ばれます $1$。グラフの場合$G$ 孤立した頂点がない場合、すべての最大の耳を平滑化することで得られる滑らかなグラフ $G$ として示されます $ \text{Smooth} (G) $。
「なめらかなグラフ」という言葉は標準ではありませんが、そのようなグラフの既存の言葉が見つからなかったので、自分で作り上げました。
定理4
しましょう $G$ 孤立した頂点のない滑らかなグラフであり、 $ H \in \mathcal{H}(G) $、その後 $ G \preceq H $。また、$ G \sim H $ 場合に限り $H$ 滑らかなグラフです。
証拠のスケッチ：
定理1による $H$ の細分割および平滑化操作のシーケンスから取得できます $G$。操作の各ステップでは、最大の耳の1つだけを、長さが異なる可能性のある別の最大の耳に変更することしかできません。
一方、滑らかなグラフでは、すべての最大の耳はすでに可能な限り短い長さを持っています（つまり、 $1$）、したがって、細分割と平滑化のシーケンスは、頂点の数をさらに減らすことはできません。したがって、$ |V(G)| \leq |V(H)| $ 平等は、次の場合にのみ成立します。 $H$ スムーズです。 $\square$
次の主張は直感に基づいていますが、それを証明する方法がわかりません。それは私の全体の証拠のギャップがあるところです。
クレーム0
しましょう $G$ そして $H$孤立した頂点のない2つの滑らかなグラフになります。それらが同型である場合、それらは同型です。
最後に、上記の主張を仮定すると、主な仮説を証明することができます。
主な仮説
クレーム0が正しいと仮定し、 $G$孤立した頂点のないグラフである。次に$ \text{Smooth} (G) $ のユニークな最小グラフです $ \mathcal{H} (G) $ 注文に関して $ \preceq $。
証明：
事実 $ \text{Smooth} (G) \preceq H $ すべてのために $ H \in \mathcal{H} (G) $ 定理4から続く。
一意性を証明するために、 $ H \in \mathcal{H} (G) $ そのようなこと $ \text{Smooth} (G) \sim H $。以来$ \text{Smooth} (G) $ スムーズで $ H \in \mathcal{H} (\text{Smooth} (G)) $、定理4による $H$スムーズです。クレーム0は、$H$ 同型です $ \text{Smooth} (G) $。 $\square$
質問：
- クレーム0は正しいですか？それを証明する方法は？
- クレーム0が間違っていても、私の主な仮説は正しいですか？
- 私の証明に他の間違いはありますか？
- すべての最大の耳が長さであるグラフのより良い用語はありますか $1$、「滑らかなグラフ」以外？
回答
あなたの証明は私には正しいようです。グラフに孤立した頂点がないと仮定する理由がわかりません。どこでも違いがありますか？また、「スムーズグラフ」は、2次の頂点がないグラフの名前のようです。（より正確には、次数2の頂点は、ループのある孤立した頂点のみです。）
私はあなたの主張の証拠をあげます。問題のグラフは接続されており、少なくとも1つのエッジがあると想定できます。任意のグラフに$G$、頂点カラーグラフを関連付ける $Ear(G)$ 次のように：
- の頂点 $Ear(G)$ のユニークな分解で耳に対応します $G$最大の耳に。耳が小道なのか周期なのかによって、青と赤に色分けされています。
- 対応する耳に共通の頂点がある場合、2つの頂点は隣接しています。それらに2つの共通の頂点がある場合、2つの平行なエッジを描画します。（これは、対応する耳がパスである場合にのみ発生する可能性があります。）
定理4の証明に多かれ少なかれ暗黙のうちに行われるべき2つの観察があります。
- 場合 $G$ そして $H$ 同相であり、 $Ear(G)$ そして $Ear(H)$同型であり、同型は頂点の色を保持します。これは、平滑化と細分割の両方が保持されることを確認した後の定理1から得られます。$Ear(G)$。
- 場合 $G$ 滑らかで、（色を無視して） $Ear(G)$の折れ線グラフです$G$、ループと複数のエッジを持つグラフに対して適切に定義されています。
便利なことに、ホイットニーの定理は、2つの接続された単純なグラフの折れ線グラフが同型である場合、グラフが三角形である場合を除いて、グラフ自体が同型であると述べています。$K_3$ と爪 $K_{1,3}$。三角形は滑らかではないことに注意してください。ループと平行エッジのあるグラフの場合、状況はより複雑になります（ただし、この記事*によると、ペイウォールリンクしか見つかりませんでした。おかしなことに、タイトルにホイットニーの名前のつづりが間違っています）。 、しかし私たちの場合、頂点彩色と定理4は、元のグラフを一意に再構築するのに十分な情報を提供します。おそらく自分でこれを整理することもできますが、完全を期すために詳細を説明します。
だから、 $G$ そして $H$ スムーズで $Ear(G)$ そして $Ear(H)$同型です。まず、ループを扱います。これらは、の赤い頂点に正確に対応します。$Ear(G)$ そして $Ear(H)$。したがって、次のように表すと$G'$ そして $H'$ のループを削除して得られたグラフ $G$ そして $H$、その後 $Ear(G')$ そして $Ear(H')$ から赤い頂点を削除することによって取得されます $Ear(G)$ そして $Ear(H)$; 特に、それらは同型です。今それを示すのに十分です$G'$ そして $H'$ は同型であるため、ループの位置はによって一意に決定されます。 $Ear(G)$：の頂点 $G'$ の赤い頂点に隣接するエッジがそれに入射する場合にのみループがあります $Ear(G)$、または $G'$ この単一の頂点で構成されます（グラフに少なくとも1つのエッジがあると想定したため）。
したがって、私たちは $G$ そして $H$ループは含まれていません。これで、平行なエッジを処理する必要があります。2つのエッジが平行である場合$G$、次に私たちの構築により、対応する頂点は $Ear(G)$2つの平行なエッジで接続されています。より一般的には、2つ以上の平行なエッジ$G$ のクリークに対応 $Ear(G)$すべてのエッジが2倍になります。のすべての頂点$Ear(G)$ は「ダブルクリーク」（サイズ1の可能性がある）などの固有の最大値に含まれ、これらのクリークを縮小し、新しく形成された平行エッジを単一のエッジに置き換えることにより、基礎となる単純なグラフの折れ線グラフを取得します。 $G$。これは逆方向にも機能するため（つまり、単純なグラフと$Ear(G)$ 回復できる $G$）、私たちは $G$ そして $H$ シンプルです。
ホイットニーの定理で終わりますよね？まあ、それほど速くはありません。ループと平行エッジを残した後、$G$ そして $H$、三角形が残っており、 $K_{1,3}$：結局のところ、エッジが2倍になった三角形は滑らかです。しかし、これは定理4によって除外されています：オリジナル$G$ そして $H$頂点の数は同じで、エッジを残してもそれは変わりません。そう$G$ そして $H$ 確かに同型です。
*私が知る限り、この記事で使用されている折れ線グラフの概念は、平行なエッジに対応する頂点が1つのエッジのみに接続されているという点で、ここで使用されているものとは異なります。