สร้าง homeomorphic กราฟที่เล็กที่สุดให้กับกราฟที่กำหนดโดยการทำให้เรียบ

Question

คลาส homeomorphism $ \mathcal{H}(G) $ ของกราฟ $G$ คือชุดของคลาสไอโซมอร์ฟิซึมของกราฟที่มีโครงสร้างแบบ homeomorphic ถึง $G$. เป็นเรื่องธรรมดาที่จะถามว่า: มีตัวแทนที่ "เล็กที่สุด" ในคลาส homeomorphism หรือไม่? ถ้ามีจะหาได้อย่างไร? ขออภัยฉันไม่พบผลลัพธ์ที่เป็นประโยชน์สำหรับปัญหานี้หลังจากค้นหาโดย Google อย่างรวดเร็ว

อย่างไรก็ตามด้วยสัญชาตญาณฉันมีสมมติฐานดังต่อไปนี้:

homeomorphic กราฟที่เล็กที่สุดของกราฟได้มาจากการปรับให้เรียบทุกหู

ในโพสต์นี้ฉันพยายามร่างหลักฐาน แต่มีช่องว่างในการพิสูจน์ดังนั้นฉันจึงไม่รู้ว่าสมมติฐานของฉันถูกต้องหรือไม่ ฉันจะขอบคุณทุกคนที่ชี้ให้เห็นข้อผิดพลาดของฉันและเติมเต็มช่องว่าง

คำเตือน: นี่จะเป็นโพสต์ที่ยาว

ก่อนอื่นเรามาทำความเข้าใจคำศัพท์บางคำ คำว่า "หู" หมายถึงสิ่งที่แตกต่างกันในตำราทฤษฎีกราฟที่แตกต่างกัน ในโพสต์นี้เราใช้คำจำกัดความต่อไปนี้:

คำจำกัดความ 1

หูในกราฟคือ:

• วัฏจักรที่มีจุดยอดทั้งหมดยกเว้นหนึ่งจุด $2$, หรือ
• เส้นทางที่มีจุดยอดภายในทั้งหมดเป็นองศา $2$.

หูขนาดใหญ่ที่สุดคือหูที่ไม่ใช่ย่อหน้าที่เหมาะสมของหูที่ใหญ่กว่า หูสูงสุดคือหนึ่งในสิ่งต่อไปนี้:

• วงจรที่เป็นส่วนประกอบที่เชื่อมต่อทั้งหมดในตัวมันเอง
• วัฏจักรที่จุดยอดหนึ่งมีองศา $ \geq 3 $ในขณะที่จุดยอดอื่น ๆ ทั้งหมดมีระดับ $2$
• เส้นทางที่จุดยอดภายในทั้งหมดมีระดับ $2$ในขณะที่จุดปลายทั้งสองมีองศา $ \neq 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$ หมายถึงการแทนที่ด้วย self-loop $e$และจุดยอดขององศา $ \neq 2 $ บน $C$ กลายเป็นเหตุการณ์จุดสุดยอดเดียวบน $e$ (ถ้าจุดยอดทั้งหมดเปิด $C$ มีระดับ $2$เพียงเลือกจุดยอดใดก็ได้)

ในทางกลับกันถ้า $C$ เป็นเส้นทางจริงๆ $P$แล้วปรับให้เรียบ $P$ หมายถึงการแทนที่ด้วยขอบที่ไม่มีลูป $e$และจุดสิ้นสุดของ $P$ กลายเป็นจุดสิ้นสุดของ $e$.

การปรับกราฟให้เรียบหมายถึงการกำหนดลำดับของการปรับให้เรียบบนใบหู

ต่อไปเรามีผลลัพธ์คลาสสิกต่อไปนี้เกี่ยวกับโทโพโลยีของกราฟ:

ทฤษฎีบท 1

กราฟสองกราฟเป็น homeomorphic ก็ต่อเมื่อสามารถหาได้จากลำดับของการแบ่งย่อยและการดำเนินการที่ราบรื่นในอีกกราฟ

หลักฐาน:ดูโพสต์นี้

ทฤษฎีบท 2

ปล่อย $G$ และ $H$เป็นกราฟ homeomorphic สองกราฟ แล้ว$ |V(G)| = |V(H)| $ ถ้าและต่อเมื่อ $ |E(G)| = |E(H)| $.

ร่างของการพิสูจน์: การแบ่งย่อย (resp. smoothing) จะเพิ่มจำนวนจุดยอดและขอบด้วยจำนวนเดียวกันเสมอ$\square$

ในแง่ของทฤษฎีบท 2 เราสามารถกำหนดลำดับในคลาส homeomorphism ของกราฟได้:

คำจำกัดความ 4

ปล่อย $ \mathcal{H}(G) $ เป็นคลาส homeomorphism ของกราฟ $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$คือการสั่งซื้อล่วงหน้าทั้งหมดซึ่งหมายความว่าเป็นสกรรมกริยาและกราฟ homeomorphic ใด ๆ ก็สามารถเทียบเคียงกันได้ น่าเสียดายที่ไม่ใช่คำสั่งซื้อทั้งหมดเนื่องจาก$ 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)$ซึ่งแต่ละระดับความเท่าเทียมกันจะมีขอบของหูสูงสุดหนึ่งหู ด้วยประการฉะนี้$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$ เป็นกราฟที่ราบรื่น

ร่างหลักฐาน:

โดย Theorem 1, $H$ สามารถหาได้จากลำดับของการแบ่งย่อยและการดำเนินการที่ราบรื่นบน $G$. แต่ละขั้นตอนของการใช้งานสามารถเปลี่ยนหูสูงสุดข้างหนึ่งให้เป็นหูสูงสุดอีกอันที่มีความยาวต่างกันได้

ในทางกลับกันในกราฟที่ราบรื่นหูสูงสุดทั้งหมดมีความยาวสั้นที่สุดเท่าที่จะเป็นไปได้ (กล่าวคือ $1$) ดังนั้นลำดับของการแบ่งย่อยและการปรับให้เรียบไม่สามารถลดจำนวนจุดยอดได้อีก ด้วยประการฉะนี้$ |V(G)| \leq |V(H)| $ และความเท่าเทียมกันถือในกรณีที่ $H$ ราบรื่น $\square$

คำกล่าวอ้างต่อไปนี้เป็นไปตามสัญชาตญาณ แต่ฉันไม่รู้จะพิสูจน์ได้อย่างไร มันคือช่องว่างของการพิสูจน์ทั้งหมดของฉันอยู่

อ้างสิทธิ์ 0

ปล่อย $G$ และ $H$เป็นกราฟเรียบสองกราฟโดยไม่มีจุดยอดแยก ถ้าพวกมันเป็น homeomorphic แสดงว่าเป็นไอโซมอร์ฟิก

สุดท้ายสมมติว่ามีการอ้างสิทธิ์ข้างต้นเราสามารถพิสูจน์สมมติฐานหลักได้:

สมมติฐานหลัก

ถือว่าการอ้างสิทธิ์ 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$ราบรื่นเช่นกัน อ้างเป็นนัยว่า$H$ isomorphic ถึง $ \text{Smooth} (G) $. $\square$

คำถาม:

1. ข้อเรียกร้อง 0 ถูกต้องหรือไม่? จะพิสูจน์ได้อย่างไร?
2. แม้ว่า Claim 0 จะผิด แต่สมมติฐานหลักของฉันยังคงถูกต้องอยู่หรือไม่?
3. มีข้อผิดพลาดอื่น ๆ ในการพิสูจน์ของฉันหรือไม่?
4. มีคำศัพท์ที่ดีกว่าสำหรับกราฟที่มีความยาวสูงสุดทุกหู $1$นอกเหนือจาก "กราฟเรียบ"?

Answer 1

หลักฐานของคุณปรากฏว่าถูกต้องสำหรับฉัน ฉันไม่เห็นว่าทำไมคุณถึงคิดว่ากราฟไม่มีจุดยอดแยก - มันสร้างความแตกต่างได้ทุกที่หรือไม่? นอกจากนี้ "กราฟเรียบ" ดูเหมือนจะเป็นชื่อที่แปลกใหม่สำหรับกราฟที่ไม่มีจุดยอดของระดับสอง (อย่างแม่นยำยิ่งขึ้นจุดยอดเพียงจุดเดียวของระดับสองคือจุดยอดที่แยกจากกันโดยมีการวนซ้ำ)

ฉันจะให้หลักฐานการอ้างสิทธิ์ของคุณ เราอาจสันนิษฐานว่ากราฟที่เป็นปัญหาเชื่อมต่อกันและมีขอบอย่างน้อยหนึ่งด้าน ไปยังกราฟใด ๆ$G$เชื่อมโยงกราฟสีจุดยอด $Ear(G)$ ด้วยวิธีต่อไปนี้:

• จุดยอดของ $Ear(G)$ สอดคล้องกับหูในการสลายตัวที่เป็นเอกลักษณ์ของ $G$เข้าสู่หูสูงสุด มีสีฟ้าและแดงตามว่าหูเป็นทางเดินหรือวงรอบ
• จุดยอดสองจุดอยู่ติดกันหากหูที่ตรงกันมีจุดยอดทั่วไป ถ้าพวกเขามีจุดยอดสองจุดร่วมกันเราก็วาดสองขอบขนาน (สิ่งนี้จะเกิดขึ้นได้ก็ต่อเมื่อหูที่เกี่ยวข้องเป็นเส้นทางเท่านั้น)

มีข้อสังเกตสองประการที่ต้องทำซึ่งมีนัยมากหรือน้อยในการพิสูจน์ทฤษฎีบท 4 ของคุณ:

1. ถ้า $G$ และ $H$ เป็น homeomorphic แล้ว $Ear(G)$ และ $Ear(H)$เป็นไอโซมอร์ฟิสโดยที่ไอโซมอร์ฟิซึมจะรักษาสีจุดยอด สิ่งนี้มาจาก Theorem 1 หลังจากตรวจสอบว่าทั้งการปรับให้เรียบและการแบ่งส่วนย่อย$Ear(G)$.
2. ถ้า $G$ เรียบแล้ว (ไม่สนใจการระบายสี) $Ear(G)$เป็นเพียงกราฟเส้นของ$G$กำหนดไว้อย่างเหมาะสมสำหรับกราฟที่มีการวนซ้ำและหลายขอบ

ตามสะดวกทฤษฎีบทของวิทนีย์ระบุว่าถ้ากราฟเส้นของไอโซมอร์ฟิกสองกราฟที่เชื่อมต่อกันกราฟเส้นนั้นจะเป็นไอโซมอร์ฟิกยกเว้นว่ากราฟเป็นสามเหลี่ยม$K_3$ และกรงเล็บ $K_{1,3}$. สังเกตว่ารูปสามเหลี่ยมไม่เรียบ ในกรณีของกราฟที่มีการวนซ้ำและขอบขนานสถานการณ์มีความซับซ้อนมากขึ้น (แม้ว่าจะไม่มากตามบทความนี้ * ซึ่งฉันสามารถหาลิงค์ paywalled ได้อย่างสนุกสนานพอชื่อของ Whitney สะกดผิดในชื่อเรื่อง) แต่ในกรณีของเราการระบายสีจุดยอดและทฤษฎีบท 4 ให้ข้อมูลเพียงพอแก่เราในการสร้างกราฟดั้งเดิมขึ้นมาใหม่โดยเฉพาะ คุณสามารถแยกแยะสิ่งนี้ได้ด้วยตัวเอง แต่ฉันจะให้รายละเอียดเพื่อความสมบูรณ์

ดังนั้นสมมติว่า $G$ และ $H$ ราบรื่นและนั่น $Ear(G)$ และ $Ear(H)$คือ isomorphic ขั้นแรกเราจัดการกับลูป: สิ่งเหล่านี้สอดคล้องกับจุดยอดสีแดงของ$Ear(G)$ และ $Ear(H)$. ตามนั้นถ้าเราแสดงโดย$G'$ และ $H'$ กราฟที่ได้จากการลบลูปใน $G$ และ $H$แล้ว $Ear(G')$ และ $Ear(H')$ ได้มาจากการลบจุดยอดสีแดงจาก $Ear(G)$ และ $Ear(H)$; โดยเฉพาะอย่างยิ่งพวกมันเป็นไอโซมอร์ฟิก ตอนนี้ก็เพียงพอแล้วที่จะแสดงให้เห็นว่า$G'$ และ $H'$ เป็น isomorphic ตั้งแต่นั้นมาตำแหน่งของลูปจะถูกกำหนดโดยเฉพาะ $Ear(G)$: จุดยอดใน $G'$ มีลูปก็ต่อเมื่อมีขอบตกกระทบซึ่งอยู่ติดกับจุดยอดสีแดงใน $Ear(G)$, หรือถ้า $G'$ ประกอบด้วยจุดยอดเดียวนี้ (เนื่องจากเราสันนิษฐานว่ากราฟของเรามีขอบอย่างน้อยหนึ่งขอบ)

ดังนั้นเราอาจสันนิษฐานได้ว่า $G$ และ $H$ไม่มีลูป ตอนนี้เราต้องดูแลขอบขนาน ถ้าสองขอบขนานกัน$G$จากนั้นโดยการสร้างของเราจุดยอดที่สอดคล้องกันใน $Ear(G)$เชื่อมต่อกันด้วยขอบขนานสองด้าน โดยทั่วไปขอบขนานสองเส้นขึ้นไปใน$G$ สอดคล้องกับกลุ่มใน $Ear(G)$ซึ่งทุกขอบจะเพิ่มเป็นสองเท่า ทุกจุดยอดใน$Ear(G)$ มีอยู่ใน "กลุ่มคู่" ที่มีค่าสูงสุดที่ไม่ซ้ำกัน (อาจมีขนาด 1) และด้วยการทำสัญญากลุ่มเหล่านี้และแทนที่ขอบขนานที่สร้างขึ้นใหม่ด้วยเส้นเดี่ยวเราจะได้เส้นกราฟของกราฟพื้นฐาน $G$. เนื่องจากสิ่งนี้ทำงานย้อนกลับได้เช่นกัน (เช่นจากกราฟอย่างง่ายและ$Ear(G)$ เราสามารถกู้คืนได้ $G$) เราอาจสันนิษฐานได้ว่า $G$ และ $H$ เรียบง่าย

เราก็ทำตามทฤษฎีบทของวิทนีย์ใช่ไหม? ไม่เร็วนัก อาจเกิดขึ้นหลังจากออกจากลูปและขอบขนานจาก$G$ และ $H$เราจะเหลือสามเหลี่ยมและ $K_{1,3}$: ท้ายที่สุดแล้วสามเหลี่ยมที่มีขอบสองเท่าจะเรียบ แต่สิ่งนี้ถูกตัดออกโดย Theorem 4: ต้นฉบับ$G$ และ $H$มีจุดยอดจำนวนเท่ากันและการเว้นขอบจะไม่เปลี่ยนแปลง ดังนั้น$G$ และ $H$ isomorphic แน่นอน

^{* โปรดทราบว่าเท่าที่ฉันสามารถบอกได้แนวคิดของกราฟเส้นที่ใช้ในบทความนั้นแตกต่างจากที่ใช้ที่นี่ตรงที่จุดยอดที่ตรงกับขอบขนานยังคงเชื่อมต่อด้วยขอบเพียงด้านเดียว}