Giải thuật và lập trình - C: I. Các định nghĩa


Đăng ký nhận thông báo về những video mới nhất

Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cung, ký hiệu G=(V,E). Các đỉnh còn được gọi là nút (node) hay điểm (point). Các cung nối giữa hai đỉnh, hai đỉnh này có thể trùng nhau. Hai đỉnh có cung nối nhau gọi là hai đỉnh kề (adjacency). Một cung nối giữa hai đỉnh v, w có thể coi như là một cặp điểm (v,w). Nếu cặp này có thứ tự thì ta có cung có thứ tự, ngược lại thì cung không có thứ tự. Nếu các cung trong đồ thị G có thứ tự thì G gọi là đồ thị có hướng (directed graph). Nếu các cung trong đồ thị G không có thứ tự thì đồ thị G là đồ thị vô hướng (undirected graph). Trong các phần sau này ta dùng từ đồ thị (graph) để nói đến đồ thị nói chung, khi nào cần phân biệt rõ ta sẽ dùng đồ thị có hướng, đồ thị vô hướng. Hình V.1a cho ta một ví dụ về đồ thị có hướng, hình V.1b cho ví dụ về đồ thị vô hướng. Trong các đồ thị này thì các vòng tròn được đánh số biểu diễn các đỉnh, còn các cung được biểu diễn bằng các đoạn thẳng có hướng (trong V.1a) hoặc không có hướng (trong V.1b).

Thông thường trong một đồ thị, các đỉnh biểu diễn cho các đối tượng còn các cung biểu diễn mối quan hệ (relationship) giữa các đối tượng đó. Chẳng hạn các đỉnh có thể biểu diễn cho các thành phố còn các cung biểu diễn cho đường giao thông nối giữa hai thành phố.

Một đường đi (path) trên đồ thị là một dãy tuần tự các đỉnh v1, v2,..., vn sao cho (vi,vi+1) là một cung trên đồ thị (i=1,...,n-1). Đường đi này là đường đi từ v1 đến vn và đi qua các đỉnh v2,...,vn-1. Đỉnh v1 còn gọi là đỉnh đầu, vn gọi là đỉnh cuối. Độ dài của đường đi này bằng (n-1). Trường hợp đặc biệt dãy chỉ có một đỉnh v thì ta coi đó là đường đi từ v đến chính nó có độ dài bằng không. Ví dụ dãy 1,2,4 trong đồ thị V.1a là một đường đi từ đỉnh 1 đến đỉnh 4, đường đi này có độ dài là hai.

Đường đi gọi là đơn (simple) nếu mọi đỉnh trên đường đi đều khác nhau, ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng nhau. Một đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là một chu trình (cycle). Một chu trình đơn là một đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau và có độ dài ít nhất là 1. Ví dụ trong hình V.1a thì 3, 2, 4, 3 tạo thành một chu trình có độ dài 3. Trong hình V.1b thì 1,3,4,2,1 là một chu trình có độ dài 4.

Trong nhiều ứng dụng ta thường kết hợp các giá trị (value) hay nhãn (label) với các đỉnh và/hoặc các cạnh, lúc này ta nói đồ thị có nhãn. Nhãn kết hợp với các đỉnh và/hoặc cạnh có thể biểu diễn tên, giá, khoảng cách,... Nói chung nhãn có thể có kiểu tuỳ ý. Hình V.2 cho ta ví dụ về một đồ thị có nhãn. Ở đây nhãn là các giá trị số nguyên biểu diễn cho giá cước vận chuyển một tấn hàng giữa các thành phố 1, 2, 3, 4 chẳng hạn.

Đồ thị con của một đồ thị G=(V,E) là một đồ thị G'=(V',E') trong đó:

  • V’ ⸦ V và
  • E’ gồm tất cả các cạnh (v,w) ∈ E sao cho v,w ∈ V’.

Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!