Đồ thị

1. ĐẶT VẤN ĐỀ.

  • Nếu bạn là một shipper chắc chắn bạn sẽ quan tâm đến việc đi đường nào là ngắn nhất khi mà Hà Nội có quá nhiều con đường  và các ngã tư. Hay bạn lấy điện thoại để đặt một cuốc Grab Bike thì làm sao mà hệ thống có thế biết được bạn đang ở đâu, có những tài xế nào đang ở quanh khu vực của bạn, tài xế nào đang rảnh để đến đón bạn.
  • Để giải quyết vấn đề đó ta phải tìm cách mô hình hóa các đối tượng liên quan(các ngã tư, con đường, tài xế grab, người đặt chuyến) và biểu diễn mối quan hệ giữa chúng (độ dài đơạn đường, mức độ tắc nghẽn,khoảng cách giữa xe grab và người dùng, trạng thái của grab) để tìm lời giải.
  • Lý thuyết đồ thị đã ra đời để giải quyết bài toán đó.

2. CÁC KHÁI NIỆM CƠ BẢN

2.1 Định nghĩa đồ thị.

  • Đồ thị (graph): đồ thị là một tập các đỉnh (các đối tượng) nối với nhau bởi các cạnh (thể hiện quan hệ) giữa các đỉnh.

G = (V, E)

V(Vertices)  là tập các đỉnhE(Edges)gọi là tập các cạnh .

  • Phân loại đồ thị: theo đặc tínhsố lượng của tập các cạnh E

+ Đồ thị vô hướng: G được gọi là đồ thị vô hướng (undirected graph) nếu các cạnh trong E là không định hướng, các cặp (u, v) không tính thứ tự. (u, v)≡(v, u).

+ Đồ thị có hướng: G được gọi là đồ thị có hướng (directed graph) nếu các cạnh trong E là có định hướng, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u).

+ Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u
tới v

+ Đa đồ thị : G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối
từ u tới v

.

 

 

 

2.2 Các khái niệm cơ bản.

2.2.1 Cạnh liên thuộc, đỉnh kề, bậc

  • Xét một cạnh e ∈ E, nếu e = (u, v) thì ta nói hai đỉnh u v kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v.
  • Bậc (degree) của đỉnh v là số cạnh liên thuộc với v

2.2.2 Đường đi và chu trình

  • Một đường đi  là một dãy các đỉnh  P=〈v(0) , v(1) , …, v(p)  của các đỉnh sao cho (v(i-1) , v(i) ) ∈ E, (∀i:
    1 ≤ i ≤ p)
  • Chu trình là đường đi khép kín, điểm đầu trùng điểm cuối

2.2.3 Liên thông

  • Một đồ thị vô hướng gọi là liên thông (connected) nếu với mọi cặp đỉnh (u, v) ta có u đến được v.
  • Một đồ thị có hướng gọi là liên thông mạnh (strongly connected) nếu với mỗi cặp đỉnh (u, v), ta có u đến được v và v đến được u.
  • Một đồ thị có hướng gọi là liên thông yếu (weakly connected) nếu với mỗi cặp đỉnh (u, v), ta có u đến được v hoặc v đến được u.

3. BIỂU DIỄN ĐỒ THỊ TRONG MÁY TÍNH

3.1 Ma trận kề.( Adjacency matrix)

  • G = (V, E) là một đơn đồ thị, không mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, …, n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông Matrix cấp n
  • Matrix[i, i] = 0
  • Matrix[i, j] = 1 nếu (i, j) ∈ E, i≠j
  • Matrix[i, j] = 0 nếu (i, j) ∉ E, i≠j

  • Nhận xét : đồ thị vô hướng G, thì ma trận kề tương ứng là ma trận đối xứng (a[i, j] = a[j, i]), điều
    này không đúng với đồ thị có hướng.
  • Ưu điểm

+ Đơn giản, trực quan, dễ cài đặt trên máy tính

+ Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau hay không

  • Nhược điểm

+ Lãng phí bộ nhớ  n² ô nhớ để lưu các phần tử ma trận

+ Khi muốn tìm các đỉnh kề nó phải duyệt qua tất cả các đỉnh còn lại, gây mất thời gian.

  • Code chi tiết: https://eggclub.org/2017/04/18/bieu-dien-thi-trong-may-tinh/

3.2 Danh sách cạnh (Edge List)

  • Biểu diễn đồ thị dưới dạng danh sách cạnh bằng cách liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương ứng với một cạnh của đồ thị.

  • Ưu điểm

+ Trong trường hợp đồ thị thưa, danh sách cạnh sẽ tiết kiệm được không gian lưu trữ

+ Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì việc duyệt các cạnh dễ dàng hơn

  • Nhược điểm

+ Khi ta cần duyệt tất cả các đỉnh kề với đỉnh v của đồ thị, thì  phải duyệt tất cả các cạnh, lọc ra những cạnh  có chứa            đỉnh v

3.3 Danh sách kề (Adjacency List)

  •  Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, ta cho tương ứng với nó một danh sách các đỉnh kề với v.

 

  • Ưu điểm

+ Dễ dàng duyệt tất cả các đỉnh kề với một đỉnh v

  • Nhược điểm

+ Để kiểm tra (u, v) có phải là cạnh hay không, buộc phải việc phải duyệt toàn bộ danh sách kề của u hay danh
sách kề của v

=> Mỗi cách biểu diễn có ưu nhược điểm riêng, tùy tình huống mà ta vận dụng cho phù hợp và tối ưu.

4. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ

  • Một bài toán quan trọng trong lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó. Có thể coi đây là bài toán liệt kê mà yêu cầu của nó là không được bỏ sót hay lặp lại bất kỳ đỉnh nào.Cần phải xây dựng những thuật toán cho phép duyệt một cách hệ thống các đỉnh, những thuật toán như vậy gọi là những thuật toán tìm kiếm trên đồ thị và ở đây ta quan tâm đến hai thuật toán cơ bản nhất: thuật toán tìm kiếm theo chiều sâuthuật toán tìm kiếm theo chiều rộng cùng với một số ứng dụng của chúng.

4.1 Thuật toán tìm kiếm theo chiều sâu. (Depth First Search)

  • Nếu A kề với B đồng thời B kề với C, chứng tỏ có ta có thể đi từ A tới C. Điều đó gợi ý cho ta cách duyệt đồ thị bằng cách liên tục duyệt tới các nút kề với các nút đang xét.
  • Ta viết một thủ tục đệ quy DFS(a) mô tả việc duyệt từ đỉnh a bằng cách thăm đỉnh a và tiếp tục quá trình duyệt DFS(b) với b là một đỉnh chưa thăm kề với a. Giải thuật tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.
  • Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa

4.2 Thuật toán tìm kiếm theo chiều rộng. ( Breadth Fist Search)

  • Tư tưởng của giải thuật này là ” lên lịch trình” thăm các nút. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần S hơn sẽ được duyệt trước)

  • Ví dụ: Bắt đầu ta thăm đỉnh A. Việc thăm đỉnh A sẽ phát sinh thứ tự duyệt những đỉnhX={ B, C, D} kề với A (những đỉnh gần A nhất). Khi thăm đỉnh B sẽ lại phát sinh yêu cầu duyệt những đỉnh Y={E, F}  kề với B. Nhưng rõ ràng các đỉnh này “xa” A hơn những đỉnh X nên chúng chỉ được duyệt khi tất cả những đỉnh X đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm B sẽ là: C-> D-> E-> F-> G->…
  • Ta thấy cơ chế hàng đợi nằm trong cách duyệt này, các đỉnh sẽ đợi được thăm.
  • Giả sử ta có một danh sách chứa những đỉnh đang “chờ” thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách( ở ví dụ trên là B) và cho những đỉnh chưa “xếp hàng” kề với nó ( tương ứng E, F ở ví dụ) xếp hàng thêm vào cuối
    danh sách. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi (Queue)

Minh họa về BFS và DFS

  • Tham khảo: code chi tiết 2 thuật toán DFS và BFS

 

The following two tabs change content below.

phuongtn