TÀI LIỆU THƯ VIỆN SỐ

Tương quan giữa cách biểu diễn đồ thị và số cạnh của đồ thị

Nội dung của bài viết này trình bày hai cách biểu diễn đồ thị trên máy tính là ma trận trọng số và danh sách cạnh, trong đó cách biểu diễn đồ thị bằng ma trận trọng số thích hợp hơn cho các đồ thị dày cạnh còn biểu diễn bằng danh sách cạnh thì thích hợp hơn cho các đồ thị ít cạnh. Điều này được chứng minh bằng thực nghiệm trong giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đơn đồ thị có trọng số.

Từ khóa: Số cạnh của đồ thị, Cách biểu diễn đồ thị, Lý thuyết đồ thị, Ma trận trọng số, Bài toán trên đồ thị