Thuật toán về đồ thị

[hanoiforever]

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".

[moibelgal]

Bất cứ một bài toán tin học nào cũng cần có test ví dụ để người đọc dễ dàng nắm bắt yêu cầu đề. Thế mà bạn chỉ đưa ra đề bài dài thượt mà không có ví dụ trong hoàn cảnh cước internet ở VN là đắt đỏ nhất thế giới !

[hoangleo]

Đúng rùi đó! Đưa đề bài mà không đưa hình demo thì đọc mệt lắm, mà lại khó hình dung nữa... đề nghị có thêm hình vẽ đi!

[hanoiforever]

Các bạn thông cảm, lần đầu mình post bài nên chưa có kinh nghiệm.

Sau đây là 1 ví dụ về đồ thị G=<V,E>
A._____.B
| |
| |
C.|____|.D

Đồ thị gồm 4 đỉnh : A,B,C,D
4 cạnh: AB,BC,CD,AD
Trọng số của các cạnh như sau:
w(A,B)=5
w(B,D)=1
w(D,C)=3
w(A,C)=-2

Một trong những đáp số là:
s(A)=1
s(B)=1
s(C)=1
S(D)=1

Đáp số này thỏa mãn:
B(A)=s(A) * ( w(A,B)*s(B) + w(A,C)*s(C) )
= 1 * ( 5 * 1 + (-2) *1 )
= 3 >0 --> đỉnh A "vui"
B(B)=s(B) * ( w(A,B)*s(A) + w(B,D)*s(D) )
= 1 * ( 5 * 1 + 1 *1 )
= 6 >0 --> đỉnh B "vui"
B(C)=s(C) * ( w(A,C)*s(A) + w(C,D)*s(D) )
= 1 * ( (-2) * 1 + 3 *1 )
= 1 >0 --> đỉnh C "vui"
B(D)=s(D) * ( w(D,B)*s(B) + w(C,D)*s(C) )
= 1 * ( 1 * 1 + 3 *1 )
= 4 >0 --> đỉnh D "vui"

Tất cả các đỉnh đều "vui"