Tô màu

[Rikku]

Cho 1 đồ thị không quá 200 đỉnh, tìm cách tô màu đồ thị sao cho với 2 đỉnh bất kì mà có cung nối thì phải có màu khác nhau...

Có pác nào biết thuật giải tốt nhất hiện giờ cho bài này không??

[MrPaint]

Cho mình hỏi: "2 đỉnh bất kì mà có cung nối thì phải có màu khác nhau..." thế nghĩa là sao? Bởi giữa 2 điểm thì mới có một cung nối, hơn nữa, trong Pascal làm sao có đủ màu để mà khác nhau????
Mong bạn giải thích đề kĩ hơn

[Rikku]

Nói thêm cho rõ nhá, đây là không phải là đồ thị phẳng, nên đừng nghĩ răng tối đa là 4 màu.
To MrPaint: Pó tay.

[vinhpv]

i=1.

1. xap xep cac dinh chua duoc to mau theo so bac giam dan m(x1) > m(x2) > ... > m(xn)
2. lay x1 va to mau i
3. tat ca những đỉnh không kề với x1 cũng tô màu i
4. i++
5. quay lai buoc 1

ok>?

[MrPaint]

Khi viết bằng Pascal thì chỉ tô được 16 màu là max gòi, làm sao mà tô nhiều hơn được. Không biết là ai bó tay ai đâu
Còn nữa, nếu bạn chỉ muốn "tô màu" một điểm thôi thì không gọi là "tô màu". (Nếu mình hiểu sai ý bạn thì xin đính chính ngay nhé )
Rốt cục vẫn chả hiều ra làm sao hết...

To Vinhpv: cách làm của bạn phức tạp quá, rất chậm: ví dụ với điểm thứ 200 thì theo cách của bạn sẽ bị đè lên 199 lần (kinh khủng!) mà cũng chưa chắc 2 điểm kề nhau được tô khác nhau!

[vinhpv]

với thuật toán trên 200 đỉnh là quá bình thường

[MrPaint]

To vinhpv: Cãi cùn wá, làm như thế làm sao giải được các bài toán lớn?
Nên sửa là:

for i:=1 to <số đỉnh> do
begin
a:=GetColor;
repeat
b:=random(GetMaxColor-1)+1;
until b<>a;
PutPixel(x[i],x[i],b);
end;

==> 100% 2 đỉnh gần nhau sẽ có màu khác nhau

To vinhpv: có phải là dân VB không mà lại xài i++ thế?

[vinhpv]

thuật toán của bạn không chạy đuợc là dúng roi chạy sẽ rất chậm mà kết quả không chính xác.

bạn hãy xem lại thuật toán trên đi(vinhpv) xem nào (đảm bảo nhanh hơn, chính xác 100% là cái chắc)

chú ý sort dùng các phương pháp sáp xếp nhanh.

?? VB co gi hay chứ
mô tả thuật toán thì dùng cái gì mà chả được

ok???

[Rikku]

Xin lỗi mọi người, tui gõ thiếu

Cho 1 đồ thị không quá 200 đỉnh, tìm cách tô màu đồ thị sao cho với 2 đỉnh bất kì mà có cung nối thì phải có màu khác nhau..., sao cho số màu là ÍT NHẤT

[toicnt44dh]

bao nay de qua cac bac oi