Bài giảng Toán rời rạc 2 - Chương 2: Biểu diễn đồ thị trên máy tính - Ngô Xuân Bách

Học viện Công nghệ Bưu chính Viễn thông  
Khoa Công nghệ thông tin 1  
Toán ri rc 2  
Biu din đthtrên máy tính  
Ngô Xuân Bách  
Ni dung  
Biểu diễn đồ thị bằng ma trận kề  
Biểu diễn đồ thị bằng ma trận liên thuộc  
Biểu diễn đồ thị bằng danh sách cạnh  
Biểu diễn đồ thị bằng danh sách kề  
2
Ma trn kca đthvô hướng (1/2)  
Xét đồ thị vô hướng 퐺 =< 푉, 퐸 >, với tập đỉnh 푉 =  
*1,2, … , 푛+, tập cạnh 퐸 = *푒1, 푒2, . . . , 푒+. Ta gọi ma trận kề  
của đồ thị là ma trận 푛 × 푛 có các phần tử hoặc bằng 0  
hoặc bằng 1 theo qui định như sau:  
o 퐴 = *푎푖푗: 푎푖푗 = 1 푛ế푢 (, ) ∈ 퐸, 푖푗 = 0 푛ế푢 (, ) ∉ 퐸; ,  =  
1, 2, . . . , 푛+.  
(Phương ND, 2013)  
3