ทฤษฎีกราฟเบื้องต้น

[PURE MATH]

ช่วยหน่อยน้ะครับ พิสูจน์ไม่เป็นเลย นิยามก็เยอะมาก

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$ เป็นคอนเนคเตดกราฟ

[DarkinSulT]

ข้อแรก เราสมมุติ ว่า แต่ละคอมโพเนนท์มีจุดยอด อย่างมาก 4 จุด ซึ่ง กราฟ G จะมีจำนวนจุดยอดมากที่สุด 12 จุด เกิดข้อขัดแย้ง ดังนั้น จะมีหนึ่งคอมโพเนนท์ที่มีจุดยอดอย่างน้อย 5 จุด

[DarkinSulT]

จากนิยาม 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

[DarkinSulT]

ให้ $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}$

[PURE MATH]

ขอบคุณ มากๆเลย ครับ ผม

[passer-by]

ข้อความเดิมเขียนโดยคุณ PURE MATH

4. ให้ $G$ เป็นซิลเปิลกราฟซึ่งมี $p$ จุด $(p\geqslant 2)$ และทุกๆจุด $v$ ของ $G$ จะมี $d(v)\geqslant \frac{p-1}{2} $ จงพิสูจน์ว่า $G$ เป็นคอนเนคเตดกราฟ

ข้อ 4 จะสื่อว่า ทุกจุดของ G มีดีกรี $ \geq \frac{p-1}{2}$ หรือเปล่าครับ

ถ้าใช่ ใช้ 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 (*)

[DarkinSulT]

ให้ กราฟ $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

[PURE MATH]

รบกวนอีก น้ะครับ
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]

3. จงแสดงว่าถ้า $G$ เป็นคอนเนคเตดกราฟซึ่งดีกรีน้อยที่สุดของจุดเป็น $k$ แล้ว $\lambda (G)\leqslant k$
จงสร้างกราฟที่ $K(G)<\lambda (G)<k$

[DarkinSulT]

เราจะใช้ อุปนัยในการพิสูจน์
ให้ 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 ที่ต้องการจากแนวเดินใหม่นี้

[PURE MATH]

ผมมองไม่ออกเลยครับ วิธีเขียนพิสูจน์ ทบ กราฟ นี่ ไงก็ขอบคุณมากนะครับ ที่ช่วย คิด ทุกท่านเลย