Buat grafik homeomorfik terkecil ke grafik tertentu dengan menghaluskan

Question

Kelas homeomorfisme $ \mathcal{H}(G) $ dari grafik $G$ adalah himpunan kelas isomorfisme dari grafik yang secara topologis bersifat homeomorfik $G$. Wajar untuk bertanya: Apakah ada perwakilan "terkecil" dalam kelas homeomorfisme? Jika ya, bagaimana cara menemukannya? Sayangnya, saya tidak menemukan hasil yang berguna untuk masalah ini setelah pencarian cepat di Google.

Namun demikian, dibimbing oleh intuisi, saya memiliki hipotesis berikut:

Grafik terkecil homeomorfik ke grafik diperoleh dengan menghaluskan setiap telinga maksimal.

Dalam posting ini saya mencoba membuat sketsa bukti, tetapi ada celah dalam bukti, jadi saya tidak tahu apakah hipotesis saya benar. Saya akan menghargai siapa pun karena menunjukkan kesalahan saya dan mengisi kekosongan.

Peringatan: ini akan menjadi posting yang panjang

Pertama, mari kita perjelas beberapa terminologi. Istilah "telinga" memiliki arti yang berbeda dalam buku teks teori grafik yang berbeda. Dalam posting ini, kami mengadopsi definisi berikut:

Definisi 1

Telinga dalam grafik adalah:

• sebuah siklus yang semua kecuali satu simpul memiliki derajat $2$, atau
• sebuah jalan yang semua simpul internalnya memiliki derajat $2$.

Telinga maksimal adalah telinga yang bukan merupakan subgrafik yang tepat dari telinga yang lebih besar. Sama halnya, telinga maksimal adalah salah satu dari yang berikut:

• sebuah siklus yang merupakan keseluruhan komponen yang terhubung dengan sendirinya
• sebuah siklus di mana tepat satu simpul adalah derajat $ \geq 3 $, sedangkan semua simpul lainnya adalah derajat $2$
• jalur di mana semua simpul internal memiliki derajat $2$, sedangkan kedua simpul ujung memiliki derajat $ \neq 2 $

Dua operasi umum yang mempertahankan topologi pada grafik adalah pengelompokan dan penghalusan:

Definisi 2

Membagi tepi berarti menggantinya dengan telinga. Lebih tepatnya, biarkan$e = uv$ menjadi tepi.

Jika $u = v$, lalu membagi self-loop $e$ berarti menggantinya dengan sebuah siklus $C$, dan $u = v$ menjadi titik puncak $C$, yang mungkin memiliki gelar atau tidak $2$, tergantung cuaca $e$ terisolasi.

Di sisi lain, jika $u \neq v$, lalu membagi $e$ berarti menggantinya dengan jalan $P$, dan $u, v$ menjadi simpul akhir dari $P$.

Membagi grafik berarti membentuk urutan pengelompokan pada tepi.

Definisi 3

Menghaluskan telinga berarti menggantinya dengan satu sisi. Lebih tepatnya, biarkan$C$ menjadi telinga.

Jika $C$ adalah sebuah siklus, lalu pemulusan $C$ berarti menggantinya dengan putaran otomatis $e$, dan puncak derajat $ \neq 2 $ di $C$ menjadi satu-satunya kejadian simpul pada $e$ (jika semua simpul aktif $C$ adalah derajat $2$, cukup pilih titik mana saja).

Di sisi lain, Jika $C$ sebenarnya adalah sebuah jalan $P$, lalu haluskan $P$ berarti menggantinya dengan tepi tanpa lingkaran $e$, dan simpul akhir $P$ menjadi simpul akhir dari $e$.

Menghaluskan grafik berarti membentuk urutan pemulusan di telinga.

Selanjutnya, kami memiliki hasil klasik berikut pada topologi grafik:

Teorema 1

Dua grafik bersifat homeomorfik jika dan hanya jika salah satunya dapat diperoleh dari urutan operasi pengelompokan dan pemulusan pada yang lain.

Bukti: Lihat posting ini .

Teorema 2

Membiarkan $G$ dan $H$menjadi dua grafik homeomorfik. Kemudian$ |V(G)| = |V(H)| $ jika dan hanya jika $ |E(G)| = |E(H)| $.

Sketsa bukti: Pengelompokan (resp. Smoothing) selalu meningkatkan (resp. Mengurangi) jumlah simpul dan tepi dengan angka yang sama.$\square$

Berdasarkan Teorema 2, kita dapat mendefinisikan pengurutan pada kelas homeomorfisme dari sebuah grafik:

Definisi 4

Membiarkan $ \mathcal{H}(G) $ menjadi kelas homeomorfisme dari sebuah grafik $G$. Tentukan urutannya$\preceq$ di $ \mathcal{H}(G) $ oleh: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ untuk apapun $ G_1, G_2 \in \mathcal{H}(G) $.

Jika $ G_1 \preceq G_2 $ dan $ G_2 \preceq G_1 $, lalu kami tunjukkan $ G_1 \sim G_2 $.

Pemesanan $\preceq$adalah preorder total, artinya transitif dan dua grafik homeomorfik dapat dibandingkan. Sayangnya itu bukan pesanan total, karena$ G_1 \sim G_2 $ tidak menyiratkan $ G_1, G_2 $ bersifat isomorfik, bahkan melalui Teorema 2 menyiratkan $ |E(G_1)| = |E(G_2)| $.

Teorema 3

Grafik apa pun tanpa simpul terisolasi dapat didekomposisi secara unik menjadi penyatuan ujung-ujung telinga maksimal.

Sketsa bukti:

Membiarkan $G$menjadi grafik tanpa simpul terisolasi. Tentukan hubungannya$R$ di $E(G)$ oleh: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ untuk apapun $ e, f \in E(G) $.

Kemudian $R$ adalah hubungan kesetaraan pada $E(G)$, di mana setiap kelas ekivalen berisi tepian dari tepat satu telinga maksimal. Jadi,$R$ menginduksi dekomposisi $G$menjadi penyatuan ujung-ujung telinga maksimal. Sebaliknya, dekomposisi semacam itu harus dipicu oleh$R$, jadi dekomposisinya unik. $\square$

Berdasarkan dekomposisi di atas, kita dapat mendefinisikan yang berikut ini:

Definisi 5

Grafik tanpa simpul terisolasi disebut mulus jika setiap telinga maksimal memiliki panjang $1$. Untuk grafik$G$ tanpa simpul terisolasi, grafik halus diperoleh dari penghalusan setiap telinga maksimal masuk $G$ dilambangkan sebagai $ \text{Smooth} (G) $.

Istilah "grafik halus" tidak standar, tetapi saya tidak dapat menemukan istilah yang ada untuk grafik semacam itu, jadi saya membuatnya sendiri.

Teorema 4

Membiarkan $G$ menjadi grafik halus tanpa simpul terisolasi dan $ H \in \mathcal{H}(G) $, kemudian $ G \preceq H $. Bahkan,$ G \sim H $ jika dan hanya jika $H$ adalah grafik yang halus.

Sketsa bukti:

Dengan Teorema 1, $H$ dapat diperoleh dari urutan operasi pengelompokan dan pemulusan pada $G$. Setiap langkah operasi hanya dapat mengubah satu telinga maksimal ke telinga maksimal lainnya dengan panjang yang mungkin berbeda.

Sebaliknya, dalam grafik yang mulus semua telinga maksimal sudah memiliki panjang yang sesingkat mungkin (yaitu, $1$), jadi setiap urutan pengelompokan dan penghalusan tidak akan pernah dapat menurunkan jumlah simpul lebih jauh. Jadi,$ |V(G)| \leq |V(H)| $ dan kesetaraan berlaku jika dan hanya jika $H$ halus. $\square$

Klaim berikut ini berdasarkan intuisi, tetapi saya tidak tahu bagaimana membuktikannya. Di sinilah letak celah dari seluruh bukti saya.

Klaim 0

Membiarkan $G$ dan $H$menjadi dua grafik halus tanpa simpul terisolasi. Jika mereka homeomorfik, maka mereka isomorfik.

Akhirnya, dengan asumsi klaim di atas, kita dapat membuktikan hipotesis utama:

Hipotesis Utama

Asumsikan Klaim 0 benar dan biarkan $G$menjadi grafik tanpa simpul terisolasi. Kemudian$ \text{Smooth} (G) $ adalah grafik terkecil yang unik di $ \mathcal{H} (G) $ sehubungan dengan pemesanan $ \preceq $.

Bukti:

Fakta bahwa $ \text{Smooth} (G) \preceq H $ untuk semua $ H \in \mathcal{H} (G) $ mengikuti Teorema 4.

Untuk membuktikan keunikan, mari $ H \in \mathcal{H} (G) $ menjadi seperti itu $ \text{Smooth} (G) \sim H $. Sejak$ \text{Smooth} (G) $ halus dan $ H \in \mathcal{H} (\text{Smooth} (G)) $, dengan Teorema 4, $H$mulus juga. Klaim 0 berarti$H$ isomorfik untuk $ \text{Smooth} (G) $. $\square$

Pertanyaan:

1. Apakah Klaim 0 benar? Bagaimana cara membuktikannya?
2. Meskipun Klaim 0 salah, apakah hipotesis utama saya masih benar?
3. Apakah ada kesalahan lain dalam pembuktian saya?
4. Apakah ada istilah yang lebih baik untuk grafik yang setiap telinga maksimalnya memiliki panjang $1$, selain "grafik halus"?

Answer 1

Bukti Anda tampaknya benar bagi saya. Saya tidak mengerti mengapa Anda berasumsi bahwa grafik tidak memiliki simpul yang terisolasi - apakah itu membuat perbedaan di mana saja? Juga, "grafik halus" tampaknya merupakan nama yang bagus untuk grafik tanpa simpul berderajat dua. (Lebih tepatnya, satu-satunya simpul dengan derajat dua adalah simpul yang terisolasi dengan sebuah simpul.)

Saya akan memberikan bukti klaim Anda. Kami dapat berasumsi bahwa grafik tersebut terhubung dan memiliki setidaknya satu sisi. Untuk grafik apa pun$G$, kaitkan grafik berwarna simpul $Ear(G)$ dengan cara berikut:

• Simpul dari $Ear(G)$ sesuai dengan telinga dalam dekomposisi unik dari $G$ke telinga maksimal. Mereka diwarnai biru dan merah menurut apakah telinganya merupakan jalan setapak atau siklus.
• Dua simpul bersebelahan jika telinga yang sesuai memiliki simpul yang sama; jika mereka memiliki dua simpul yang sama, maka kita menggambar dua sisi sejajar. (Ini hanya dapat terjadi jika telinga yang sesuai adalah jalur.)

Ada dua pengamatan yang harus dilakukan yang kurang lebih tersirat dalam bukti Teorema 4 Anda:

1. Jika $G$ dan $H$ bersifat homeomorfik $Ear(G)$ dan $Ear(H)$bersifat isomorfik, dengan isomorfisma yang mempertahankan warna puncak. Ini mengikuti Teorema 1 setelah memeriksa bahwa baik pemulusan dan pengelompokan dipertahankan$Ear(G)$.
2. Jika $G$ halus, lalu (tanpa memperhatikan pewarnaan) $Ear(G)$hanyalah grafik garis dari$G$, didefinisikan dengan tepat untuk grafik dengan loop dan banyak sisi.

Tepatnya, teorema Whitney menyatakan bahwa jika grafik garis dari dua grafik sederhana yang terhubung isomorfik, maka grafik itu sendiri adalah isomorfik, kecuali jika grafik tersebut adalah segitiga$K_3$ dan cakar $K_{1,3}$. Perhatikan bahwa segitiga tidak mulus. Dalam kasus grafik dengan loop dan tepi paralel, situasinya lebih rumit (meskipun tidak terlalu parah, menurut artikel ini * yang saya hanya dapat menemukan tautan paywall; cukup lucu, nama Whitney salah eja dalam judul) , tetapi dalam kasus kami pewarnaan-puncak dan Teorema 4 memberi kami informasi yang cukup untuk merekonstruksi grafik asli secara unik. Anda mungkin bisa menyelesaikannya sendiri, tetapi saya akan memberikan detailnya untuk kelengkapan.

Jadi anggaplah begitu $G$ dan $H$ halus dan itu $Ear(G)$ dan $Ear(H)$bersifat isomorfik. Pertama, kita berurusan dengan loop: ini sama persis dengan simpul merah dari$Ear(G)$ dan $Ear(H)$. Itu mengikuti jika kita dilambangkan dengan$G'$ dan $H'$ grafik yang diperoleh dengan menghapus loop di $G$ dan $H$, kemudian $Ear(G')$ dan $Ear(H')$ diperoleh dengan menghapus simpul merah dari $Ear(G)$ dan $Ear(H)$; khususnya, mereka isomorfik. Sekarang cukup untuk menunjukkan itu$G'$ dan $H'$ bersifat isomorfik, sejak saat itu posisi loop ditentukan secara unik oleh $Ear(G)$: titik di $G'$ memiliki loop jika dan hanya jika ada sisi bersisian dengannya yang berdekatan dengan simpul merah di $Ear(G)$, atau jika $G'$ terdiri dari titik tunggal ini (karena kami mengasumsikan bahwa grafik kami memiliki setidaknya satu sisi).

Jadi, kita dapat berasumsi demikian $G$ dan $H$tidak mengandung loop. Sekarang kita hanya perlu merawat tepi paralel. Jika dua sisi sejajar$G$, kemudian dengan konstruksi kami simpul yang sesuai di $Ear(G)$dihubungkan oleh dua tepi paralel. Secara lebih umum, dua atau lebih tepi paralel masuk$G$ sesuai dengan klik di $Ear(G)$di mana setiap sisi digandakan. Setiap simpul di$Ear(G)$ terkandung dalam maksimal unik seperti "klik ganda" (berpotensi berukuran satu), dan dengan mengkontraksikan klik ini dan mengganti tepi paralel yang baru dibentuk menjadi satu, kami mendapatkan grafik garis dari grafik sederhana yang mendasari $G$. Karena ini bekerja mundur juga (yaitu dari grafik sederhana dan$Ear(G)$ kita bisa pulih $G$), kami dapat berasumsi bahwa $G$ dan $H$ sederhana.

Jadi kita sudah selesai dengan teorema Whitney, bukan? Tidak terlalu cepat. Itu bisa terjadi setelah meninggalkan loop dan tepi paralel dari$G$ dan $H$, kita ditinggalkan dengan segitiga dan $K_{1,3}$: bagaimanapun, segitiga dengan tepi berlipat ganda itu mulus. Tetapi ini dikesampingkan oleh Teorema 4: aslinya$G$ dan $H$memiliki jumlah simpul yang sama, dan meninggalkan sisi tidak mengubah itu. Begitu$G$ dan $H$ memang isomorfik.

^{* Perhatikan bahwa, sejauh yang saya tahu, pengertian grafik garis yang digunakan dalam artikel ini berbeda dengan yang digunakan di sini, di mana simpul-simpul yang berhubungan dengan tepi-tepi sejajar masih terhubung hanya dengan satu sisi.}