การแทนกราฟ

กราฟ คือโครงสร้างที่มีจุดและเส้นลากระหว่างจุด ซึ่งเราเรียกว่า vertex หรือ โหนด (node) และ อาร์ค (arc)

ตัวอย่างกราฟ มี โหนด  N = (a, b, c, d, e, f)
มี อาร์ค   A = (ab, ac, bc, be, bf, ef, ed, cd, df)

   ถ้ากราฟที่ไม่มีการลาดเชื่อมต่อระหว่างโหนดเลย มีแต่โหนดเราเรียกว่า กราฟว่าง (null graph)

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

   กราฟที่มีการเชื่อมต่อระหว่างโหนดได้ครบสมบูรณ์เรียกว่า กราฟสมบูรณ์ (complete graph)

ตัวอย่างกราฟสมบูรณ์

ชนิดของกราฟ

กราฟที่ใช้ทางคณิตศาสตร์ยังมีการแบ่ง กราฟในลักษณะทิศทางที่ประกอบในส่วนของแต่ละโหนด ว่าแต่ละเส้น (edge) มีทิศทางไปในทางใด ดังนั้นจึงแบ่งออกเป็น

กราฟไม่มีทิศทางกราฟมีทิศทาง
กราฟมีทิศทางเดียว
กราฟมีสองทิศทาง

ลักษณะสมบัติของกราฟ

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

ลักษณะของกราฟจึงประกอบด้วยโหนด (node) และเส้น (edge) ที่ลากระหว่างโหนด กราฟจึงเป็น กราฟที่มีทิศทางแบบทางเดียว  กราฟที่มีสองทิศทาง  และกราฟที่ไม่มีทิศทาง ก็ได้

คุณสมบัติของกราฟยังมีส่วนลักษณะพิเศษเฉพาะที่นำมาใช้ประโยชน์ได้หลายอย่าง เช่น เส้นทางกราฟ (path)   ต้นไม้ (tree)   พลาน่ากราฟ (planar graph) คุณสมบัติเหล่านี้สามารถนำมาประยุกต์ใช้งานต่าง ๆ ได้หลายอย่าง โดยเฉพาะการประยุกต์เพื่อใช้ในการแก้ปัญหาสมัยใหม่ต่าง ๆ

ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์