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

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

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng (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Ủ ĐỀ - Trả lời: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng
#67714
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 2 tháng trước   (+0)
Chào mọi người, em có một thắc mắc cần giải đáp trong thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng. Thuật toán trong sách viết là:

Bước 1: Tạo cây DFS
Bước 2: Với mọi cặp nút (i, j) thuộc cây DFS thỏa "độ sâu" khác nhau, nếu có cạnh (i, j) không thuộc cây thì tồn tại một chu trình cơ sở.

Thắc mắc của em là tại sao phải thỏa "độ sâu" khác nhau? Em nghĩ rằng nếu đã tồn tại một cạnh (i, j) như vậy thì lẽ ra cũng là một lời giải rồi chứ? Mong mọi người giải thích giúp cho em, sẵn nếu như có thuật toán nào tốt hơn thì chia sẻ cho em với ^.^

P/s: Tiêu đề thì vô hướng mà xuống bài em lại ghi là có hướng @_@ Sr mọi người.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68348
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
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: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 1 tháng trước   (+0)
Up phát @_@ Mọi người giúp em với @_@
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68354
pirate (Admin)
khanhptnk+108
Admin
Bài viết: 868
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: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 1 tháng trước   (+0)
Sách nào vậy bạn, bạn chụp lên cho mình xem với...
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68359
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
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: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 1 tháng trước   (+0)
Dạ em không có máy chụp hình @_@ Tên sách là Chuyên đề bồi dưỡng học sinh giỏi tin học THPT - Ứng dụng lí thuyết đồ thị của tác giả Hồ Sĩ Đàm và Trần Đỗ Hùng.
Nguyên văn đoạn đó là:
"...Để tìm hệ chu trình cơ sở trên đồ thị vô hướng, có thể thực hiện thuật toán sau:
Bước 1: Bằng tìm kiếm chiều sâu (DFS) thăm các đỉnh tạo ra cây tìm kiếm DFS;
Bước 2: Với mọi cặp nút (i, j) trên cây DFS có mức (độ sâu) khác nhau, nếu có cạnh (i, j) không thuộc cây DFS thì tồn tại một chu trình thuộc hệ chu trình cơ sở. Chu trình này có thể tìm bằng cách sau: giả sử jcó mức sâu hơn thì lần ngược trên cây DFS tìm đường đi từ j về i, sau đó khép kín đường đi bằng cạnh (i, j)..."
Chủ yếu là em không hiểu tại sao cần phải xét cạnh (i, j) với độ sâu i và j khác nhau @_@ Nếu nó bằng nhau (ở hai nhánh khác nhau của DFS) thì sao?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68360
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
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: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 1 tháng trước   (+1)
Vì là cây DFS trên đồ thị vô hướng nên không tồn tại cạnh chéo (đi từ 1 nhánh sang 1 nhánh cũ).
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68362
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
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: Thắc mắc thuật toán tìm hệ chu trình cơ sở của đồ thị vô hướng 8 năm, 1 tháng trước   (+0)
@_@ vậy mà không nghĩ ra @_@ em cảm ơn ạ @_@
 
Đã 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