TAILIEUCHUNG - GIẢI TÍCH MẠNG part 4

Vết cắt là tập hợp của các nhánh, nếu bỏ đi hoặc chia graph liên thông thành hai graph con liên thông. Nhóm vết cắt có thể chọn độc lập duy nhất nếu mỗi vết cắt chỉ bao gồm một nhánh cây. Vết cắt độc lập như vậy gọi là vết cắt cơ bản. Số vết cắt cơ bản đúng bằng số nhánh cây. Sự định hướng của vết cắt cơ bản được chọn giống như hướng của nhánh cây. | GIẢI TÍCH MẠNG hướng của vòng cơ bản được chọn giống như chiều của nhánh bù cây. Vòng cơ bản của graph cho trong hình được trình bày trong hình . Hình Vòng cơ bản định hướng theo graph liên thông Vết cắt là tập hợp của các nhánh nếu bỏ đi hoặc chia graph liên thông thành hai graph con liên thông. Nhóm vết cắt có thể chọn độc lập duy nhất nếu mỗi vết cắt chỉ bao gồm một nhánh cây. Vết cắt độc lập như vậy gọi là vết cắt cơ bản. Số vết cắt cơ bản đúng bằng số nhánh cây. Sự định hướng của vết cắt cơ bản được chọn giống như hướng của nhánh cây. Vết cắt cơ bản của graph cho trong hình được trình bày trong hình Hình vết cắt cơ bản định hướng theo graph liên thông . MA TRẬN THÊM VÀO. . Ma trậ n thêm vào nhánh - nút Â. Sự liên hệ giữa nhánh và nút trong graph liên thông trình bày bởi ma trận thêm vào nhánh nút. Các thành phần của ma trận được trình bày như sau aịj 1 Nếu nhánh thứ i và nút thứ j có chiều hướng từ nhánh i vào nút j aịj -1 Nếu nhánh thứ i và nút thứ j có chiều hướng từ nhánh i ra khỏi nút j aịj 0 Nếu nhánh thứ i và nút thứ j không có mối liên hệ với nhau. Kích thước của ma trận là e x n với e là số nhánh và n là số nút của graph. Ma trận thêm vào nhánh nút cho trong graph hình trình bày như trên. Với Trang 44 GIẢI TÍCH MẠNG Ẻ ai 0 i 1 2 .e J 0 n e 4 2 3 5 6 7 2 3 0 1 Đ 4 1 1 1 1 -1 -1 1 1 1 1 -1 -1 1 -1 1 Các cột của ma trận  là phụ thuộc tuyến tính. Vì vậy hạng của  n. . Ma trận thêm vào nút A. Các nút của graph liên thông có thể chọn làm nút qui chiếu. Nút qui chiếu có thể thay đổi nó được xem như một nút trong graph có thể cân nhắc khi ấn định cụ thể một nút nào đó làm nút qui chiếu. Ma trận thu được từ ma trận  bỏ đi cột tương ứng với nút chọn làm nút qui chiếu là ma trận nhánh - nút A nó sẽ được gọi là ma trận nút. Kích thước của ma trận là e x n-1 và hạng là n-1 b. Với b là số nhánh cây của graph. Chọn nút 0 làm nút qui chiếu thể hiện trên graph trong hình .

TÀI LIỆU MỚI ĐĂNG
10    178    3    24-12-2024
8    164    3    24-12-2024
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.