tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 2 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 2 Biểu diễn đồ thị, được biên soạn gồm các nội dung chính sau: Các cách biểu diễn đồ thị; Sự đẳng cấu của các đồ thị; Hướng dẫn cài đặt. Mời các bạn cùng tham khảo! | Chương 2 Biểu diễn đồ thị Nội dung I. Các cách biểu diễn đồ thị II. Sự đẳng cấu của các đồ thị III. Hướng dẫn cài đặt Chương 2 Biểu diễn đồ thị 2 Lý thuyết đồ thị I. Các cách biểu diễn đồ thị Các cách biểu diễn đồ thị Ma trận kề Danh sách cạnh Danh sách kề Ma trận liên thuộc Ma trận trọng số Danh sách cung Chương 2 Biểu diễn đồ thị 3 Lý thuyết đồ thị . Ma trận kề đơn đồ thị vô hướng Định nghĩa Đơn đồ thị G V E với tập đỉnh V 0 n-1 tập cạnh E e0 e1 em-1 . Ta gọi ma trận kề của G là A ai j i j 0 n-1 với 0 if i j E ai j 1 if i j E 0 1 2 3 4 0 0 1 1 0 1 1 1 0 1 0 1 2 1 1 0 0 0 3 0 0 0 0 0 4 1 1 0 0 0 Chương 2 Biểu diễn đồ thị 4 . Ma trận kề đơn đồ thị có hướng Định nghĩa Giống đơn đồ thị có hướng E là tập các cung 0 if i j E ai j 1 if i j E 0 1 2 3 4 0 0 0 1 0 1 1 1 0 0 0 0 2 0 1 0 1 0 3 0 0 0 0 1 4 0 1 0 0 0 Chương 2 Biểu diễn đồ thị 5 . Ma trận kề Đa đồ thị Định nghĩa E là tập các cạnh cung Ai j là số cạnh nối đỉnh i và đỉnh j 0 1 2 3 4 5 0 0 1 1 0 1 0 1 1 0 1 0 1 0 2 1 1 0 2 0 0 3 0 0 2 0 1 1 4 1 1 0 1 0 1 5 0 0 0 1 1 1 Chương 2 Biểu diễn đồ thị 6 . Ma trận kề Đa đồ thị Một số tính chất của ma trận kề Ma trận kề của đồ thị vô hướng là đối xứng a i j a j i . Ngược lại ma trận đối xứng 0 1 có đường chéo chính bằng 0 bậc n sẽ tương ứng với đơn đồ thị vô hướng n đỉnh. Nếu đồ thị vô hướng Tổng dòng thứ i Tổng cột thứ i deg i Nếu đồ thị có hướng Tổng dòng i deg i Tổng cột i deg - i Ưu điểm và hạn chế của ma trận kề Chương 2 Biểu diễn đồ thị 7 . Ma trận trọng số đơn đồ thị Định nghĩa Đơn đồ thị G V E với tập đỉnh V 0 n-1 tập cạnh E e0 e1 em-1 . Ta gọi ma trận kề trọng số của G là A ai j i j 0 n-1 với b if i j E Ck là một giá trị nào đó được a i j quy định trước 0 -1 - . c k if i j E 0 1 2 3 4 5 0 0 4 3 0 7 0 1 4 0 5 0 3 0 2 3 5 0 2 0 0 3 0 0 2 0 5 2 4 7 3 0 5 0 3 5 0 0 0 2 3 0 Chương 2 Biểu diễn đồ thị 8 . Danh sách cạnh Đối với các đồ thị thưa n đỉnh m cạnh m lt 6n người ta thường dùng cách biểu diễn danh sách cạnh để tiết kiệm không gian lưu trữ Lưu .