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

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

แอนนิโมมิเตอร์แบบเส้นลวดความร้อน (hot-wire anemometer) เป็นอุปกรณ์ใช้วัดการไหล ที่นิยมใช้วัดความเร็วลมหรือวัดการไหลของของไหลที่อยู่ในสถานะก๊าซ โครงสร้างของแอนนิโมมิเตอร์แบบเส้นลวดความร้อนประกอบด้วย เส้นลวดความต้านทานติดตั้งที่โพรบ (รูปที่ 1) โดยทั่วไปเส้นลวดความต้านทานทำจากแพลททินัมหรือทังสเตน อุปกรณ์วัดการไหลชนิดนี้ทำงานโดยอาศัยหลักการสูญเสียความร้อนของเส้นลวดที่ได้รับความร้อน เมื่อมีลมผ่านเส้นลวดความร้อนจะเย็นตัวลง โดยอัตราการเปลี่ยนแปลงความร้อนที่เกิดขึ้นที่เส้นลวดเป็นสัดส่วนโดยตรงกับอัตราเร็วของลมที่เคลื่อนที่ผ่านตัววัด ข้อดีของเครื่องมือวัดชนิดนี้ คือ ให้ค่าตอบสนองการวัดที่เร็ว ละเอียด และสามารถใช้วัดกระแสลมที่มีความเร็วต่ำได้ เนื่องจากเครื่องมือวัดมีความไว (sensitivity)ต่อการตรวจจับสูง

แอนนิโมมิเตอร์แบบเส้นลวดความร้อนแบ่งเป็น 2 ชนิด คือ ชนิดควบคุมกระแสไฟฟ้าคงที่ และชนิดควบคุมอุณหภูมิคงที่

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

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

ที่มา : http://www.foodnetworksolution.com/wiki/word/7252/hot-wire-anemometer-แอนนิโมมิเตอร์แบบเส้นลวดความร้อน

โดย : ผศ.ดร.นวภัทรา หนูนาค

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