วิธีการใช้งานเวปไซต์นี้

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

การประยุกต์ของกราฟ

บทนิยาม วงจร (circuit) คือแนวเดินที่เส้นเชื่อมทั้งหมด แตกต่างกัน โดยมีจุดเริ่มต้น
                และ จุดสุดท้ายเป็นจุดเดียวกัน
บทนิยาม     วงจรออยเลอร์ (Euler circuit) คือ วงจรที่ผ่านจุดยอดทุกจุด และ เส้นเชื่อมทุกเส้นของกราฟ
              โดยที่จุดสามารถซ้ำกันได้ และจะเรียกกราฟที่มีวงจรออยเลอร์ว่า กราฟออยเลอร์

ทฤษฏีบท 3 กำหนดกราฟ G เป็นกราฟเชื่อมโยง G จะเป็นกราฟออยเลอร์ก็ต่อเมื่อ
                    จุดยอดทุกจุดของ G เป็นจุดยอดคู่

ตัวอย่าง จงพิจารณาว่ากราฟนี้เป็นกราฟออยเลอร์หรือไม่

คำตอบคือ ไม่ เพราะจุดยอดทุกจุดในกราฟนี้เป็นจุดยอดคี่

บทนิยาม  ค่าน้ำหนัก (weight) ของเส้นเชื่อม e ในกราฟ คือ จำนวนที่ไม่เป็นลบที่กำหนดไว้บนเส้นเชื่อม 

บทนิยาม        กราฟถ่วงน้ำหนัก ( weighted graph) คือกราฟที่เส้นเชื่อมทุกเส้นมีค่าน้ำหนัก

จากบทนิยาม  การกำหนดจำนวนไว้บนเส้นเชื่อมแต่ละเส้น อาจมีจุดมุ่งหมายเพื่อแทนระยะห่างของ

                        ตำแหน่งต่างๆ หรือเวลาที่ใช้เดินทางบนเส้นทางนั้น จากจุดหนึ่ง ถึง จุดที่ต้องการ

                       ในชีวิตประจำวัน [ค่าน้ำหนัก = เส้นทาง (ระยะ) , กราฟถ่วงน้ำหนัก = แผนที่]

                                         
บทนิยาม วิถี (path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมด แตกต่างกัน (ไปโดยไม่ย้อนกลับ)
           
บทนิยาม    วิถีที่สั้นที่สุด จากจุดยอด A ถึง Z ในกราฟถ่วงน้ำหนัก คือ วิถี A-Z ที่ ผลรวม
                ของค่าน้ำหนักบนเส้นเชื่อมทุกเส้นในวิถี A-Z ที่มีค่าน้อยที่สุด (ไปถึงจุดหมายเร็วที่สุด)
                                   
ตัวอย่าง จงหาวิถีที่สั้นที่สุด จาก A ถึง E
                                   
             ตอบ วิถีที่สั้นที่สุดคือ A,B,D,E ค่าน้ำหนักคือ 2+1+3 = 6 ซึ่งมีค่าน้อยที่สุด
บทนิยาม วัฏจักร (cycle) คือ วงจร ทีี่ไม่มีจุดยอดซ้ำกัน ยกเว้น จุดเริ่มต้นและจุดสุดท้าย
                 (จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน)
บทนิยาม ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร
ตัวอย่าง

 ไม่เป็น ต้นไม้ เพราะมีวัฏจักร

เป็นต้นไม้

ไม่เป้นต้นไม้เพราะไม่เป้นกราฟเชื่อมโยง

         

    เป็นต้นไม้

บทนิยาม กราฟย่อย (subgraph) ของกราฟ G คือ กราฟที่ประกอบด้วยจุดยอดและเส้นเชื่อมใน G 

               กล่าวคือ กราฟ H เป้นกราฟยอยของกราฟ G ก็ต่อเมื่อ V(H) เป็นสับเซต V(G) และ 

               E(H) เป็นสับเซตของ E(G) (หากไม่มีเส้นเชื่อมก็เป็น subgraph ได้)

ตัวอย่าง

จากกราฟข้างต้นจงพิจารณาว่ากราฟใดเป็น กราฟย่อยของกราฟนี้

เป็นกราฟย่อย

ไม่เป็นกราฟย่อย

เป็นกราฟย่อย

บทนิยาม  ต้นไม้แผ่ทั่ว (spanning tree) คือ ต้นไม้ ซึ่ง เป็น กราฟย่อยของกราฟเชื่อมโยง 

                 ที่ บรรจุจุดยอดทุกจุดของ G 

บทนิยาม ต้นไม้แผ่ท่วที่น้อยที่สุด (minimal spaning tree) คือค่าน้ำหนักที่น้อยที่สุดของต้นไม้แผ่ทั่วนั้น

                (ในกรณีต้นไม้แผ่ทั่วในกราฟถ่วงน้ำหนัก)

ตัวอย่าง ต้นไม้แผ่ทั่ว

ต้นไม้แผ่ทั่วของกราฟนี้อาจมีดัีงนี้

  

ตัวอย่าง ต้นไม้แผ่ทั่วที่น้อยที่สุดจากกราฟนี้

พิจจารณา

1+2+1ไม่น้อยที่สุด1+2+1ไม่น้อยที่สุด

1+1+1น้อยที่สุด

ข้อสังเกตุ : ต้นไม้ จะไม่มีเส้นขนานและวงวน

         จากองค์ความรู้เรื่อง ต้นไม้แผ่ทั่วนี้สามารถนำไปประยุกต์ใช้ในชีวิตประวันได้หลายแบบ อาทิ
การสร้างโปรแกรมคอมพิมเตอร์  การทำงานของ search engine เป็นต้น

แนวเดิน

บทนิยาม ให้ U และ V เป็นจุดยอดของกราฟG แนวเดิน U - V ( U-V walk) คือลำดับจำกัดของ 
                จุดยอด และ เส้นเชื่อมสลับกัน เช่น
                 U = u0,e1,u1.e2,u2,...,un-1,en,un = V
                 โดยเริ่มต้นที่จุด U และสิ้นสุดที่จุด V  และแต่ละเส้นเชื่อม e1 จะ้เกิดกับจุดยอด ui-1 และ ui 
                 เมื่อ i = {1,2,3,...,n}
 ข้อสังเกตุ : ยิ่งกราฟมีความซับซ้อนมากเท่าไร จำนวนเส้นทางแนวเดินก็ยิ่งมากขึ้นเท่านั้น

                             แนวเดินC→A→D เขียนเป็นลำดับได้ว่า

                                     C, e1, A, e3,D หรืออื่น ๆ

บทนิยาม  กราฟ G จะเรียกว่า กราฟเชื่อมโยง (connected    graph )

                  ก็ต่อเมื่อ ทุกๆจุดยอด มีแนวเดินทั่วถึงกัน

เป็นกราฟเชื่อมโยง

ไม่เป็นกราฟเชื่อมโยง

         

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

บทนิยาม ดีกรี (degree) ของจุดยอด V ในกราฟ G คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด V
               ใช้สัญลักษณ์ deg V แทน ดีกรีของจุดยอด V

ตัวอย่าง

 จากกราฟข้างต้น จะได้ว่า
                                deg A = 2
                                deg B = 3
                                deg C = 2
                                deg D = 3 (วงวนเท่ากับ 2 ดีกรี)
                                deg E = 0 (ไม่มีเส้นเชื่อมมาเกิดกับจุดนี้)
ทฤษฏีบท 1 ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่า ของจำนวนเส้นเชื่อมในกราฟ

และมีค่าเป็นจำนวนคู่เสมอ เมื่อให้ m เป็นจำนวนเส้นเชื่อมในกราฟ G จะได้ว่า

และจากกราฟข้างต้นจะได้ผลรวมของดีกรีคือ 2+3+2+3+0 = 10 ซึ่งเป็น สองเท่า ของจำนวนเส้นเชื่อมในกราฟ

ความสัมพันธ์ระหว่างดีกรีกับจุดยอด
บทนิยาม  จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (Even vertex)
                จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (Odd vertex

ตัวอย่าง

              จะได้ว่า  จุดยอดคู่ คือ จุดA และ D
                            จุดยอดคี่ คือ จุดB และ C

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

        การนำไปใช้ในชีวิตประจำวัน อาทิ การจัดการแข่งขันต่างๆแบบพบกันหมด เป็นต้น
ข้อสังเกตุ : เมื่อกราฟใดมีจำนวนจุดยอดคี่เป็นจำนวนคี่แสดงว่า กราฟนั้นไม่มีอยู่จริง

ลักษณะของเส้นเชื่อม

บทนิยาม เส้นเชื่อมตั้งแต่ 2 เส้นขึ้นไปที่เชื่อมระหว่างจุดยอดคู่เดียวกัน เรียกว่า เส้นเชื่อมขนาน 
                (parallel edge)

ตัวอย่าง เส้นเชื่อมขนาน

บทนิยาม วงวนคือ เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกเส้นนี้ว่า วงวน (Loop)

ตัวอย่าง วงวน

กราฟ graph

บทนิยาม กราฟ G ประกอบด้วยเซตจำกัด 2 เซต คือ
            1.เซตที่ไม่เป็นเซตว่างของจุดยอด (vertex ; V(G) )
            2.เซตของเส้นเชื่อม (edge ; E(G) ) ที่เช่อมระหว่างจุดยอด
   ข้อสังเกตุ : เซตของเส้นเชื่อม อาจเป็นเซตว่างได้

ตัวอย่างของกราฟ

      องค์ความรู้เกี่ยวกับกราฟนี้นำไปใช้อย่างหลากหลายในชีวิตประจำวัน อาทิเช่น การทำแผนที่ หรือ แม้กระทั่งการเชื่อมโยงเวปไซต์ของบราวเซอร์ อันจะกล่าวถึงต่อไป

ความเป็นมาของกราฟ

มนุษย์ในอดีตพยายามจะอธิบายถึงสิ่งต่างๆบนโลก จึงได้คิดค้นศาสตร์ต่างๆขึ้นมา โดยคณิตศาสตร์นั้น ว่ากันว่าเป็นศาสตร์ที่บ่งบอกถึงภาษาของธรรมชาติ ซึ่งอาจกล่าวได้ว่าเป็นศาสตร์ชนิดแรกที่ถือกำเนิดขึ้นมาบนโลก ในที่นี่จะขอกล่าวถึงหนึ่งในองค์ความรู้ของคณิตศาสตร์ที่เกี่ยวข้องกับชีวิตประจำวันของเราเรื่องหนึ่ง นั่นก็คือ ทฤษฏีกราฟเบื้องต้น หากมีข้อผิดพลาดประการใดต้องขออภัยมา ณ ที่นี้ด้วย
ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ Solutio problematis ad geometriam situs pertinentis ในปี ค.ศ. 1736 (พ.ศ. 2279) หรือที่รู้จักกันในนาม ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Seven Bridges of Königsberg) เขาสนใจวิธีที่จะข้ามสะพานทั้ง 7 แห่งนี้ โดยข้ามแต่ละสะพานเพียงครั้งเดียวเท่านั้น ผลงานนี้ยังถือว่าเป็นงานแนวทอพอโลยีชิ้นแรกในเรขาคณิต กล่าวคือเป็นงานที่สนใจเฉพาะโครงสร้างของรูปเรขาคณิตที่ไม่ขึ้นกับขนาด ระยะ หรือการวัดใดๆ งานชิ้นสำคัญนี้ยังได้แสดงความเกี่ยวข้องอย่างลึกซึ้งระหว่างทฤษฎีกราฟและทอพอโลยี

ในปี ค.ศ. 1845 (พ.ศ. 2388) กุสตาฟ คีร์คฮอฟฟ์ ได้เผยแพร่ผลงานที่รู้จักกันภายใต้ชื่อกฎวงจรไฟฟ้าของคีร์คฮอฟฟ์ ที่แสดงความสัมพันธ์ของกระแสและความต่างศักย์ บนกราฟที่แทนวงจรไฟฟ้า

ต่อมาในปี ค.ศ. 1852 (พ.ศ. 2395) ฟรานซิส กัทธรี ได้ตั้งปัญหาสี่สี (Four color problem) เพื่อศึกษาถึงความเป็นไปได้ที่จะใช้สีเพียง 4 สี เพื่อระบายให้กับประเทศต่าง ๆ บนแผนที่ใด ๆ โดยที่ประเทศเพื่อนบ้านจะไม่มีสีเดียวกัน. ปัญหานี้ได้ถูกแก้ในอีกมากกว่า 100 ปีถัดมา ในปี ค.ศ. 1976 (พ.ศ. 2519) โดย เคนเนธ แอปเพล และวูล์ฟกัง ฮาเคน ซึ่งใช้คอมพิวเตอร์เข้าช่วยในการพิสูจน์ ซึ่งทำให้ได้รับการวิพากษ์วิจารณ์อย่างกว้างขวาง. อย่างไรก็ตามจากความพยายามในการแก้ปัญหา 4 สีนี้ ทำให้มีการสร้างแนวคิดและนิยามพื้นฐานในทฤษฎีกราฟขึ้นอย่างมากมาย จนอาจจะกล่าวได้ว่าจุดเริ่มต้นของทฤษฎีกราฟเกิดจากปัญหาสี่สีนี้เอง

กราฟมักถูกนำเสนอในลักษณะของรูปภาพ โดยใช้จุดแทนจุดยอดแต่ละจุด และลากเส้นระหว่างจุดยอดถ้าจุดยอดทั้งสองนั้นมีเส้นเชื่อมถึงกัน ถ้ากราฟมีทิศทาง ทิศทางของเส้นเชื่อมจะถูกระบุโดยใช้ลูกศร

เราไม่ควรจะสับสนระหว่างกราฟที่วาดออกมากับกราฟ (ที่เป็นโครงสร้างนามธรรม) เนื่องจากกราฟหนึ่ง ๆ สามารถเขียนออกมาได้หลายแบบ และสาระหลักของกราฟนั้นมีแค่ว่าจุดยอดใด เชื่อมต่อกับจุดยอดใด ด้วยเส้นเชื่อมกี่เส้น ไม่ใช่วิธีการที่วาดมันออกมา ในทางปฏิบัติแล้ว การจะตัดสินว่ากราฟที่วาดออกมาสองกราฟนั้น มาจากกราฟเดียวกัน ในบางกรณี การวาดกราฟบางแบบอาจมีความเหมาะสมและทำให้เข้าใจได้ง่ายกว่าแบบอื่น

linked

http://th.wikipedia.org/wiki/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F