Cây có hướng BULLET CÂY là đồ_thị vô hướng liên_thông và không có chu_trình BULLET RỪNG là một đồ_thị gồm p thành_phần liên_thông trong đó mỗi thành_phần liên_thông là một cây BULLET Lưu_ý cây không chứa khuyên và cạnh song_song Định_nghĩa BULLET Cho G X E là đồ_thị có hướng liên_thông G được gọi là cây có hướng nếu BULLET 1 G không có chu_trình BULLET 2 G có gốc BULLET Lưu_ý BULLET 1 Chu_trình có_thể không quan_tâm đến hướng của các cạnh BULLET 2 Cây có hướng cũng là cây BULLET 3 Cần phân_biệt cây trong LTĐT và cây trong các giáo_trình khác Các định_nghĩa tương_đương BULLET Cho đồ_thị có hướng G X E gồm N đỉnh Các điều sau đây tương_đương với nhau BULLET 1 G là một cây có hướng BULLET 2 r X thoả v X có một đường đi duy_nhất từ r đến v BULLET 3 G tựa liên_thông mạnh tối tiểu BULLET 4 G liên_thông và có đỉnh r sao cho d r 0 và d i 1 i X r BULLET 5 G không có chu_trình và có đỉnh r sao cho d r 0 và d i 1 i X r BULLET 6 G tựa liên_thông mạnh và không có chu_trình BULLET 7 G tựa liên_thông mạnh và có N 1 cạnh BULLET Lưu_ý BULLET 1 r trong các định_nghĩa trên là duy_nhất và được gọi là gốc của cây có hướng BULLET 2 Mỗi đỉnh i thuộc X có duy_nhất một đỉnh j mà cạnh liên_kết với j i hướng vào i đỉnh j được gọi đỉnh cha của I BULLET 3 Nếu đỉnh x thuộc X thoả điều_kiện d x 0 thì x được gọi là lá của cây có hướng Định_lý BULLET Cho G là đồ_thị có hướng BULLET 1 Nếu G có chứa một đồ_thị bộ_phận là cây có hướng thì G tựa liên_thông mạnh BULLET 2 Nếu G tựa liên_thông mạnh thì G có chứa một đồ_thị bộ_phận là cây có hướng BULLET Lưu_ý Nếu G tựa liên_thông mạnh T là một cây có hướng là đồ_thị bộ_phận G thì T cũng được gọi là cây có hướng tối đại của G Bài_toán đếm số_lượng cây con có hướng BULLET Cho đồ_thị có hướng G 5 đỉnh BULLET Hãy chọn một đỉnh gốc và xác_định số_lượng cây có hướng con của đồ_thị G đó BULLET Chọn đỉnh xuất_phát là 1 BULLET Bước 1 Viết ma_trận kề cho đồ_thị G BULLET Bước 2 Tạo_K_Những giá_trị nằm trên đường_chéo chính thay bằng bậc của đỉnh đó đi ra khỏi các đỉnh khác Còn tất_cả các giá_trị còn lại của nó thay bằng đối_nghịch đảo của giá_trị đó BULLET Bước 3 Do đỉnh xuất_phát của ta chọn là 1 Vậy ma_trận mới từ K Sau khi bỏ đi dòng 1 cột 1 K 1 1 BULLET Bước 4 Tính det K 1 1 BULLET Chọn dòng hay cột có nhiều số 0 nhất dòng số 4 từ ma_trận K 1 1 BULLET Nhân từng phần_tử trong dòng đó với ma_trận bỏ đi dòng và cột của phần_tử đó formula _ 1 Giải_thích biểu_thức Ở biểu_thức đầu_tiên ở dòng 4 dòng nhiều số 0 nhất Ma_trận K 1 1 BULLET Ta thấy giá_trị tại dòng 4 và cột 1 0 như_vậy ta sẽ tiến_hành bỏ đi dòng 4 và cột 1 Sinh ra một ma_trận khác BULLET Tính định_thức của ma_trận đó và nhân với 2 giá_trị 1 và giá_trị tại dòng cột đã bị xoá 0 BULLET Kết_luận Vậy với việc chọn đỉnh gốc là 1 thì ta sẽ có 4 cây con Liên_kết ngoài BULLET Sách trực_tuyến về Lý_thuyết đồ_thị BULLET Hướng_dẫn về lý_thuyết đồ_thị BULLET Bài giảng của một môn_học về các thuật_toán đồ_thị BULLET Minh_hoạ hoạt_hình về các thuật_toán đồ_thị BULLET Lần bước thuật_toán để tìm_hiểu BULLET Tóm_tắt các trang minh_hoạ thuật_toán BULLET Dữ_liệu test chuẩn cho các bài_toán đồ_thị con đầy_đủ lớn nhất Maximum_Clique tập con độc_lập lớn nhất Maximum_Independent_Set phủ đỉnh nhỏ nhất Minimum_Vertex_Cover và tô màu đỉnh Vertex_Coloring_BULLET_Sưu tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập các liên_kết về đồ_thị BULLET Các tạp_chí lý_thuyết đồ_thị BULLET Sách về lý_thuyết đồ_thị
Cây có hướng