Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị

1. Chương 2 Biểu diễn đồ thị
2. Biểu diễn bằng ma trận kề ⚫ Định nghĩa 1.10 Cho 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 đỉnh i 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
3. Ví dụ Ma trận kề của đa đồ thị có hướng: 2 0 1 1 2 1 3 A = 0 0 1 0 4 0 0 1 0 0 0 1 0 Hình 1.3. Đồ thị có hướng và ma trận kề
4. Ma trận kề (tt) ⚫ Định lý 1.1 Phầ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.
5. 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 k Ký hiệu A = [aij], A = [bij], C = A .A = [cij] Khi đó cij =  biq aqj q j i
6. Ma 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 .
7. 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ề.
8. Danh sách kề (tt) Đồ thị và danh sách kề biểu diễn đồ thị tương ứng: b c a e d
9. Danh sách cạnh (cung) ⚫ Đồ thị và danh sách cung tương ứng: b c a e d