Bài giảng Toán rời rạc - Chương 2: Biểu diễn đồ thị

Chương 2Biểu diễn đồ thịBiểu diễn bằng ma trận kề Định nghĩa 1.10Cho G = (V, E) là một đồ thị có các đỉnh được đánh số là các số tự nhiên: 1, 2, ... , n. Ma trận vuông A cấp n được gọi là ma trận kề của đồ thị G nếu:  i, j  V, A[i,j] = số cạnh nối đỉnhi với đỉnh j trong G. Đồ thị G là đối xứng khi và chỉ khi ma trận kề A là đối xứng Ví dụMa trận kề của đa đồ thị có hướng: 	0 1 1 2	 A =	0 0 1 0	0 0 1 0	 0 0 1 0Hình 1.3. Đồ thị có hướng và ma trận kề1243Ma trận kề (tt)Định lý 1.1Phần tử ở hàng i và cột j của ma trận luỹ thừa Ak chính là số các đường đi khác nhau có độ dài k nốiđỉnh i với đỉnh j trong đồ thị G.Ma trận kề (tt)Chứng minh:Quy nạp theo độ dài k của đường đi - k = 1: suy từ định nghĩa ma trận kề.- (k)  (k+1)Ký hiệu A = [aij], Ak = [bij], C = Ak.A = [cij] Khi đó cij =  biq aqjiqjMa trận kề (tt)Chứng minh (tiếp):Theo giả thiết quy nạp, với q bất kỳ (1  q  n), biq chính là số đường đi từ đỉnh i đến đỉnh q có độ dài k.- Nếu aqj = d  1 thì có cạnh đi từ q đến j, do vậy có các đường đi từ i đến j qua q với độ dài k+1, mà số các đường đi đó chính là d * biq .Danh sách kề Với mỗi đỉnh của đồ thị ta xây dựng một danh sách móc nối chứa các đỉnh kề với đỉnh này: Danh sách này được gọi là danh sách kề. Một đồ thị được biểu diễn bằng một mảng các danh sách kề.Danh sách kề (tt)Đồ thị và danh sách kề biểu diễn đồ thị tương ứng:abedcDanh sách cạnh (cung)Đồ thị và danh sách cung tương ứng:abedc