LÝ THUYẾT ĐỒ THỊ 1

- 2 THÔNG TIN CHUNG VỀ MÔN HỌC • Tên học phần: Lý thuyết đồ thị • Mã học phần.
- 3 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 1 KHÁI NIỆM ĐỒ THỊ • Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.
- Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị.
- Định nghĩa 1 (Đơn đồ thị.
- Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh khác rỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
- 4 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 1 KHÁI NIỆM ĐỒ THỊ Định nghĩa 2 (Đa đồ thị.
- Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh khác rỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
- CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 1 KHÁI NIỆM ĐỒ THỊ Định nghĩa 3 (Giả đồ thị.
- Giả đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh khác rỗng và E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là cạnh.
- Nhận xét: giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể chứa các khuyên và các cạnh lặp.
- CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 1 KHÁI NIỆM ĐỒ THỊ Định nghĩa 4 (Đơn đồ thị có hướng.
- Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh khác rỗng và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung.
- 7 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 1 KHÁI NIỆM ĐỒ THỊ Định nghĩa 5 (Đa đồ thị có hướng.
- Đa đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh khác rỗng và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung.
- Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v) Є E.
- Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó.
- Giả sử G = (V, E) là đồ thị vô hướng với m cạnh.
- Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
- Thực vậy, gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị.
- Cho G =(V, E) là một đồ thị có hướng.
- ĐỒ THỊ LIÊN THÔNG Định nghĩa 1 (Đường đi).
- Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1.
- ĐỒ THỊ LIÊN THÔNG Ví dụ 1.
- Trên đồ thị vô hướng cho trong hình.
- d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị.
- ĐỒ THỊ LIÊN THÔNG Định nghĩa 2.
- Đồ thị G và H Đồ thị G là liên thông, còn đồ thị H là không liên thông.
- ĐỒ THỊ LIÊN THÔNG Định nghĩa 3.
- Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó WV và FE.
- Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.
- Đồ thị H trong hình 2 gồm 3 thành phần liên thông H1, H2, H3.
- ĐỒ THỊ LIÊN THÔNG Định nghĩa 4.
- Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
- Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
- Trong đồ thị G ở hình 2, đỉnh c, d và e là đỉnh rẽ nhánh, còn các cạnh (c,d) và (c,e) là cầu.
- ĐỒ THỊ LIÊN THÔNG Định nghĩa 5.
- Đồ thị có hướng G = (V, A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
- Đồ thị có hướng G = (V, A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông.
- Xét ví dụ: 21 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT Đồ thị vòng: Đơn đồ thị n đỉnh v1, v2.
- (vn-1,vn), (vn,v1) được gọi là đồ thị vòng, ký hiệu là Cn.
- Xét ví dụ: 22 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT Đồ thị bánh xe: Từ đồ thị vòng Cn, thêm vào đỉnh vn+1 và các cạnh (vn+1,v1), (vn+1,v2.
- (vn+1,vn), ta nhận được đơn đồ thị gọi là đồ thị bánh xe, ký hiệu là Wn.
- Như vậy, mỗi đỉnh của Qn có bậc là n số cạnh của Qn là n.2n-1 Đồ thị lập phương Q1, Q2, Q3 24 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT Đồ thị phân đôi (đồ thị hai phe): Đơn đồ thị G=(V,E) sao cho V=V1UV2, V1∩V2.
- V2≠∅ và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị phân đôi.
- Nếu đồ thị phân đôi G=(V1UV2,E) sao cho với mọi v1ЄV1, v2 Є V2, (v1,v2) Є E thì G được gọi là đồ thị phân đôi đầy đủ.
- Nếu |V1|=m, |V2|=n thì đồ thị G được ký hiệu là Km,n.
- 25 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT Ứng dụng của các đồ thị đặc biệt.
- Các mạng cục bộ (LAN): Đồ thị phân đôi đầy Đồ thị vòng Cn Đồ thị bánh xe Wn đủ K1,n 26  CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1.
- Ma trận kề, ma trận trọng số Xét đơn đồ thị G=(V,E) Ma trận kề: Ma trận A={ai,j : i,j=1, 2.
- .,n gọi là ma trận kề của đồ thị G.
- Đồ thị vô hướng G 27 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1.
- Ma trận kề, ma trận trọng số Xét đơn đồ thị có hướng G=(V,E) Ma trận kề: Ma trận A={ai,j : i,j=1, 2.
- Ví dụ: Đồ thị có hướng G1 28 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH * Tính chất của ma trận kề của đồ thị vô hướng.
- Tính chất của ma trận kề của đồ thị có hướng.
- 29 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1.
- Ma trận kề, ma trận trọng số Xét ví dụ 2: 30 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH Ma trận trọng số: Đồ thị có trọng số là đồ thị mà mỗi cạnh (i,j) có một giá trị c(i,j) gọi là trọng số của cạnh.
- Để biểu diễn đồ thị ta sử dụng ma trận trọng số C= {c[i,j], i,j=1, 2.
- 33 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2.
- Ma trận liên thuộc đỉnh-cạnh: Xét G=(V, E) là đơn đồ thị có hướng.
- Ma trận liên thuộc đỉnh- cạnh có dạng: 34 CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 3.
- 61 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2.
- 3/2), nên G là đồ thị Hamilton.
- nên nó là đồ thị Hamilton.
- 62 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2.
- Đồ thị HAMILTON Ví dụ 4.
- Hình dưới đây mô tả cây tìm kiếm tất cả các chu trình Hamilton của đồ thị.
- Đồ thị HAMILTON Bài toán sắp xếp chỗ ngồi: Có n đại biểu đến dự hội nghị.
- Như vậy, ta có đồ thị đầy đủ Kn.
- 64 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2.
- Đồ thị HAMILTON Mỗi chu trình Hamilton là một cách sắp xếp như yêu cầu của bài toán.
- Bái toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy đủ Kn (hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung).
- Định lý: Đồ thị đầy đủ Kn với n lẻ và n ≥ 3 có đúng (n −1)/2 chu trình Hamilton phân biệt.
- Đồ thị HAMILTON Giải bài toán sắp xếp chỗ ngồi với n=11.
- Có cách sắp xếp chỗ ngồi phân biệt như sau CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 1.
- Định nghĩa và các tính chất cơ bản Định nghĩa: Cây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh.
- Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng.
- 67 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 1.
- Định nghĩa và các tính chất cơ bản: Định lý: Cho T là một đồ thị có n ≥ 2 đỉnh.
- 68 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2.
- Cây đó gọi là cây khung hay cây bao trùm của đồ thị G.
- 69 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2.
- Cây khung và bài toán tìm cây khung nhỏ nhất: Bài toán được phát biểu như sau: Cho G=(V,E) là đồ thị vô hướng liên thông có This image cann ot cur rently b e displayed.
- m (e ) eET 70 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2.
- Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị.
- 71 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 3.
- Bắt đầu từ đồ thị rỗng T có n đỉnh.
- 72 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 3.
- Thuật toán Kruskal: Xét thí dụ: Tìm cây khung nhỏ nhất cho bởi đồ thị: 73 4.
- trong đó v* là đỉnh tuỳ ý của đồ thị G.
- 74 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 4.
- Thuật toán Prim: Xét thí dụ: Tìm cây khung nhỏ nhất cho bởi đồ thị: 75 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 4.
- 76 CHƯƠNG V CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 5.
- Cây có gốc: Định nghĩa: Cây có hướng là đồ thị có hướng mà đồ thị vô hướng nền của nó là một cây.
- 77 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 5.
- 78 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 5.
- TÌM ĐƯỜNG ĐI NGẮN NHẤT • Trong phần này, giới thiệu về giải thuật tìm đường đi ngắn nhất giữa 2 đỉnh trên đồ thị có trọng số.
- Giới thiệu về bài toán – Xét đồ thị G.
- Bài toán: Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t của đồ thị G.
- Tìm đường đi ngắn nhất từ A đến Z trong đồ thị G sau.
- Cho đồ thị G như trên, tìm đường từ 1->6 – Các bước thực hiện Bước lặp Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 Đỉnh 6