Các định nghĩa,kiểu dữ liệu,biểu diễn và bài tập về đồ thị

1. Viết biểu diễn đồ thị V.8 bằng:

- Ma trận kề.

- Danh sách các đỉnh kề.

2. Duyệt đồ thị hình V.8 (xét các đỉnh theo thứ tự a,b,c...)

- Theo chiều rộng bắt đầu từ a.

- Theo chiều sâu bắt đầu từ f

3. Áp dụng giải thuật Dijkstra cho đồ thị hình V.8, với đỉnh nguồn là

4. Viết biểu diễn đồ thị V.9 bằng:

Ma trận kề.

Danh sách các đỉnh kề.

5. Duyệt đồ thị hình V.9 (xét các đỉnh theo thứ tự A,B,C...)

Theo chiều rộng bắt đầu từ A.

Theo chiều sâu bắt đầu từ B.

6. Áp dụng giải thuật Dijkstra cho đồ thị hình V.9, với đỉnh nguồn là A.

7. Tìm cây bao trùm tối thiểu của đồ thị hình V.9 bằng

Giải thuật Prim.

Giải thuật Kruskal.

8. Cài đặt đồ thị có hướng bằng ma trận kề rồi viết các giải thuật:

Duyệt theo chiều rộng.

Duyệt theo chiều sâu.

Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra).

Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd).

9. Cài đặt đồ thị có hướng bằng danh sách các đỉnh kề rồi viết các giải thuật:

Duyệt theo chiều rộng.

Duyệt theo chiều sâu.

10. Cài đặt đồ thị vô hướng bằng ma trận kề rồi viết các giải thuật:

Duyệt theo chiều rộng.

Duyệt theo chiều sâu.

Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra).

Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd).

Tìm cây bao trùm tối thiểu (Prim, Kruskal).

Cài đặt thuật toán Greedy cho bài toán tô màu đồ thị (Gợi ý: xem giải thuật trong chương 1)

11. Cài đặt đồ thị vô hướng bằng danh sách các đỉnh kề rồi viết các giải thuật:

Duyệt theo chiều rộng.

Duyệt theo chiều sâu.

12. Hãy viết một chương trình, trong đó, cài đặt đồ thị vô hướng bằng cấu trúc ma trận kề rồi viết các thủ tục/hàm sau:

Nhập toạ độ n đỉnh của đồ thị.

Giả sử đồ thị là đầy đủ, tức là hai đỉnh bất kỳ đều có cạnh nối, và giả sử giá của mỗi cạnh là độ dài của đoạn thẳng nối hai cạnh. Hãy tìm:

Đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra).

Đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd).

Cây bao trùm tối thiểu (Prim, Kruskal).

Thể hiện đồ thị lên màn hình đồ hoạ, các cạnh thuộc cây bao trùm tối thiểu được vẽ bằng một màu khác với các cạnh khác.

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’.

Các phép toán được định nghĩa trên đồ thị là rất đơn giản như là:

• Đọc nhãn của đỉnh.
• Đọc nhãn của cạnh.
• Thêm một đỉnh vào đồ thị.
• Thêm một cạnh vào đồ thị.
• Xoá một đỉnh.
• Xoá một cạnh.
• Lần theo (navigate) các cung trên đồ thị để đi từ đỉnh này sang đỉnh khác.

Thông thường trong các giải thuật trên đồ thị, ta thường phải thực hiện một thao tác nào đó với tất cả các đỉnh kề của một đỉnh, tức là một đoạn giải thuật có dạng sau:

For (mỗi đỉnh w kề với v)

{ thao tác nào đó trên w }

Để cài đặt các giải thuật như vậy ta cần bổ sung thêm khái niệm về chỉ số của các đỉnh kề với v. Hơn nữa ta cần định nghĩa thêm các phép toán sau đây:

• FIRST(v) trả về chỉ số của đỉnh đầu tiên kề với v. Nếu không có đỉnh nào kề với v thì null được trả về. Giá trị null được chọn tuỳ theo cấu trúc dữ liệu cài đặt đồ thị.
• NEXT(v,i) trả về chỉ số của đỉnh nằm sau đỉnh có chỉ số i và kề với v. Nếu không có đỉnh nào kề với v theo sau đỉnh có chỉ số i thì null được trả về.
• VERTEX(i) trả về đỉnh có chỉ số i. Có thể xem VERTEX(v,i) như là một hàm để định vị đỉnh thứ i để thức hiện một thao tác nào đó trên đỉnh này.

Một số cấu trúc dữ liệu có thể dùng để biểu diễn đồ thị. Việc chọn cấu trúc dữ liệu nào là tuỳ thuộc vào các phép toán trên các cung và đỉnh của đồ thị. Hai cấu trúc thường gặp là biểu diễn đồ thị bằng ma trận kề (adjacency matrix) và biểu diễn đồ thị bằng danh sách các đỉnh kề (adjacency list).

Biểu diễn đồ thị bằng ma trận kề

Ta dùng một mảng hai chiều, chẳng hạn mảng A, kiểu boolean để biểu diễn các đỉnh kề. Nếu đồ thị có n đỉnh thì ta dùng mảng A có kích thước nxn. Giả sử các đỉnh được đánh số 1..n thì A[i,j] = true, nếu có đỉnh nối giữa đỉnh thứ i và đỉnh thứ j, ngược lại thì A[i,j] = false. Rõ ràng, nếu G là đồ thị vô hướng thì ma trận kề sẽ là ma trận đối xứng. Chẳng hạn đồ thị V.1b có biểu diễn ma trận kề như sau:

Ta cũng có thể biểu diễn true là 1 còn false là 0. Với cách biểu diễn này thì đồ thị hình V.1a có biểu diễn ma trận kề như sau:

Với cách biểu diễn đồ thị bằng ma trận kề như trên chúng ta có thể định nghĩa chỉ số của đỉnh là số nguyên chỉ đỉnh đó (theo cách đánh số các đỉnh) và ta cài đặt các phép toán FIRST, NEXT và VERTEX như sau:

const null=0;

int A[n,n]; //mảng biểu diễn ma trận kề

int FIRST(int v) //trả ra chỉ số [1..n] của đỉnh đầu tiên kề với v ∈ 1..n

{

int i;

for (i=1; i<=n; i++)

if (a[v-1,i-1] == 1)

return (i); //trả ra chỉ số đỉnh của đồ thị

return (null);

}

int NEXT(int v; int i) //trả ra đỉnh [1..n] sau đỉnh i mà kề với v; i, v ∈ 1..n

{

int j;

for (j=i+1; j<=n; j++)

if (a[v-1,j-1] == 1)

return(j)

return(null);

}

Còn VERTEX(i) chỉ đơn giản là trả ra chính i.

Vòng lặp trên các đỉnh kề với v có thể cài đặt như sau

i=FIRST(v);

while (i<>null)

{ w = VERTEX(i);

//thao tác trên w

i =NEXT(v,i);

}

Trên đồ thị có nhãn thì ma trận kề có thể dùng để lưu trữ nhãn của các cung chẳng hạn cung giữa i và j có nhãn a thì A[i,j]=a. Ví dụ ma trận kề của đồ thị hình V.2 là:

Ở đây các cặp đỉnh không có cạnh nối thì ta để trống, nhưng trong các ứng dụng ta có thể phải gán cho nó một giá trị đặc biệt nào đó để phân biệt với các giá trị có nghĩa khác. Chẳng hạn như trong bài toán tìm đường đi ngắn nhất, các giá trị số nguyên biểu diễn cho khoảng cách giữa hai thành phố thì các cặp thành phố không có cạnh nối ta gán cho nó khoảng cách bằng µ, còn khoảng cách từ một đỉnh đến chính nó là 0.

Cách biểu diễn đồ thị bằng ma trận kề cho phép kiểm tra một cách trực tiếp hai đỉnh nào đó có kề nhau không. Nhưng nó phải mất thời gian duyệt qua toàn bộ mảng để xác định tất cả các cạnh trên đồ thị. Thời gian này độc lập với số cạnh và số đỉnh của đồ thị. Ngay cả số cạnh của đồ thị rất nhỏ chúng ta cũng phải cần một mảng nxn phần tử để lưu trữ. Do vậy, nếu ta cần làm việc thường xuyên với các cạnh của đồ thị thì ta có thể phải dùng cách biểu diễn khác cho thích hợp hơn.