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

Bài 1 Cho G=(V,E) đồ thị có hướng trong đó không có cung (s,t). Chứng minh rằng số đường đi cơ bản nối hai đỉnh s và t là bằng số ít nhất các đỉnh của đồ thị cần loại bỏ để trong đồ thị không còn đường đi nối s với t. Bài 2 Xây dựng thuật toán tìm tập E1 tất cả các cung của đồ thị mà việc tăng khả năng thông qua của bất kỳ cung nào trong E đều dẫn đến tăng giá trị của luồng cực đại trong mạng. . | BÀI TẬP CHƯƠNG 7 Bài 1 Cho G V E đồ thị có hướng trong đó không có cung s t . Chứng minh rằng số đường đi cơ bản nối hai đỉnh s và t là bằng số ít nhất các đỉnh của đồ thị cần loại bỏ để trong đồ thị không còn đường đi nối s với t. ĩỉBài 2 Xây dựng thuật toán tìm tập E1 tất cả các cung của đồ thị mà việc tăng khả năng thông qua của bất kỳ cung nào trong E đều dẫn đến tăng giá trị của luồng cực đại trong mạng. Bài 3 Cho hai dãy số nguyên dương pi i 1 2 . m và qj j 1 2 . n . Hãy xây dựng ma trận A aij i 1 2 . m j 1 2 .n với các phần tử ai j ĩ 0 1 có tổng các phần tử trên dòng i là Pi tổng các phần tử trên cột j là qj. ĩ Bài 4 Có m chàng trai n cô gái và k bà mối Mỗi bà mối p p 1 2 . k có một danh sách Lp một số chàng trai và cô gái trong số các chàng trai và cô gái nói trên là khách hàng của bà ta. Bà mối p có thể se duyên cho bất cứ cặp trai gái nào là khách hàng của bà ta nhưng không đủ sức tổ chức quá dp đám cưới. Hãy xây dựng thuật toán căn cứ vào danh sách Lp dp p 1 2 . k đưa ra cách tổ chức nhiều nhất các đám cưới giữa m chàng trai và n cô gái với sự giúp đỡ của các bà mối. Ĩ Bài 5 Chuyển bi Cậu bé vẽ N N 100 vòng tròn đánh số từ 1 tới N và tô màu các vòng tròn đó có thể có các vòng tròn có màu giống nhau sau đó nối từng cặp các cung định hướng mỗi cung có một màu nhất định. Các màu của cung và vòng tròn được đánh số từ 1 đến 100. Cậu bé chọn 3 số nguyên khác nhau L K và Q nằm trong phạm vi từ 1 tới N đặt vào trong các vòng tròn số L và K mỗi vòng một hòn bi sau đó bắt đầu di chuyển bi theo nguyên tắc sau Bi chỉ được chuyển theo cung có màu trùng với màu của vòng tròn chứa viên bi thứ 2. vBi chỉ được chuyển theo chiều cung Hai viên bi không được đồng thời ở cùng một vòng tròn Không nhất thiết phải di chuyển lần lượt các viên bi Quá trình di chuyển kết thúc khi một trong hai viên bi tới vòng tròn Q. Hãy lập trình xác định cách di chuyển để chấm dứt quá trình sau một số ít nhất các bước chuyển. Dữ liệu vào từ file Dòng đầu 4 số nguyên N L K Q Dòng thứ 2 N

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