Đồ thị được sử dụng để mô hình hóa các bài toán bao gồm một tập các đối tượng có quan hệ với nhau theo 1 cách nào đó. | CÁC THUẬT TOÁN TRÊN ĐỒ THỊ MỤC TIÊU Một số khái niệm cơ bản Biểu diễn đồ thị Duyệt đồ thị Thành phần liên thông và thành phần liên thông mạnh Đồ thị định hướng không có chu trình Sắp xếp topo Các thuật toán đồ thị Đường đi ngắn nhất Cây bao trùm ngắn nhất MỘT SỐ KHÁI NIỆM CƠ BẢN Đồ thị được sử dụng để mô hình hóa các bài toán bao gồm một tập các đối tượng có quan hệ với nhau theo 1 cách nào đó Ví dụ Một mạng truyền thông Bản đồ đường đi giữa các thành phố Việc giải quyết các bài toán trở thành việc giải quyết một bài toán trên đồ thị Chẳng hạn Tìm đường đi ngắn nhất Tìm cây bao trùm ngắn nhất Tìm các thành phần liên thông MỘT SỐ KHÁI NIỆM CƠ BẢN Một đồ thị định hướng G = V là tập các đỉnh, E là tập các cung nối các đỉnh Mỗi cung là một cặp đỉnh có thứ tự (u,v), ký hiệu u->v Nếu có cung (u,v) ta nói đỉnh v kề với đỉnh u u v a b c d Một cung của đồ thị Đồ thị định hướng MỘT SỐ KHÁI NIỆM CƠ BẢN Một đồ thị vô hướng G = V là tập các đỉnh, E là tập các cạnh nối các đỉnh Mỗi . | CÁC THUẬT TOÁN TRÊN ĐỒ THỊ MỤC TIÊU Một số khái niệm cơ bản Biểu diễn đồ thị Duyệt đồ thị Thành phần liên thông và thành phần liên thông mạnh Đồ thị định hướng không có chu trình Sắp xếp topo Các thuật toán đồ thị Đường đi ngắn nhất Cây bao trùm ngắn nhất MỘT SỐ KHÁI NIỆM CƠ BẢN Đồ thị được sử dụng để mô hình hóa các bài toán bao gồm một tập các đối tượng có quan hệ với nhau theo 1 cách nào đó Ví dụ Một mạng truyền thông Bản đồ đường đi giữa các thành phố Việc giải quyết các bài toán trở thành việc giải quyết một bài toán trên đồ thị Chẳng hạn Tìm đường đi ngắn nhất Tìm cây bao trùm ngắn nhất Tìm các thành phần liên thông MỘT SỐ KHÁI NIỆM CƠ BẢN Một đồ thị định hướng G = V là tập các đỉnh, E là tập các cung nối các đỉnh Mỗi cung là một cặp đỉnh có thứ tự (u,v), ký hiệu u->v Nếu có cung (u,v) ta nói đỉnh v kề với đỉnh u u v a b c d Một cung của đồ thị Đồ thị định hướng MỘT SỐ KHÁI NIỆM CƠ BẢN Một đồ thị vô hướng G = V là tập các đỉnh, E là tập các cạnh nối các đỉnh Mỗi cạnh là một cặp đỉnh không có thứ tự (u,v) Nếu có cạnh (u,v) ta nói đỉnh u và v kề nhau u v a b c d e Một cạnh của đồ thị Đồ thị vô hướng MỘT SỐ KHÁI NIỆM CƠ BẢN Đồ thị có trọng số Đồ thị mà mỗi cung/cạnh của đồ thị được gắn với một số c(u,v) Số c(u,v) được gọi là trọng số (giá/độ dài) của cung/cạnh (u,v) Đường đi đơn Là một dãy hữu hạn các đỉnh (v0, v1, , vk) khác nhau, ngoại trừ có thể v0 = vk, và vi+1 là đỉnh kề của vi (i=1,2 k-1) Với đồ thị có trọng số độ dài đường đi được tính là tổng trọng số trên các cạnh trên đường đi Với đồ thị không có trọng số độ dài đường đi là k MỘT SỐ KHÁI NIỆM CƠ BẢN Đồ thị đơn Là đồ thị vô hướng có nhiều nhất một cạnh nối hai đỉnh Là đồ thị vô hướng mà hai đỉnh có thể được nối bởi nhiều hơn một cạnh Đa đồ thị MỘT SỐ KHÁI NIỆM CƠ BẢN Chu trình Là đường đi khép kín, tức là đường đi (v0, v1, , vk) có v0 = vk Ví dụ Trong đồ thị định hướng dưới đây thì (v4, v1, v2, v3) là một đường đi từ v4 đến v3, và (v4, v1, v2, v4) là một chu trình v1 v2 v4 v3 MỘT SỐ .
