hanoiforever
10-02-2004, 06:46
Mình có bài toán này chưa giải được, mong các bạn giúp đỡ:
Cho 1 graph G=<V,E> n đỉnh. (graph thỏa mãn điều kiện có đường đi đến tất cả các đỉnh). V là tập hợp các đỉnh, E là tập hợp các cạnh của đồ thị G.
Mỗi đỉnh v có 1 trạng thái S(v)= 1 hoặc -1
Mỗi cạnh có một trọng số w cho trước (có thể <0 hoặc >=0) .
Một đỉnh v được gọi là "tốt" khi : B(v)>=0, "xấu" khi B(v)<0
B(v) được tính như sau: B(v)=S(v)*(tổng(S(u)*w(u,v))) u là tất cả các đỉnh có cạnh nối với đỉnh v.
Câu hỏi:
Tìm trạng thái cho các đỉnh của đồ thị G sao cho tất cả các đỉnh đều "vui".
Cho 1 graph G=<V,E> n đỉnh. (graph thỏa mãn điều kiện có đường đi đến tất cả các đỉnh). V là tập hợp các đỉnh, E là tập hợp các cạnh của đồ thị G.
Mỗi đỉnh v có 1 trạng thái S(v)= 1 hoặc -1
Mỗi cạnh có một trọng số w cho trước (có thể <0 hoặc >=0) .
Một đỉnh v được gọi là "tốt" khi : B(v)>=0, "xấu" khi B(v)<0
B(v) được tính như sau: B(v)=S(v)*(tổng(S(u)*w(u,v))) u là tất cả các đỉnh có cạnh nối với đỉnh v.
Câu hỏi:
Tìm trạng thái cho các đỉnh của đồ thị G sao cho tất cả các đỉnh đều "vui".