Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Xem đầy đủ

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63
Xem đầy đủ

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Forum Học tập Toán học
Bài toán Tô màu cây (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Bài toán Tô màu cây
#68708
minhduclqdvt (Thành viên)
theboywholived+2
Đã biết code đệ quy
Bài viết: 10
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Bài toán Tô màu cây 8 năm, 1 tháng trước   (+0)
Bài toán: Cho một cây, tìm cách gán cho mỗi đỉnh một nhãn nguyên dương sao cho:
- Hai nút có cạnh nối được gán nhãn khác nhau
- Tổng giá trị của tất cả các nhãn là nhỏ nhất

link: http://vn.spoj.com/problems/CTREE/

Em đọc trong một số tài liệu có ghi:
" Dễ dàng chứng minh được có thể dùng KHÔNG QUÁ 3 MÀU để tô màu cây "
Các bác giúp em chứng minh điều này nhé
__________________
Thanks a lot !!!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68839
luv_luxury (Thành viên)
luv_luxury-
Biết code binary-indexed tree
Bài viết: 22
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán Tô màu cây 8 năm, 1 tháng trước   (+0)
Mình thấy điều đó giống tham lam ấy. Thấy nó đúng đúng chứ cũng chẳng phải chứng minh
Giả sử một nút i có cha là u thì để tô 2 nút u và i 2 màu khác nhau.
Nút i có k con, để tô màu nút con thì chỉ cần tô màu sao cho khác i. Nên chỉ cần 3 màu thôi: một màu cho cha i, một màu cho i và một màu cho con i
 
Đã lưu IP Đã lưu IP  
 
Cộng mình cho mình hết bị trừ lào
  Đã khóa chức năng gửi bài.
#68937
minhduclqdvt (Thành viên)
theboywholived+2
Đã biết code đệ quy
Bài viết: 10
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán Tô màu cây 8 năm, 1 tháng trước   (+0)
nếu vậy tại sao không tô màu các con của i giống màu của u luôn (chỉ cần 2 màu) ????
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68940
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán Tô màu cây 8 năm, 1 tháng trước   (+0)
Trong trường hợp dưới đây nếu bạn chỉ dùng 2 màu để tô thì tổng nhỏ nhất là bao nhiêu?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68959
minhduclqdvt (Thành viên)
theboywholived+2
Đã biết code đệ quy
Bài viết: 10
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán Tô màu cây 8 năm, 1 tháng trước   (+0)
Trường hợp này tất nhiên là phải dùng phải dùng 3 màu rồi.
Mình đang thắc mắc là ko biết có trường hợp nào phải dùng đến 4 màu ko
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS