tailieunhanh - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 2

BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. | CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể bài toán và thuật toán cụ thể . Trong mục này chúng ta sẽ xét một số phương pháp cơ bản được sử dụng để biểu diễn đồ thị trên máy tính đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng. 1. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ Xét đơn đồ thị vô hướng G V E với tập đỉnh V 1 2 . . . n tập cạnh E ei e2 . . . em . Ta gọi ma trận kề của đồ thị G là ma trận. A ai j i j 1 2 . . . n Với các phần tử được xác định theo qui tắc sau đây ai j 0 nếu i j I E và ai j 1 nếu i j ĩ E i j 1 2 . . . n. JThí dụ 1. Ma trận trận kề của đồ thị vô hướng cho trong hình 1 là 1 2 3 4 5 6 1 0 110 10 2 10 10 10 3 110 10 0 4 0 0 10 11 5 110 10 1 6 0 0 0 1 1 0 Hình 1. Đồ thị vô hướng G và Đồ thị có hướng G1 --Các tính chất của ma trận kề 1 Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng tức là a i j a j i i j 1 2 . . . n. ngược lại mỗi 0 1 -ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh còn nói là chính xác đến đẳng cấu với một đơn đồ thị vô hướng n đỉnh. 2 Tổng các phần từ trên dòng i cột j của ma trận kề chính bằng bậc của đỉnh i đỉnh j . 3 nếu ký hiệu aịjp i j 1 2 . . . n là phần tử của ma trận Ap . . .A p thừa số Khi đó aịjp i j 1 2 . . . n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. JThí dụ 2. Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau 1 2 3 4 5 6 1 0 110 0 0 2 0 0 0 0 0 0 3 0 10 10

• Toán học
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị