Bài tập về đồ thị thì nhiều nhưng thường ở dạng các bài toán ứng dụng và khá phức tạp. Nếu tìm hiểu về các bài tập lý thuyết thì bạn đọc trong giáo trình DSAPTB mình đã giới thiệu trong mục "tài liệu cần thiết cho việc học giải thuật", ngoài ra có một số cuốn sáCh khác nói về đồ thị như : Toán rời rạc, lý thuyết đồ thị...
-Còn các bài trên của bạn thì như sau:
+ trong số các đơn đồ thị có n đỉnh thì đồ thị đầy đủ có nhiều cạnh nhất C(2, n)(Các đỉnh đều có cạnh nối với tất cả các đỉnh còn lại), do đó dễ dàng suy ra điều cần chứng minh
+ bài 2: dùng thuật toán warshall chỉ mất 3 vòng for, khá đơn giản. Còn có những cách phức tạp nhưng nhanh hơn thì bạn tìm trong mục đường đi ngắn nhất sẽ thấy.
+ bài 3: sử dụng tìm kiếm sâu hoặc rộng kết hợp với đánh dấu các đỉnh đã duyệt.
Code:
for (int i=1; i<= n; i++)
if (mark[i])
{
sothanhphan++;
dfs(i);
}