TAILIEUCHUNG - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - BÀI TẬP CHƯƠNG 6

Bài 1: Di chuyển trên các hình tròn Cho N hình tròn (đánh số từ 1 đến N). Một người muốn đi từ hình tròn này sang hình tròn khác cần tuân theo qui ước: Nếu khoảng cách giữa 2 điểm gần nhất của 2 hình tròn không quá 50 cm thì có thể bước sang. | BÀI TẬP CHƯƠNG 6 ĩ Bài 1 Di chuyển trên các hình tròn Cho N hình tròn đánh số từ 1 đến N . Một người muốn đi từ hình tròn này sang hình tròn khác cần tuân theo qui ước Nếu khoảng cách giữa 2 điểm gần nhất của 2 hình tròn không quá 50 cm thì có thể bước sang. Nếu khoảng cách này hơn 50cm và không quá 80cm thì có thể nhảy sang. Các trường hợp khác không thể sang được. Một đường đi từ hình tròn này sang hình tròn khác đuợc gọi là càng tốt nếu số lần phải nhảy là càng ít. Hai đường đi có số lần nhảy bằng nhau thì đường đi nào có số hình tròn đi qua ít hơn thì đường đi đó tốt hơn. Các hình tròn được cho trong một file văn bản trong đó dòng thứ i mô tả hình tròn số hiệu i i 1 2 . N bao gồm 3 số thực hoành độ tâm tung độ tâm độ lớn bán kính đơn vị đo bằng mét . Lập trình đọc các hình tròn từ một file văn bản tên file vào từ bàn phím sau đó cứ mỗi lần đọc số hiệu hình tròn xuất phát S và hình tròn kết thúc T từ bàn phím chương trình sẽ đưa ra đường đi từ S đến T là tốt nhất theo nghĩa đã nêu hoặc thông báo là không có . Yêu cầu đường đi được viết dưới dạng một dãy các số hiệu hình tròn lần lượt cần được đi qua trong đó nói rõ tổng số các bước nhảy tổng số các hình tròn đi qua và những bước nào cần phải nhảy. Giới hạn sô hình tròn không quá 100. ĩ Bài 2 Tìm hành trình tốn ít xăng nhất Trên một mạng lưới giao thông một người muôn đi từ điểm A đến điểm B bằng xe máy. Xe chứa được tôi đa 3 lít xăng và chạy 100km hết 2 5 lít. Các trạm xăng chỉ được đặt ở các điểm dân cư không đặt ở giữa đường và người này không mang theo bất kỳ thùng chứa xăng nào khác. Hãy viết chương trình nhập vào mạng lưới giao thông và xác định giúp người này tuyến đường đi từ A đến B sao cho ít tôn xăng nhất. Bài 3 Di chuyển giữa các đảo Trên một đảo quôc có N hòn đảo. Giả sử tất cả các đảo đều có hình dạng là hình chữ nhật nằm ngang. Trên mỗi hòn đảo có thể có sân bay nằm ở trung tâm đảo có thể có cảng nằm ở 4 góc đảo. Trên mỗi đảo đều có tuyến đường xe buýt nôi 4 góc đảo với nhau và với trung tâm đảo. .

• 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ị