Cấu trúc dữ liệu và giải thuật - Chương 6

ĐỒ THỊI. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM Một đồ thị G(V,E) là 1 tập bao gồm 2 tập con : - Tập hữu hạn V, không rỗng, của các phân tử mà ta gọi là đỉnh (vertices). - Tập hữu hạn E, của các cặp đỉnh, mà mỗi cặp ta gọi là 1 cung (edge). Bản đồ đường bộ giữa các thành phố trong 1 khu vực là 1 đồ thị với thành phố là đỉnh, đường lối trong thời gian đó là cung. Mạng máy tính của 1 công ty, sơ đồ mạch điện của 1...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 6Chương VI. ĐỒ THỊI. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM Mộ t đồ thị G(V,E) là 1 tập bao gồm 2 tập con : - Tập hữu h ạn V, không rỗng, của các phân tử mà ta gọi là đỉnh (vertices). - Tập h ữu hạn E, của các cặp đỉnh, mà mỗi cặp ta gọi là 1 cung (edge). Bản đồ đường bộ giữa các thành phố trong 1 khu vự c là 1 đồ thị với thànhphố là đ ỉnh, đường lối trong thời gian đó là cung. Mạng máy tính của 1 công ty, sơ đồ mạch điện của 1 khu chung cư, cấu trúcphân tử của các hợp chất hữu cơ v.v…tất cả đ ều có dạng đồ thị. Nếu u và v là 2 đỉnh trên đồ th ị mà thứ tự được phân biệt trong từng cặp,nghĩa vụ là (u, v) khác với (v, u) thì đồ thị được gọ i là đồ thị có hướng (directedgraph). Lúc đó (u, v)được gọi là cung từ u tới v còn (v, u) được gọ i là cung từ v tớiu. Nếu thứ tự 2 đỉnh củ a 1 cung không được coi trọng thì đồ thị được gọi là đồth ị vô h ướng (undirected grap) và (u, v)được gọ i là cung giữa u và v hoặc cunggiữa v và u. Trên hình vẽ cung có hướng được biểu diễn bằng mũ i tên còn cung vôhướng thì bằng 1 đoạn thẳng. Hình 6.1 minh ho ạ 1 số đồ thị :G1, G2 là các đồ th ị có hướng ; G3, G4 là cácđồ thị vô h ướng. Ở đây ta quy ước : các đỉnh được đánh số từ 1 tới n (nếu đồ th ịcó n đỉnh). Nếu trên đồ thị G (V,E) có 1 cung đi từ u tới v thì ta nói : v là đỉnh lân cậncủa u hay là đ ỉnh kề (adjacent) của u. Tất nhiên với đồ thị vô h ướng, khi có cunggiữa 2 đỉnh, thì ta nói đ ỉnh này là lân cận của đỉnh kia. 1 1 2 2 3 3 4 G1 a) Đồ thị có hướng 1 1 2 3 2 3 4 5 G4 4 5 G3 b ) Đồ thị vô hướng Hình 6.1 Mộ t đường đi (path) từ đ ỉnh u tới đỉnh v là 1 dãy các đỉnh : x0, x1,…,xn-1, xn (n là số nguyên dương), trong đó : u = x0, v = xn và (xi, xi+1)với i = 0, 1, 2, …, n-1 là các cung thuộc E , u gọi là đỉnh đầu , v gọi là đỉnh cuối.Số lượng các cung trên 1 đường đi được gọ i là độ dài của đ ường đ i (path length). Mộ t đường đ i đơn (simple path) là đường đ i mà mọi đ ỉnh trên đó, trừ đ ỉnhđầu và đỉnh cuối đều khác nhau. Trường h ợp đỉnh đầu trùng với đỉnh cuố i ta gọi là chu trình (cycle). Ví dụ : với đồ th ị G2 (hình 6.1),ta có : Đường đ i 1, 2, 3, 4 là đường đi đ ơn có độ dài bằng 3. Đường đ i 1, 4, 2, 3, 1 là 1 chu trình có độ dài bằng 4. Mộ t đồ thị gọi là liên thông(cennected) nếu luôn có đường đi giữa 2 đ ỉnh bấtkì của nó. Đố i với đồ thị có hướng thì trường hợp đó người ta gọ i là liên thôngmạnh (strengly connected). Ví dụ : trong hình 6.1 : - Các đồ th ị G2 và G3 là liên thông. - Các đồ th ị G1 và G4 là không liên thông (vì ở G1 không có đường đi, chẳnghạn, từ đ ỉnh 1 đ ến đỉnh 2 ; ở G4 không có đường đ i từ đỉnh 4 d ến đỉnh 3 v.v…). Có khi ở mỗ i cung củ a đồ thị người ta gắn vào đấy 1 giá trị thể hiện 1 thôngtin nào đó có liên quan tới cung, giá trị đó được gọ i là trọng số, và đồ thị đ ược gọ ilà đồ thị có trọng số (weighted graph). Ví dụ : đồ thị trên hình 6.2 thể hiện các đường đi nố i giữ a6 tỉnh A, B, C, D,E, F với các trọng số là độ dài tính theo km, của các tuyến đường. 83 55 A B C 60 47 D E 150 26 F Hình 6.2II. BIỂU DIỄN TRONG MÁY CỦA ĐỒ THỊ Cũng như các cấu trúc dữ liệu nói ở các chương trước, đối với đồ th ị, ta cũngxét tới 2 cách biểu diễn thông dụng sau đ ây :1. Biểu diễn bằ ng ma trận lân cận (lưu trữ kế tiếp) Xét 1 đồ thị có hướng G (V, E) với V có n đỉnh (n≥1). Giả sử các đ ỉnh đãđược đánh số từ 1 đến n. Đồ th ị G có thể được biểu diễn trong máy bởi 1 ma trận vuông A, kích thướcn × n, mà các phần tử Aij của nó sẽ nhận giá trị 1 hoặc 0 : Aij = 1 nếu trên G tồn tại 1 cung đi từ đỉnh i tới đỉnh j. Aij = 0 nếu không có cung giữa đỉnh i và j. Dĩ nhiên với đồ thị vô hướng, n ếu tồn tại 1 cung (i, j) thì ta có th ể h iểu là tồntại 1 cung đi từ i đến j, và ngược lại, cũng tồn tại 1 cung đi từ j tới i, ngh ĩa là Aij=1thì Aji = 1. Như vậy với đồ th ị vô hướng thì ma trận A biểu diễn nó có các phân tử đố ixứng với nhau qua đường chéo chính. Ma trận A được gọi là ma trận lân cận hay ma trận kề (adjacency ...