Thuật toán đồ thị
Biểu đồ là một ký hiệu trừu tượng được sử dụng để biểu diễn kết nối giữa các cặp đối tượng. Một biểu đồ bao gồm -
Vertices- Các đối tượng liên kết với nhau trong một đồ thị được gọi là các đỉnh. Dọc còn được gọi lànodes.
Edges - Cạnh là liên kết nối các đỉnh.
Có hai loại đồ thị -
Directed graph - Trong đồ thị có hướng, các cạnh có hướng, tức là các cạnh đi từ đỉnh này sang đỉnh khác.
Undirected graph - Trong đồ thị vô hướng, các cạnh không có hướng.
Tô màu đồ thị
Tô màu đồ thị là phương pháp gán màu cho các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào có cùng màu. Một số vấn đề về tô màu đồ thị là -
Vertex coloring - Cách tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau cùng màu.
Edge Coloring - Là phương pháp gán một màu cho mỗi cạnh sao cho không có hai cạnh liền nhau nào có cùng màu.
Face coloring - Nó chỉ định màu cho từng mặt hoặc từng vùng của đồ thị phẳng sao cho không có hai mặt có chung đường biên nào có cùng màu.
Số màu
Số màu là số màu tối thiểu cần thiết để tô màu một biểu đồ. Ví dụ, số màu của đồ thị sau là 3.
Khái niệm tô màu đồ thị được áp dụng trong việc chuẩn bị thời gian biểu, ấn định tần số vô tuyến điện thoại di động, Suduku, phân bổ thanh ghi và tô màu bản đồ.
Các bước để tô màu đồ thị
Đặt giá trị ban đầu của mỗi bộ xử lý trong mảng n chiều thành 1.
Bây giờ để gán một màu cụ thể cho một đỉnh, hãy xác định xem màu đó đã được gán cho các đỉnh liền kề hay chưa.
Nếu một bộ xử lý phát hiện cùng một màu trong các đỉnh liền kề, nó sẽ đặt giá trị của nó trong mảng thành 0.
Sau khi thực hiện n 2 so sánh, nếu bất kỳ phần tử nào của mảng là 1 thì đó là màu hợp lệ.
Mã giả để tô màu đồ thị
begin
create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
status[i0,..in-1] = 1
for j varies from 0 to n-1 do
begin
for k varies from 0 to n-1 do
begin
if aj,k=1 and ij=ikthen
status[i0,..in-1] =0
end
end
ok = ΣStatus
if ok > 0, then display valid coloring exists
else
display invalid coloring
endCây kéo dài tối thiểu
Cây khung có tổng trọng lượng (hoặc chiều dài) của tất cả các cạnh của nó nhỏ hơn tất cả các cây khung có thể có khác của đồ thị G được gọi là minimal spanning tree hoặc là minimum cost spanningcây. Hình sau cho thấy một đồ thị liên thông có trọng số.
Một số cây khung có thể có của biểu đồ trên được hiển thị bên dưới:
Trong số tất cả các cây khung ở trên, hình (d) là cây khung tối thiểu. Khái niệm cây bao trùm chi phí tối thiểu được áp dụng trong bài toán nhân viên bán hàng đi du lịch, thiết kế mạch điện tử, thiết kế mạng hiệu quả và thiết kế thuật toán định tuyến hiệu quả.
Để triển khai cây bao trùm chi phí tối thiểu, hai phương pháp sau được sử dụng:
- Thuật toán Prim
- Thuật toán Kruskal
Thuật toán Prim
Thuật toán của Prim là một thuật toán tham lam, giúp chúng ta tìm cây bao trùm tối thiểu cho một đồ thị vô hướng có trọng số. Nó chọn một đỉnh đầu tiên và tìm một cạnh có trọng số thấp nhất trên đỉnh đó.
Các bước của thuật toán Prim
Chọn một đỉnh bất kỳ, ví dụ v 1 của Đồ thị G.
Chọn một cạnh, giả sử e 1 của G sao cho e 1 = v 1 v 2 và v 1 ≠ v 2 và e 1 có trọng số nhỏ nhất trong số các cạnh nằm trên v 1 trong đồ thị G.
Bây giờ, theo bước 2, chọn sự cố cạnh trọng số nhỏ nhất trên v 2 .
Tiếp tục điều này cho đến khi n – 1 cạnh được chọn. Đâyn là số đỉnh.
Cây bao trùm tối thiểu là -
Thuật toán Kruskal
Thuật toán của Kruskal là một thuật toán tham lam, giúp chúng tôi tìm cây bao trùm tối thiểu cho một đồ thị có trọng số được kết nối, thêm các cung chi phí ngày càng tăng ở mỗi bước. Nó là một thuật toán cây bao trùm tối thiểu nhằm tìm ra một cạnh có trọng lượng nhỏ nhất có thể để kết nối hai cây bất kỳ trong rừng.
Các bước của thuật toán Kruskal
Chọn một cạnh có trọng lượng tối thiểu; nói e 1 của Đồ thị G và e 1 không phải là một vòng lặp.
Chọn cạnh có trọng số nhỏ nhất tiếp theo được kết nối với e 1 .
Tiếp tục điều này cho đến khi n – 1 cạnh được chọn. Đâyn là số đỉnh.
Cây bao trùm tối thiểu của biểu đồ trên là -
Thuật toán đường dẫn ngắn nhất
Thuật toán Đường đi ngắn nhất là một phương pháp tìm đường đi có chi phí thấp nhất từ nút nguồn (S) đến nút đích (D). Ở đây, chúng ta sẽ thảo luận về thuật toán Moore, còn được gọi là Thuật toán tìm kiếm đầu tiên theo chiều rộng.
Thuật toán Moore
Gắn nhãn đỉnh nguồn, S và gắn nhãn nó i và thiết lập i=0.
Tìm tất cả các đỉnh không được gắn nhãn liền kề với đỉnh có nhãn i. Nếu không có đỉnh nào được nối với đỉnh, S, thì đỉnh, D, không được nối với S. Nếu có đỉnh nào được nối với S, hãy gắn nhãn chúngi+1.
Nếu D được gắn nhãn thì chuyển sang bước 4, còn lại chuyển sang bước 2 để tăng i = i + 1.
Dừng lại sau khi tìm được đoạn đường ngắn nhất.