Học viện Cơng nghệ Bưu Viễn thơng Khoa Cơng nghệ thơng tin Tốn rời rạc Các khái niệm lý thuyết đồ thị Ngô Xuân Bách CuuDuongThanCong.com https://fb.com/tailieudientucntt Nội dung Định nghĩa đồ thị Một số thuật ngữ đồ thị vô hướng Một số thuật ngữ đồ thị có hướng Một số dạng đồ thị đặc biệt     CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đơn đồ thị vô hướng Định nghĩa 1: Đơn đồ thị vô hướng 𝐺 = < 𝑉, 𝐸 > bao gồm 𝑉 tập đỉnh, 𝐸 tập cặp khơng có thứ tự gồm hai phần tử khác 𝑉 gọi cạnh  (Phương ND, 2013) CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đa đồ thị vô hướng Định nghĩa 2: Đa đồ thị vô hướng 𝐺 = < 𝑉, 𝐸 > bao gồm 𝑉 tập đỉnh, 𝐸 họ cặp khơng có thứ tự gồm hai phần tử khác 𝑉 gọi tập cạnh 𝑒1 ∈ 𝐸 , 𝑒2 ∈ 𝐸 gọi cạnh bội chúng tương ứng với cặp đỉnh  (Phương ND, 2013) CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Giả đồ thị vô hướng Định nghĩa 3: Giả đồ thị vô hướng 𝐺 = < 𝑉, 𝐸 > bao gồm 𝑉 tập đỉnh, 𝐸 họ cặp khơng có thứ tự gồm hai phần tử (hai phần tử không thiết phải khác nhau) 𝑉 gọi cạnh Cạnh 𝑒 gọi khuyên có dạng 𝑒 = (𝑢, 𝑢), 𝑢 đỉnh thuộc 𝑉  (Phương ND, 2013) CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đơn đồ thị có hướng Định nghĩa 4: Đơn đồ thị có hướng 𝐺 = < 𝑉, 𝐸 > bao gồm 𝑉 tập đỉnh, 𝐸 tập cặp có thứ tự gồm hai phần tử 𝑉 gọi cung  (Phương ND, 2013) CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đa đồ thị có hướng Định nghĩa 5: Đa đồ thị có hướng 𝐺 = < 𝑉, 𝐸 > bao gồm 𝑉 tập đỉnh, 𝐸 họ cặp có thứ tự gồm hai phần tử khác 𝑉 gọi cung Hai cung 𝑒1 , 𝑒2 tương ứng với cặp đỉnh gọi cung lặp  (Phương ND, 2013) CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Quy ước Ta chủ yếu làm việc với đơn đồ thị vô hướng đơn đồ thị có hướng Khi viết “đồ thị vơ hướng” ta hiểu “đơn đồ thị vô hướng” Khi viết “đồ thị có hướng” ta hiểu “đơn đồ thị có hướng”    CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Nội dung Định nghĩa đồ thị Một số thuật ngữ đồ thị vô hướng Một số thuật ngữ đồ thị có hướng Một số dạng đồ thị đặc biệt     CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Bậc đỉnh  Định nghĩa 1: Hai đỉnh 𝑢 𝑣 đồ thị vô hướng 𝐺 =< 𝑉, 𝐸 > gọi kề (𝑢, 𝑣) cạnh thuộc đồ thị 𝐺 Nếu 𝑒 = (𝑢, 𝑣) cạnh đồ thị 𝐺 ta nói cạnh liên thuộc với hai đỉnh 𝑢 𝑣, ta nói cạnh 𝑒 nối đỉnh 𝑢 với đỉnh 𝑣, đồng thời đỉnh 𝑢 𝑣 gọi đỉnh đầu cạnh (𝑢, 𝑣)  Định nghĩa 2: Ta gọi bậc đỉnh 𝑣 đồ thị vô hướng số cạnh liên thuộc với ký hiệu deg(𝑣) 10 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Cầu, trụ   Định nghĩa 3: Cạnh 𝑒 ∈ 𝐸 gọi cầu loại bỏ e làm tăng thành phần liên thông đồ thị Đỉnh 𝑢 ∈ 𝑉 gọi đỉnh trụ loại bỏ 𝑢 với cạnh nối với 𝑢 làm tăng thành phần liên thơng đồ thị Ví dụ cạnh (5,9), (5,10) cầu, đỉnh 5,6 trụ (Phương ND, 2013) 17 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Nội dung     Định nghĩa đồ thị Một số thuật ngữ đồ thị vô hướng Một số thuật ngữ đồ thị có hướng Một số dạng đồ thị đặc biệt 18 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Bán bậc đỉnh  Định nghĩa 1: Nếu 𝑒 = (𝑢, 𝑣) cung đồ thị có hướng 𝐺 ta nói hai đỉnh 𝑢 𝑣 kề nhau, nói cung (𝑢, 𝑣) nối đỉnh 𝑢 với đỉnh 𝑣, nói cung khỏi đỉnh 𝑢 vào đỉnh 𝑣 Đỉnh 𝑢 gọi đỉnh đầu, đỉnh 𝑣 gọi đỉnh cuối cung (𝑢, 𝑣)  Định nghĩa 2: Ta gọi bán bậc đỉnh 𝑣 đồ thị có hướng số cung đồ thị khỏi 𝑣 ký hiệu 𝑑𝑒𝑔+ (𝑣) Ta gọi bán bậc vào đỉnh 𝑣 đồ thị có hướng số cung đồ thị vào 𝑣 ký hiệu 𝑑𝑒𝑔− (𝑣) 19 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Ví dụ   𝑑𝑒𝑔+ 𝑎 = 2, 𝑑𝑒𝑔+ 𝑏 = 2, 𝑑𝑒𝑔+ 𝑐 = 0, 𝑑𝑒𝑔+ (𝑑) = 1, 𝑑𝑒𝑔+ (𝑒) = 𝑑𝑒𝑔− 𝑎 = 1, 𝑑𝑒𝑔− 𝑏 = 1, 𝑑𝑒𝑔− 𝑐 = 2, 𝑑𝑒𝑔− (𝑑) = 2, 𝑑𝑒𝑔− (𝑒) = (Phương ND, 2013) 20 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Định lý tổng bán bậc đỉnh  Định lý 1: Giả sử 𝐺 =< 𝑉, 𝐸 > đồ thị có hướng Khi + = − = |𝐸| 𝑑𝑒𝑔 𝑑𝑒𝑔 𝑣∈𝑉 𝑣∈𝑉 Chứng minh: Do cung (𝑢, 𝑣) tính lần bán bậc vào đỉnh 𝑣 lần bán bậc đỉnh 𝑢  Chú ý:  o o 21 Rất nhiều tính chất đồ thị có hướng không phụ thuộc vào hướng cung Vì vậy, nhiều trường hợp, ta bỏ qua hướng cung đồ thị Đồ thị vô hướng nhận cách bỏ qua hướng cung gọi đồ thị vô hướng tương ứng với đồ thị có hướng cho CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đường đi, chu trình      Định nghĩa 1: Đường độ dài 𝑛 từ đỉnh 𝑢 đến đỉnh 𝑣 đồ thị có hướng 𝐺 =< 𝑉, 𝐸 > dãy 𝑥0 , 𝑥1 , , 𝑥𝑛−1 , 𝑥𝑛 , 𝑛 số nguyên dương, 𝑥0 = 𝑢, 𝑥𝑛 = 𝑣, (𝑥𝑖 , 𝑥𝑖+1 ) ∈ 𝐸, 𝑖 = 0, 1, 2, , 𝑛 − Đường cịn biểu diễn thành dãy cung (𝑥0 , 𝑥1 )(𝑥1 , 𝑥2 ) , , (𝑥𝑛−1 , 𝑥𝑛 ) Đỉnh 𝑢 đỉnh đầu, đỉnh 𝑣 đỉnh cuối đường Đường có đỉnh đầu trùng với đỉnh cuối (𝑢 = 𝑣) gọi chu trình Đường hay chu trình gọi đơn khơng có cạnh lặp lại 22 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Liên thông mạnh, liên thơng yếu Định nghĩa 2: Đồ thị có hướng 𝐺 =< 𝑉, 𝐸 > gọi liên thông mạnh hai đỉnh 𝑢 ∈ 𝑉, 𝑣 ∈ 𝑉 có đường từ 𝑢 đến 𝑣 Định nghĩa 3: Đồ thị có hướng 𝐺 =< 𝑉, 𝐸 > gọi liên thông yếu đồ thị vơ hướng tương ứng với liên thông (Phương ND, 2013) 23 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Định chiều  Định nghĩa 4: Đồ thị vô hướng 𝐺 =< 𝑉, 𝐸 > gọi định chiều ta biến đổi cạnh 𝐺 thành cung tương ứng để nhận đồ thị có hướng liên thơng mạnh  Định lý 1: Đồ thị vô hướng 𝐺 =< 𝑉, 𝐸 > định chiều cạnh khơng phải cầu 24 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Nội dung     Định nghĩa đồ thị Một số thuật ngữ đồ thị vô hướng Một số thuật ngữ đồ thị có hướng Một số dạng đồ thị đặc biệt 25 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đồ thị đầy đủ  Đồ thị đầy đủ 𝑛 đỉnh, ký hiệu 𝐾𝑛 , đơn đồ thị vô hướng mà hai đỉnh có cạnh nối 𝑛(𝑛−1) o Số cạnh: (Phương ND, 2013) 26 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đồ thị vòng  Đồ thị vòng 𝑛 đỉnh, ký hiệu 𝐶𝑛 (𝑛 ≥ 3) đơn đồ thị vô hướng gồm cạnh (1,2), (2,3), … , (𝑛 − 1, 𝑛), (𝑛, 1) (Phương ND, 2013) 27 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đồ thị bánh xe  Đồ thị bánh xe 𝑛 đỉnh, ký hiệu 𝑊𝑛 đồ thị thu cách bổ sung đỉnh nối với tất đỉnh đồ thị vòng 𝐶𝑛 (Phương ND, 2013) 28 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Đồ thị hai phía  Đồ thị 𝐺 =< 𝑉, 𝐸 > gọi đồ thị hai phía tập đỉnh 𝑉 phân hoạch thành hai tập 𝑋 𝑌 cho cạnh đồ thị có dạng (𝑥, 𝑦), 𝑥 ∈ 𝑋 𝑦 ∈ 𝑌 (Phương ND, 2013) 29 CuuDuongThanCong.com http://www.ptit.edu.vn https://fb.com/tailieudientucntt Bài tập  Xác định bậc đỉnh đồ thị vô hướng sau CuuDuongThanCong.com 30 http://www.ptit.edu.vn https://fb.com/tailieudientucntt Bài tập  Xác định bán bậc vào bán bậc đỉnh đồ thị có hướng sau CuuDuongThanCong.com 31 http://www.ptit.edu.vn https://fb.com/tailieudientucntt ... https://fb .com/ tailieudientucntt Ví dụ  