Lý thuết đồ thị | Bài tập Lý thuyết đồ thị

[soda_chanhmuoi]

Có ai có bài tập về LTDT post lên cho mình với, những bài về chứng minh như:
-Chứng tỏ rằng nấu đồ thị đơn G có k thành phần liên thông và các thanh 2pha62n đó lần lượt có n,n2,n3….nk đỉnh , thì số cạnh của G ko vượt quá:
C(2,n1) +C(2,n2)+…+C(2,nk).
-Chứng tỏ rằng nấu đồ thị đơn G có k thành phần liên thông và các thanh 2pha62n đó lần lượt có n,n2,n3….nk đỉnh , thì số cạnh của G ko vượt quá:
C(2,n1) +C(2,n2)+…+C(2,nk).
hay những bài về viết code như:
-Giả sử đơng đồ thị vô hướng G(V,E) có : n đỉnh , mọi trọng số đều dương, các trọng số ko trùng nhau, được biểu diễn bằng ma trận kề a(nxn)
ta xây dựng đồ thị G(V,E) từ G(V, E) theo cách lấy trọng số của cạnh (u,v) trong G’ là độ dài đường đi ngắn nhất giữa 2 đỉnh u,v trong đồ thị G . Hãy viết hàm tìm ma trận kề b(nxn) của đồ thị G
-Giả sử đơn dồ thị vô hướng G(E,V) với n đỉnh được tổ chức lưu trữ bằng ma trận kề a. Hãy viết hàm trả về số thành phần liên thông của G.
Nếu có bài giải luôn thì càng tốt! thanks!

[hailoc12]

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.

  for (int i=1; i<= n; i++)
     if (mark[i])
     {
        sothanhphan++;
        dfs(i);
     }

[maxrk]

mình đang cần code bài toán tìm đường đi ngắn nhất dùng ngôn ngữ c.bạn nao biet thi post lên giứp mình với .
thanks

[rox_rook]

Vào đây tham khảo nhé :

http://forums.congdongcviet.com/showthread.php?p=31678#post31678