Tag Archives: graph

1.    Thuật toán Dijkstra Cho G=(X,E) là một đồ thị có trọng không âm gồm n đỉnh. Thuật toán Dijkstra được dùng để tìm đường đi ngắn nhất từ đỉnh i đến j cho trước. Gọi L là ma trận trọng lượng (với qui ước Lhk = +∞ nếu không …

1.     Lý thuyết Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần trong đó đỉnh đầu và đỉnh cuối trùng nhau (đồ thị có thể có các đỉnh cô lập). Tương tự với đường đi Euler, ngoại trừ điểm …

1.     Thuật toán Prim Cho G=(X,E) là một đồ thị liên thông có trọng gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung NN của G. [crayon-67ad133e93bc6111503785/] Chú ý: trong các thuật toán tìm khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh …

1.1.    Tính liên thông Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không liên thông. Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị …

1.     Tóm tắt một số khái niệm Đồ thị là một thể hiện bao gồm một tập hợp các đối tượng và giữa chúng có thể có các liên kết. Trong toán học người ta gọi các đối tượng là các đỉnh và các liên kết là các cạnh. Đồ …