วันอังคารที่ 26 เมษายน พ.ศ. 2559

บทที่ 7 กราฟ (GRAPH)

กราฟ (GRAPH)
                กราฟ (Graph) เป็นโครงสร้างที่แทนความสัมพันธ์ระหว่างข้อมูลที่มีข้อมูลจำกัดน้อย ความสัมพันธ์ที่ไม่มีจำกัดว่าต้องเป็นตามลำดับชั้น หรือข้อมูลต้องเรียงจากซ้ายไปขวา
                กราฟ (Graph) หมายถึง เซตของสิ่งที่เรียกว่า โหนด (Note หรือ Vertex) และเส้นเชื่อม (Edge) “โหนดคือ สมาชิกของความสัมพันธ์ระหว่างโหนด 2 โหนด จะเขียนอยู่ในรูปของคู่อันดับ (a , b)

                กราฟแบ่งออกเป็น 2 ประเภท คือ
                กราฟไม่มีทิศทาง (Undirected Graph) เป็นกราฟที่มีเส้นเชื่อมระหว่างโหนด 2 ตัวไม่มีทิศทาง


                  กราฟมีทิศทาง (Directed Graph) เป็นกราฟที่มีเส้นเชื่อมระหว่างระบุทิศทางกำกับอยู่


           จากกราฟรูปที่ 8.2 เป็นภาพแสดงความสัมพันธ์แบบไม่มีทิศทาง เส้นเชื่อมระหว่างโหนด 2 ตัวไม่มีทิศทางระบุไว้ ดังนั้นจากโหนด ไปโหนด B มีความหมายเหมือนโหนด ไปโหนด ในกราฟมีทิศทาง รูปที่ 8.3 เส้นเชื่อมโหนดมีทิศทางกำกับอยู่ ความหมายจากโหนด ไปโหนด ไม่เหมือนกับ ไป A 
             เส้นทางเดินในกราฟ
                การกำหนดทางการเดินในกราฟมีเชื่อมต่อกัน 2 ลักษณะ คือ ต่อกันโดยทางตรง (Directly Connection) และต่อกันแบบทางอ้อม (Indirectly Connected) ซึ่งการเชื่อต่อของลักษณะทางอ้อม และเส้นเชื่อมที่เข้าและออกจากแต่ละโหนดจะเรียกว่า ดีกรี (Degree) ดังนั้น ดีกรีจะ หมายถึง จำนวนของเส้นเชื่อมที่ต่อโดยตรงกับโหนดนั้น ๆ มี 2 ชนิด คือ เอาต์ดีกรี (Outdegree) เป็นเส้นที่ออกจากโหนด และอินดีกรี (Indegree) เป็นเส้นที่เข้ามายังโหนดนั้น ๆ

การแทนโครงสร้างข้อมูลกราฟ
                การแทนโครงสร้างข้อมูลกราฟเป็นการแทนความสัมพันธ์ที่เกิดขึ้นจากกราฟด้วยรูปแบบที่สามารถนำไปประมวลผลด้วยคอมพิวเตอร์ แบ่งออกเป็น 2 วิธีคือ
                1. Adjacency Matrices คือ การแทนด้วยอาร์เรย์ขนาด N x N ด้วยการกำหนดหมายเลข 1 ในแถวที่ และสดมภ์ที่ ในเมตริกซ์ โดยที่ และ เป็นหมายเลขโหนดของกราฟ ถ้า Aij  มีค่าเป็น 1 หมายถึง มีความสัมพันธ์ระหว่างโหนด  i ไปโหนด j  (มีเส้นเชื่อมจาก ไป j)  ถ้า Aij  มีค่าเป็น 0 หมายถึง ไม่มีความสัมพันธ์ระหว่างโหนด ไปโหนด ไม่มีเส้นเชื่อมจาก ไป j )
                2. Node Directory  หรือ Linked  list  จากการแทนกราฟด้วยอาร์เรย์จะต้องมีการเก็บข้อมูลเส้นทางเชื่อมต่อทุก ๆ เส้นทางที่เกิดขึ้น  ทำให้สิ้นเปลืองเนื้อที่ของหน่วยความจำ เนื่องจากต้องมีการจอง
เนื้อที่ ที่ไม่ได้ใช้ไว้ (ค่าเป็น 0 )  แต่การแทนข้อมูลด้วยโครงสร้างแบบ Node Directory จะเก็บข้อมูลที่มีความสัมพันธ์กัน (ค่าไม่เป็น 0การหาตำแหน่งของข้อมูลทำได้ง่ายและรวดเร็วกว่า การจัดเก็บข้อมูลจะมีลักษณะของการจัดเก็บข้อมูลที่จัดเรียงต่อเนื่องกันเป็นชุด  และข้อมูลแต่ละชุดจะถูกเรียกว่า โหนด (Node)
ซึ่งมี 2 แบบ คือ Node Directory และ Multi-list
Node Directory
                การแทนกราฟด้วยโครงสร้างข้อมูลแบบ Node Directory ประกอบด้วยข้อมูล 2 ส่วน คือ
                     - Node Directory  คือ ส่วนที่ใช้กับรายละเอียดของข้อมูลที่ใช้งานจริง และส่วนของพอยน์เตอร์ที่ทำหน้าที่ชี้ไปยังโหนดอื่น ๆ
           - Edge Information  คือ ส่วนของข้อมูลตำแหน่งที่อยู่ของโหนดต่อไป ซึ่งประกอบด้วย เซ็ตของโครงสร้างข้อมูลของการเชื่อมโยง คือชื่อโหนด (Node Identifier) และ พอยน์เตอร์ที่ชี้ไปยังสมาชิกตัวถัดไป



Multi-list
             การแทนกราฟด้วย Multi-list  ประกอบด้วย 2 ส่วนคือ ส่วนที่เป็น Node Directory ที่จัดเก็บข้อมูล
จริง ๆ และส่วนของ Edge Information  ซึ้งข้อมูลในส่วนของ Edge Information  ซึ้งข้องมูลในส่วนของ Edge Information จะประกอบด้วยข้อมูล 4 ส่วน คือ (1) ข้อมูลชื่อของโหนด i (Vi)  (2) ตำแหน่งของข้อมูลโหนดถัดจากโหนด I (Next i)  (3) ชื่อ j (Viและ (4) พอยน์เตอร์ที่ใช้ไปยังตำแหน่งของข้อมูลโหนดถัดจากโหนด j (Next j) โดยในโหนด Directory จะชี้ไปยัง Edge Information แต่ละตัว

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

PERT
             PERT เป็นเทคนิคคำหรับคำนวณเวลาที่เร็วที่สุดในการทำกิจกรรมแต่ละกิจกรรมให้เสร็จมีข้อกำหนัด คือ กิจกรรมจะต้องเป็นไปตามลำดับการทำงานก่อนหลัก กิจกรรมต้องทำให้เสร็จก่อนจึงสามารถทำกิจกรรมอื่นได้ การคำนวณหาระยะทางของการทำกิจกรรม การพิจารณา 2 เหตุการณ์ คือ เวลาที่น้อยที่สุดของการทำกิจกรรมจะมีการพิจารณา 2 เหตุการณ์ คือ เวลาที่น้อยที่สุดของการทำกิจกรรมตั้งแต่เริ่มต้นจนถึงสิ้นสุดกิจกรรม และเวลาที่มากที่สุดของการทำกิจกรรมตั้งแต่เริ่มต้นจนถึงสิ้นสุดกิจกรรม

             การทำกิจกรรมให้เสร็จสิ้นมี 3 เส้นทาง คือ 1 , 2 และ 3 โดยเส้นทางที่ใช้เวลาน้อยที่สุด คือ เส้นทาง ที่ 2 และเส้นทางที่ใช้เวลามากที่สุด คือ เส้นทางที่ 2 จากการคำนวณเวลาของการทำกิจกรรมในแต่ละเส้นทาง ทำให้เราทราบว่ากิจกรรมหนึ่งควรทำให้เสร็จภายในเวลากี่วัน และ ใช้เวลาทำงานอย่างต่ำกี่วัน เพื่อ เป็นประโยชน์ต่อการวางแผนการทำงานและควบคุมค่าใช้จ่ายได้อย่างมีประสิทธิภาพ


ไม่มีความคิดเห็น:

แสดงความคิดเห็น