![]() |
|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ค้นหา | ข้อความวันนี้ | ทำเครื่องหมายอ่านทุกห้องแล้ว |
![]() ![]() |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
![]() โจทย์ให้พิสูจน์ว่า 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) $ ก็หยุดแค่นั้น ใครมีน้ำใจแนะนำให้ จะเป็นพระคุณอย่างสูง
__________________
$ \rho\iota\gamma$o$\rho \ \iota\sigma \ \omega$o$\rho\kappa\iota\nu\gamma \ \eta\alpha\rho\delta $ |
#2
|
|||
|
|||
![]() ลองใช้ทฤษฎีที่แสดงความสัมพันธ์ของ component ของกราฟ กับจำนวนจุดและเส้น ประกอบกับ ลบเส้นใน cycle ออกไป 1 เส้น น่าจะช่วยได้นะครับ
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว |
#3
|
||||
|
||||
![]() ขอบคุณคับ
![]() ปกติถ้าทำเองไม่ได้จะรู้สึกไม่สบายใจคับ ![]()
__________________
$ \rho\iota\gamma$o$\rho \ \iota\sigma \ \omega$o$\rho\kappa\iota\nu\gamma \ \eta\alpha\rho\delta $ |
#4
|
|||
|
|||
![]() I have a proof using Algebraic Topology but it is very very very hard to understand (at least you have to know Homology Theory
![]() ![]() 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. ![]()
__________________
site:mathcenter.net คำค้น |
#5
|
||||
|
||||
![]() ขอบคุณทั้งสองท่านคับ ทำได้แล้วคับ หุหุ
__________________
$ \rho\iota\gamma$o$\rho \ \iota\sigma \ \omega$o$\rho\kappa\iota\nu\gamma \ \eta\alpha\rho\delta $ |
#6
|
|||
|
|||
![]() ประมาณนี้รึเปล่าครับ
ให้ $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
__________________
จงรักเพื่อนบ้านเหมือนรักตนเอง |
#7
|
|||
|
|||
![]() นาน ๆ ทีจะมีกระทู้ทฤษฎีกราฟ ขอถามต่อแล้วกันนะครับ
จงพิสูจน์ว่า กราฟ $G$ เป็นต้นไม้ ก็ต่อเมื่อ ทุกจุดยอด 2 จุดที่แตกต่างกันของ $G$ จะเชื่อมโยงกันโดยวิถีเพียงวิถีเดียวเท่านั้น
__________________
จงรักเพื่อนบ้านเหมือนรักตนเอง |
#8
|
|||
|
|||
![]() จงพิสูจน์ว่า กราฟ 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 (ภาษาอาจไม่สวยลองไปเรียงใหม่ดูละกันคับ ไม่ค่อยถนัดภาษาไทย) ![]() |
#9
|
|||
|
|||
![]() สมัยเด็กเริ่มศึกษาผมชอบพิสูจน์โดยการพิสูจน์หาข้อขัดแย้ง ต่อมาตอนนี้คิดว่าเรากำหนดข้อคิดเห็นผิดหรือไม่ครอบคุม ความขัดแย้งย่อมเกิดขึ้นแน่
จึงขอเตือนทุกท่าน อย่าเชื่อตามตำราเสมอไป หนึ่งเหตุการณ์จริงมีเหตุผลนานาประกอบ เวลาใช้มักผิดพลาดเนื่องจากการสมมติที่ละเลยกฏธรรมชาติ |
#10
|
|||
|
|||
![]() อธิบายเพิ่ม เสือกับคน เกิดโดยธรรมชาติเหมือนกัน เหมือนเป็นกฏ แต่หากพิจารณาทุกแง่ ย่อมมีกฏที่ต่างกัน จริงไหม
ดังนั้นควรจะแน่ใจว่าใช้กับอะไร จึงไม่หลงทางครับ |
![]() ![]() |
![]() |
||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
Theory of Equations | kanji | พีชคณิต | 24 | 18 กุมภาพันธ์ 2008 21:39 |
spectrum of graph | rada | คณิตศาสตร์อุดมศึกษา | 2 | 19 พฤศจิกายน 2006 14:53 |
รบกวนไขข้อข้องใจหน่อยครับ ~ graph theory | prachya | ปัญหาคณิตศาสตร์ ม.ปลาย | 1 | 18 พฤษภาคม 2006 22:48 |
โจทย์graphครับ | A1 | ปัญหาคณิตศาสตร์ ม.ปลาย | 2 | 09 สิงหาคม 2005 22:14 |
เรื่องเกี่ยวกับ Graph และ Calculus | Adapt | ปัญหาคณิตศาสตร์ทั่วไป | 3 | 26 พฤษภาคม 2002 21:33 |
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
|