|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
ทฤษฎีกราฟเบื้องต้น
ช่วยหน่อยน้ะครับ พิสูจน์ไม่เป็นเลย นิยามก็เยอะมาก
1. ถ้า $G$ เป็นกราฟที่มี $13$ จุด และมี $3$ คอมโพเนนท์แล้วจงแสดงว่า $G$ จะมีอย่างน้อย $1$ คอมโพเนนท์ที่มีจุดอย่างน้อย $5$ จุด 2. ให้ $G$ เป็นซิมเปิลกราฟที่มีจำนวนจุดเป็นจำนวนคู่ และ $G$ มี $2$ คอมโพเนนท์ ซึ่งเป็นคอมพลีท จงแสดงว่าจำนวนเส้นที่น้อยที่สุดของ $G$ คือ $q=\frac{p^2-2p}{4} $ 3. ให้ $G_1\cong G_2$ จงพิสูจน์ว่า ถ้า $G_1$ เป็นคอนเนคเตดกราฟ แล้ว $G_2$ จะเป็นคอนเนคเตดกราฟ 4. ให้ $G$ เป็นซิลเปิลกราฟซึ่งมี $p$ จุด $(p\geqslant 2)$ และทุกๆจุด $v$ ของ $G$ จะมี $d(v)\geqslant \frac{p-1}{2} $ จงพิสูจน์ว่า $G$ เป็นคอนเนคเตดกราฟ
__________________
PURE MATH |
#2
|
|||
|
|||
ข้อแรก เราสมมุติ ว่า แต่ละคอมโพเนนท์มีจุดยอด อย่างมาก 4 จุด ซึ่ง กราฟ G จะมีจำนวนจุดยอดมากที่สุด 12 จุด เกิดข้อขัดแย้ง ดังนั้น จะมีหนึ่งคอมโพเนนท์ที่มีจุดยอดอย่างน้อย 5 จุด
|
#3
|
|||
|
|||
ข้อสาม
จากนิยาม isomorphic ของกราฟ จะมีฟังชัน 1-1 onto f ซึ่ง uv เส้นเชื่อมของ $G_1$ แล้ว f(u)f(v) เป็นเส้นเชื่อมของ $G_2$
ให้ a, b เป็นจุดยอดใด ๆ ใน กราฟ $G_1$ เนื่องจาก $G_1$ เป็น connected graph แล้ว จะมีแนวเดิน $a{a_1}...b$ ซึ่ง f(a) และ f(b) เป็นจุดยอด ในกราฟ $G_2$ แล้วมีแนวเดิน $f(a){f(a_{1})...f(b)}$ ดังนั้น $G_2$ เป็น connected graph |
#4
|
|||
|
|||
ข้อสอง
ให้ $G$ เป็น simple graph โดยที่ จำนวนจุดยอดของกราฟ $G$ คือ $p$ โดยที่ $p$ เป็นจำนนวนคู่ และ $G_1$ และ $G_2$ เป็น component ของกราฟ $G$
ให้ $G_1$ และ $G_2$ เป็น complete graph ต้องการจำนวนเส้นเชื่อมที่น้อยที่สุด ดังนั้น จำนวนจุดยอดของ กราฟ $G_1$ และกราฟ $G_2$ ต้องเท่ากัน และมีค่าเท่ากับ $\frac{p}{2}$ (จำนวนเส้นเชื่อมของ complete graph $K_{n}$=$\frac{n(n-1)}{2}$ ) ดังนั้น จำนวนเส้นเชื่อมของกราฟ $G$ = $2\frac{\frac{p}{2}(\frac{p}{2}-1)}{2}=\frac{p^{2}-2p}{4}$ |
#5
|
|||
|
|||
ขอบคุณ มากๆเลย ครับ ผม
__________________
PURE MATH |
#6
|
|||
|
|||
อ้างอิง:
ถ้าใช่ ใช้ Contradiction ครับ สมมติ G not connected แสดงว่า G มี at least 2 components Take u ,v จาก 2 components ต่างกัน แน่นอนว่า u,v ไม่มี path เชื่อมถึงกัน ....(*) Define N(x) แทนเซตของจุดที่ มีเส้นเชื่อมกับ x ดังนั้น $ | N(u) \cup N(v) | \leq p-2 $ (By (*)) By inclusion-exclusion principle , $ | N(u) \cup N(v) | = |N(u)| +| N(v)| - | N(u) \cap N(v)| \geq \frac{p-1}{2} + \frac{p-1}{2} - | N(u) \cap N(v)| $ ดังนั้น $| N(u) \cap N(v)| \geq 1 $ CONTRADICTION WITH (*)
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว |
#7
|
|||
|
|||
ข้อสี่
ให้ กราฟ $G$ เป็นกราฟทีมีจุดยอด $p$ จุด
สมมุติ $d(v)\geq \frac{p-1}{2}$ สำหรับทุกจุดยอด $v$ ในกราฟ $G$ ให้ $a$ และ $b$ เป็นจุดยอดในกราฟ $G$ แล้ว $d(a)\geq \frac{p-1}{2}$ และ $d(b)\geq \frac{p-1}{2}$ ซึ่ง จุดยอด $a$ และจุดยอด $b$ จะประชิดกับจุดยอดอื่น อย่างน้อย $\frac{p-1}{2}$ นั่นคือ จะมีจุดยอด $c$ ในกราฟ $G$ ซึ่งประชิดกับจุดยอด $a$ และจุดยอด $b$ จะมีแนวเดิน $acb$ ดังนั้น กราฟ $G$ เป็น connected graph |
#8
|
|||
|
|||
รบกวนอีก น้ะครับ
1. ทุกๆ $u-v$ เทรล จะบรรจุ $u-v$ พาท. 2. ให้ $G$ เป็น $(p,q)$ กราฟซึ่งมีดีกรีของจุดเป็น $k$ หรือ $k+1$ ถ้า $G$ มี $p_k$ จุดซึ่งมีดีกรี $k$ และมี $p_{k+1}$ จุด ซึ่งมีดีกรี $k+1$ จงแสดงว่า $p_k=(k+1)p-2q$.
__________________
PURE MATH |
#9
|
|||
|
|||
3. จงแสดงว่าถ้า $G$ เป็นคอนเนคเตดกราฟซึ่งดีกรีน้อยที่สุดของจุดเป็น $k$ แล้ว $\lambda (G)\leqslant k$
จงสร้างกราฟที่ $K(G)<\lambda (G)<k$
__________________
PURE MATH |
#10
|
|||
|
|||
แสดงว่า u-v tail จะบรรจุ u-v path
เราจะใช้ อุปนัยในการพิสูจน์
ให้ k เป็นจำนวนเส้นเชื่อมของ u-v tail ขั้นฐาน k=0 จะได้ว่า u คือ path ที่เราต้องการ ขั้นอุปนัย สมมติว่า ทุก u-v tail ที่มีความยาวไม่เกิน k จะบรรจุ u-v path กรณี u-v tail เป็น path เราได้ตามต้องการ กรณี u-v tail ไม่เป็น path ดังนั้นจะมีจุดยอด w ปรากฎซ้ำในลำดับของ u-v tail เราจะเขียน u-v tail ในรูปของ $us_{1}ws_{2}ws_{3}v$ โดย $s_1, s_2$ และ $s_3$ เป็นลำดับของจุดยอดที่เหลือใน tail นั้น ถ้าเราลบเส้นเชื่อมและจุดยอด $s_2$ ที่อยู่ระหว่าง w ในลำดับของ tail จะได้ว่า tail นั้นจะสั้นกว่าเดิม คือ $us_{1}ws_{3}v$ ฉะนั้นโดยอุปนัยเชิงคณิตศาสตร์ จะมี u-v path ที่ต้องการจากแนวเดินใหม่นี้ |
#11
|
|||
|
|||
ผมมองไม่ออกเลยครับ วิธีเขียนพิสูจน์ ทบ กราฟ นี่ ไงก็ขอบคุณมากนะครับ ที่ช่วย คิด ทุกท่านเลย
__________________
PURE MATH |
|
|