TAILIEUCHUNG - Algorithms Programming - Thuật Toán Số phần 8

Các thuật toán trên đồ thị Nếu mỗi cạnh của G đều nằm trên một chu trình đơn, ta sẽ chứng minh rằng: phép định chiều DFS sẽ tạo ra đồ thị G' liên thông mạnh. | Các thuật toán trên đồ thị 211 Nếu mỗi cạnh của G đều nằm trên một chu trình đơn ta sẽ chứng minh rằng phép định chiều DFS sẽ tạo ra đồ thị G liên thông mạnh. Trước hết ta chứng minh rằng nếu u v là cạnh của G thì sẽ có một đường đi từ u tới v trong G . Thật vậy vì u v nằm trong một chu trình đơn mà mọi cạnh của một chu trình đơn đều phải thuộc một chu trình cơ sở nào đó nên sẽ có một chu trình cơ sở chứa cả u và v. Chu trình cơ sở qua phép định chiều DFS vẫn là chu trình trong G nên đi theo các cạnh định hướng của chu trình đó ta có thể đi từ u tới v và ngược lại. Nếu u và v là 2 đỉnh bất kỳ của G thì do G liên thông tồn tại một đường đi u x0 x1 . xn v . Vì xi xi 1 là cạnh của G nên trong G từ xi có thể đến được xi 1. Suy ra từ u cũng có thể đến được v bằng các cạnh định hướng của G . . Cài đặt Với những kết quả đã chứng minh trên ta còn suy ra được Nếu đồ thị liên thông và mỗi cạnh của nó nằm trên ít nhất một chu trình đơn thì phép định chiều DFS sẽ cho một đồ thị liên thông mạnh. Còn nếu không thì phép định chiều DFS sẽ cho một đồ thị định hướng có ít thành phần liên thông mạnh nhất một cạnh không nằm trên một chu trình đơn nào cầu của đồ thị ban đầu sẽ được định hướng thành cung nối giữa hai thành phần liên thông mạnh. Ta sẽ cài đặt một thuật toán với một đồ thị vô hướng liệt kê các cầu và định chiều các cạnh để được một đồ thị mới có ít thành phần liên thông mạnh nhất Đánh số các đỉnh theo thứ tự thăm DFS gọi Numbering u là số thứ tự của đỉnh u theo cách đánh số đó. Trong quá trình tìm kiếm DFS duyệt qua cạnh nào định chiều luôn cạnh đó. Định nghĩa thêm Low u là giá trị Numbering nhỏ nhất của những đỉnh đến được từ nhánh DFS gốc u bằng một cung ngược. Tức là nếu nhánh DFS gốc u có nhiều cung ngược hướng lên trên phía gốc cây thì ta ghi nhận lại cung ngược hướng lên cao nhất. Nếu nhánh DFS gốc u không chứa cung ngược thì ta cho Low u O . Cụ thể cách cực tiểu hoá Low u như sau Trong thủ tục Visit u trước hết ta đánh số thứ tự thăm cho đỉnh u Numbering u và

• Kỹ thuật lập trình
• Tài liệu IT
• Tài liệu lập trình
• Thuật toán
• Toán logic
• Giải thuật
• Hàm số
• thủ thuật lập trình
• tài chính
• ngân hàng
• kế toán
• quản lý tài chính
• tài liệu tài chính
• tài liệu về ngân hàng
• Tài liệu kinh doanh
• hướng dẫn hạch toán
• Hạch toán doanh nghiệp
• Tài sản doanh nghiệp