Từ 1 tới 4 trên tổng số 4 kết quả

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

  1. #1
    Ngày gia nhập
    04 2007
    Bài viết
    128

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

    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!

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    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);
         }

  3. #3
    Ngày gia nhập
    12 2007
    Bài viết
    1

    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

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Vào đây tham khảo nhé :
    Code:
    http://forums.congdongcviet.com/showthread.php?p=31678#post31678

Các đề tài tương tự

  1. Thuật toán nén dữ liệu | Lý thuyết nén dữ liệu Huffman (phần 1: ý tưởng)
    Gửi bởi sonhn trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 20-07-2017, 02:34 PM
  2. Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 31
    Bài viết cuối: 30-01-2015, 10:41 PM
  3. Project Demo một số thuật toán Lý thuyết đồ thị
    Gửi bởi zkday2686 trong diễn đàn Dự án & Source code VC++
    Trả lời: 5
    Bài viết cuối: 28-09-2013, 04:53 PM
  4. Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 28
    Bài viết cuối: 15-05-2013, 11:10 AM
  5. Thuật toán trong lý thuyết đồ thị ( Help)
    Gửi bởi sonmobai trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 12-11-2008, 03:22 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn