การแทนที่กราฟด้วยเมตริกซ์ (Adjacency Matrix)

การแทนที่กราฟด้วยเมตริกซ์ (Adjacency Matrix)

โครงสร้างของกราฟเป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยเมตริกซ์ได้ด้วยการกำหนดเมตริกซ์ n x n

รูปที่ 4 กราฟแบบไดกราฟ (Direct Graph)

จากรูปที่ 4 หากนำมาแทนที่ด้วยเมตริกซ์จะแทนที่ได้ด้วยจำนวน n x n ซึ่ง n ก็คือ A,B,C,D,E,F เป็น 6 จำนวน โหนดทำให้ได้ค่าเมตริกซ์ จำนวน 6 x 6 = 36 ช่อง และเมื่อพิจารณาตามทิศทางของการเชื่อมต่อ หากโหนดใดมีเส้นเชื่อมต่อไปยังโหนดอื่นให้ระบุตัวเลขลง ไปในเมตริกซ์เป็น 1 แต่ถ้าโหนดใดไม่ได้มีการระบุว่าทำการเชื่อมต่อก็ให้ระบุเป็น 0 ดังภาพ

รูปที่ 5 การแทนที่กราฟ รูปที่ 4 ด้วยเมตริกซ์

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

พิจารณาโหนด A มีเส้นเชื่อมต่อระบุไป B ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด B มีเส้นเชื่อมต่อระบุไป C, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด C มีเส้นเชื่อมต่อระบุไป D, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด D ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง
พิจารณาโหนด E มีเส้นเชื่อมต่อระบุไป D, F ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด F ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง

รูปที่ 6 กราฟแบบไม่ระบุทิศทาง (Undirected Graph)

จากรูปที่ 6 กราฟแบบไม่ระบุทิศทางเมื่อนำมาแทนที่ด้วยเมตริกซ์สามารถที่จะกำหนดจำนวนช่องได้เช่นเดียวกับไดกราฟ คือ n x n และระบุตัวเลขสำหรับการเชื่อมต่อ คือ 1 และ 0 แต่ในการวางตำแหน่งโหนดในแนวนอน และแนวตั้งนั้น ระบุเป็นโหนดต้นทางและโหนดปลายทางได้ในตัวเดียวกันดังรูปที่ 7

รูปที่ 7 การแทนที่กราฟรูปที่ 6 ด้วยเมตริกซ์

จากรูปที่ 7 เป็นการกำหนดเขียนเลขกำกับเมตริกซ์โดยอ่านค่าทั้งแนวตั้งและแนวนอน เช่น
โหนด A มีเส้นเชื่อมต่อ ที่ระบุไปยังโหนด B ได้และเช่นกันโหนด B สามารถที่จะเชื่อมต่อมายังโหนด A ได้ จึงระบุตัวเลขในเมตริกซ์เป็น 1
โหนด B มีเส้นเชื่อมต่อ A, C, E ได้ระบุเป็น 1 และ A, C, E ระบุช่องโหนด B เป็น 1 เช่นกัน โหนด C มีเส้นเชื่อมต่อ B, D, E ได้ระบุเป็น 1 และ B, D, E ระบุช่องโหนด C เป็น 1 เช่นกัน
โหนด D มีเส้นเชื่อมต่อ C, E ได้ระบุเป็น 1 และ C, E ระบุช่องโหนด D เป็น 1 เช่นกัน
โหนด E มีเส้นเชื่อมต่อ B, C, D, F ได้ระบุเป็น 1 และ B, C, D, F ระบุช่องโหนด ฎ เป็น 1 เช่นกัน
โหนด F มีเส้นเชื่อมต่อ E ได้ระบุเป็น 1 และ E ระบุช่องโหนด F เป็น 1 เช่นกัน