วันนี้มาอบรมการสร้างภาพกราฟิกด้วยโปรแแกรม Photoscape, การตัดต่อเสียงด้วย Wavepan พรุ่งนี้ยังมีอีก 1 โปรแกรม คือ Pro Show Gold เพื่อเป็นการศึกษาความรู้ใหม่ๆ เพิ่มความรู้ให้กับตัวเอง แต่ก็ยังมีเรื่องที่อยากรู้คือ การทำเว็บบล็อกก็เลยลองสมัครดู...ครั้งแรกคะ...การเรียนรู้ไม่เคยหยุดนิ่ง...ถ้าไม่เบื่อ...แต่ถ้าเบื่อเมื่อไรก็ทำอย่างอื่นไปก่อน...อยู่กับคอมมานานบางครั้งก็เบื่อและเหนื่อยด้วย..ขอให้กำลังใจตัวเองด้วยการอยู่กับครอบครัว

รูปแบบการเรียนรู้ในศตวรรษที่ 21 ที่เปลี่ยนแปลงจากการสอนไปเป็นการเรียนรู้และการเข้าถึงความรู้ได้เร็วมากกว่าที่จะจดจำเอง ทำให้เกิดการสร้างองค์ความรู้เกิดขึ้นได้อย่างรวดเร็วและต่อเนื่อง เกิดเป็นสังคมแห่งการเรียนรู้ ที่ไม่จำกัดเวลา สถานที่ ผู้เรียน และผู้สอน ทุกคนสามารถเข้าถึงองค์ความรู้ได้เท่าที่ต้องการ เกิดเป็น Knowledge Cloud ซึ่งเป็นแหล่งความรู้ในศตวรรษที่ 21 ซึ่งสามารถใช้คลาวด์คอมพิวติง (Cloud computing) ประยุกต์ใช้เพื่อการศึกษาและการจัดการเรียนรู้ โดยใช้ knowledge cloud ได้แก่ data cloud, Google doc, sky drive และ iCloud ของ apple เป็นต้น

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

1. กราฟ

กราฟเป็นแบบจำลองทางคณิตศาสตร์ ซึ่งใช้จำลองปัญหาบางปัญหาโดยเขียนแผนภาพที่ประกอบด้วยจุดและเส้น ปัจจุบันมีการนำทฤษฎีกราฟมาประยุกต์ใช้ในศาสตร์สาขาต่าง ๆ เช่น วิทยาศาสตร์ สังคมศึกษา เศรษฐศาสตร์ พันธุศาสตร์ วิศวกรรมศาสตร์ เป็นต้น

บทนิยาม กราฟ G ประกอบด้วยเซตจำนวน 2 เซต คือ

1. เซตที่ไม่เป็นเวตว่างของจุดยอด (vertex) แทนด้วยสัญลักษณ์ V(G)

2. เซตของเส้นเชื่อม (edge) ที่เชื่อมระหว่างจุดยอดแทนด้วยสัญลักษณ์ E(G)

2. ดีกรี

ดีกรีของจุดยอด

ได้

 จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v

ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 2

deg b = 1

deg c = 3

deg d = 4

ตัวอย่างที่ 2 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 5

deg b = 5

deg c = 5

deg d = 4

พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้น

จะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด

นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

ข้อสังเกต ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ

ตัวอย่างที่ 3 จงหาจำนวนเส้นเชื่อมของกราฟที่มีผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ 22

วิธีทำ สมมติว่า กราฟมีเส้นเชื่อม n เส้น

จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

ดังนั้น 22 = 2n

นั่นคือ n = 11

สรุปได้ว่า กราฟมีเส้นเชื่อม11 เส้น

ตัวอย่างที่ 4 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด 3 จุด ที่มีดีกรี 4 ส่วนจุดยอดที่เหลือมีดีกรี 3

วิธีทำ ให้ n เป็นจำนวนจุดยอดที่มีดีกรี 3

ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟ คือ (3)(4) + 3n

จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

ดังนั้น (3)(4) + 3

เพราะฉะนั้น n = 6

ดังนั้น จำนวนจุดยอดทั้งหมดของกราฟ คือ 3 + 6 = 9 จุด

วิธีทำ สมมติว่า มีดีกรีที่มีจุดยอด 4 จุด และดีกรีของจุดยอดเท่ากับ 1, 1, 2 และ 3

ดังนั้น ผลรวมของดีกรีของจุดยอดทุกจุด คือ 1 + 1 + 2 + 3 = 7

ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 1

ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว

ตัวอย่างที่ 5 จงพิจารณาว่าเป็นไปได้หรือไม่ว่า จะมีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3 ตามลำดับ

ตัวอย่างที่ 6 กำหนดกราฟ ดังรูป

จากรูปจะได้ว่า deg a = 2

deg b = 3

deg c = 0

deg d = 3

deg e = 2

ดังนั้น จุดยอด a, c และ e เป็นจุดยอดคู่

จุดยอด b และ d เป็นจุดยอดคี่

ทฤษฎีบท2 ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่

พิสูจน์ ให้ G เป็นกราฟ

ถ้า G ไม่มีจุดยอดคี่ นั่นคือ G มีจำนวนจุดยอดคี่เป็นศูนย์

จึงได้ว่าG มีจำนวนจุดยอดคี่เป็นจำนวนคู่

ต่อไปสมมติว่า กราฟ G มีจุดยอดคี่ k จุด คือ v1, v2, v3, …, vk

และมีจุดยอดคู่ n จุด คือ u1, u2, u3, …, un จากทฤษฎีบท 1

จะได้ว่า (deg v1 + deg v2 + … + deg vk) + (deg u1 + deg u2 + … + deg un) = 2q

เมื่อ q คือ จำนวนเส้นเชื่อมของ G

ดังนั้น deg v1 + deg v2 + … + deg vk = 2q - (deg u1 + deg u2 + … + deg un)

เนื่องจาก deg u1 + deg u2 + … + deg un ต่างก็เป็นจำนวนคู่

ดังนั้น 2q - (deg u1 + deg u2 + … + deg un) เป็นจำนวนคู่

นั่นคือ deg v1 + deg v2 + … + deg vk เป็นจำนวนคู่

แต่เนื่องจาก deg v1 + deg v2 + … + deg vk เป็นจำนวนคี่

เพราะฉะนั้น k จะต้องเป็นจำนวนคู่ จึงจะทำให้ deg v1 + deg v2 + … + deg vk

เป็นจำนวนคู่ สรุปได้ว่า กราฟ G มีจุดยอดคี่เป็นจำนวนคู่

จากตัวอย่างที่ 5 เราให้เหตุผลโดยอาศัยทฤษฎีบท 2 ดังนี้

สมมติว่า มีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3

จะได้ว่า กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท 2 สรุปได้ว่า ไม่มีกราฟที่มีสมบัติดังกล่าว

ตัวอย่างที่ 7 ถ้าในห้องประชุมแห่งหนึ่งมีผู้เข้าร่วมประชุมทั้งหมด 23 คน เป็นไปได้หรือไม่

ว่าผู้เข้าร่วมประชุมแต่ละคนจับมือทักทายผู้เข้าร่วมประชุมคนอื่นเพียง 7 คนเท่านั้น

วิธีทำ แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนผู้เข้าร่วมประชุม และเส้นเชื่อมแทน การจับมือทักทายของผู้เข้าร่วมประชุม

จะได้ว่า กราฟนี้มีจุดยอด 23 จุด และจุดยอดแต่ละจุดมีดีกรี 7

นั้นคือ กราฟมีจุดยอดคี่เป็นจำนวน 23 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 2

ดังนั้น เป็นไปไม่ได้ที่ผู้เข้าร่วมประชุมแต่ละคนจับมือกับคนอื่นเพียง 7 เท่านั้น

ที่มา : http://mathematics-pr.blogspot.com/p/blog-page_4945.html