สุดปัญญาแล้วครับ Graph Theory

[rigor]

โจทย์ให้พิสูจน์ว่า connected graph $G$ ที่มีจำนวนจุดยอด $\nu (G) $ และจำนวนเส้นเชื่อม $\epsilon(G) = \nu (G) - 1$ เป็น acyclic graph

ผมเริ่มต้นให้ connected graph $G$ มี $\epsilon(G) = \nu (G) - 1$ และพิสูจน์โดยความขัดแย้ง สมมติให้ $G$ เป็น cyclic ดังนั้นมี cycle $C$ ใน $G$ และ
\[ \epsilon (G) \geq \epsilon (C) \]
\[ \nu (G) \geq \nu (C) \]
พยายามจะทำให้เกิดความขัดแย้งครับ คิดวนไปวนมาสองวันแล้วยังแกะไม่ออกเลย

ผมลองสมมติจุดยอดสองจุดใดบน cycle $C$ ให้ชื่อ $u, v$ แล้วได้ว่ามี $(u,v)$-path $P$ และ $(u,v)$-path $Q$ ซึ่ง $P\not = Q$ ทำไปทำมาได้แค่ว่า $\epsilon (C) = \nu (C) $ ก็หยุดแค่นั้น

ใครมีน้ำใจแนะนำให้ จะเป็นพระคุณอย่างสูง

[passer-by]

ลองใช้ทฤษฎีที่แสดงความสัมพันธ์ของ component ของกราฟ กับจำนวนจุดและเส้น ประกอบกับ ลบเส้นใน cycle ออกไป 1 เส้น น่าจะช่วยได้นะครับ

[rigor]

ขอบคุณคับ จะลองดูคับ

ปกติถ้าทำเองไม่ได้จะรู้สึกไม่สบายใจคับ

[nooonuii]

I have a proof using Algebraic Topology but it is very very very hard to understand (at least you have to know Homology Theory ) and I think everyone here don't want to see it . Anyway, I will show you the power of this subject.

Note that a graph is a CW - complex of dimension 1. Thus $\chi (G)$ ,the Euler characteristic of G, is the difference of the number of vertices of G and the number of edges of G which is 1 from our assumtion. Since G is a connected graph, we have
$H_0 (G) = Z$ and hence rank$ H_0 (G) = 1 = \chi (G).$
But $\chi (G) = $rank$ H_0 (G) - $rank$ H_1 (G) + 0 - 0 + ...$, so rank $H_1 (G) = 0.$
Since $H_1 (G)$ is a free abelian group, we have that $H_1 (G)=0.$
Therefore, $H_0 (G) = Z$ and $H_i (G) = 0$ for any $i > 0$. This means that G is acyclic.

[rigor]

ขอบคุณทั้งสองท่านคับ ทำได้แล้วคับ หุหุ

[st_alongkorn]

ประมาณนี้รึเปล่าครับ

ให้ $G$ เป็น connected graph ที่มีจุดยอดจำนวน $n$ จุด และเส้นเชื่อมจำนวน $n - 1$ เส้น
สมมติในทางตรงข้ามว่า $G$ มี cycle $C$ (ไม่เป็น acyclic graph) และ $e$ เป็นเส้นเชื่อมของ $C$
ดังนั้น $G - e$ เป็น connected graph ที่มีจุดยอดจำนวน $n$ จุด และเส้นเชื่อมจำนวน $n - 2$ เส้น
ซึ่งเป็นไปไม่ได้ที่ connected graph จะมีจำนวนเส้นเชื่อมเพียง $n - 2$ ดังนั้น $G$ เป็น acyclic graph

[st_alongkorn]

นาน ๆ ทีจะมีกระทู้ทฤษฎีกราฟ ขอถามต่อแล้วกันนะครับ

จงพิสูจน์ว่า กราฟ $G$ เป็นต้นไม้ ก็ต่อเมื่อ ทุกจุดยอด 2 จุดที่แตกต่างกันของ $G$ จะเชื่อมโยงกันโดยวิถีเพียงวิถีเดียวเท่านั้น

[ไร้สมรรถภาพ]

จงพิสูจน์ว่า กราฟ G เป็นต้นไม้ ก็ต่อเมื่อ ทุกจุดยอด 2 จุดที่แตกต่างกันของ G จะเชื่อมโยงกันโดยวิถีเพียงวิถีเดียวเท่านั้น
ข้อนี้ พิสูจน์ได้หลายแบบ
\rightarrow ขาไป ขอพิสูจน์โดยใช้ contradiction แล้วกันนะคับ
สมมติให้ G เป็น tree
ให้ u, v เป็นจุดใดๆใน G และมีวิถีอย่างน้อย 2 วิถี ที่แตกต่างกัน จาก u ไป v
นั่นคือจะวีวัฏจักรภายใน G ซึ่งขัดกับนิยามของ Tree
ดังนั้น G จะเชื่อมโยงกันโดยวิถีเพียงวิถีเดียวเท่านั้น
\leftarrow ขากลับ ใช้วิธีพิสูจน์โดยตรง
ให้ u, v เป็นจุดใดๆใน G และ มีวิถีจาก u ไป v เพียงวิถีเดียวเท่านั้น
จะได้ว่า G ไม่มีวัฏจักร และ connected
ดังนั้น G เป็น tree
(ภาษาอาจไม่สวยลองไปเรียงใหม่ดูละกันคับ ไม่ค่อยถนัดภาษาไทย)

[kongp]

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

[kongp]

อธิบายเพิ่ม เสือกับคน เกิดโดยธรรมชาติเหมือนกัน เหมือนเป็นกฏ แต่หากพิจารณาทุกแง่ ย่อมมีกฏที่ต่างกัน จริงไหม
ดังนั้นควรจะแน่ใจว่าใช้กับอะไร จึงไม่หลงทางครับ