Luận văn Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị

Tóm tắt Luận văn Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị: ... song song ta cịn phải chú ý đến kiến trúc của hệ thống tính tốn. Khi chuyển một thuật tốn tuần tự sang thuật tốn song song hoặc chuyển một thuật tốn song song thích hợp với kiến trúc đang cĩ. Cần xác định được yêu cầu sau: - Kiến trúc tính tốn nào sẽ phù hợp với bài tốn? - Những bài...ớng G khơng liên thơng, nĩ sẽ được phân thành các đồ thị con độc lập nhau và chúng đều liên thơng. Mỗi đồ thị con như vậy được gọi là một thành phần liên thơng của G. Định nghĩa 2.10. Cho G = (V,E) là đồ thị cĩ hướng. - G được gọi là liên thơng mạnh nếu luơn tìm được đường đi giữa hai đỉnh... hiện lại bước 2. CHƯƠNG 3 XÂY DỰNG THUẬT TỐN SONG SONG CHO MỘT SỐ BÀI TỐN VỀ ĐỒ THỊ 3.1 Bài tốn tìm cây bao trùm nhỏ nhất 3.1.1 Bài tốn: Cho đồ thị vơ hướng cĩ trọng số G =(V, E, w). Hãy tìm cây bao trùm T của G sao cho tổng trọng số của các cạnh của T đạt giá trị nhỏ nhất. 3.1....