Xem mẫu
- CHƯƠNG 5
ĐỒ THỊ
Nguyễn Quỳnh Diệp
diepnq@tlu.edu.vn
File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD
1
Nguyễn Quỳnh Diệp
- NỘI DUNG
• Các định nghĩa
• Các thuật ngữ về đồ thị
• Biểu diễn đồ thị
• Tính liên thông
• Đường đi Euler và đường đi Hamilton
• Bài toán đường đi ngắn nhất
Toán rời rạc Nguyễn Quỳnh Diệp 2
- 5.1. CÁC ĐỊNH NGHĨA
Toán rời rạc Nguyễn Quỳnh Diệp 3
- ĐỒ THỊ
• Đồ thị là một cấu trúc rời rạc
• Gồm các đỉnh (V) và các cạnh (E) nối đỉnh
Toán rời rạc Nguyễn Quỳnh Diệp 4
- ĐỒ THỊ
• Dùng đồ thị cho các lĩnh vực khác nhau:
Kĩ sư điện: dùng đồ thị để thiết kế các mạch điện
Ngành khoa học: biểu diễn cấu trúc hóa học của các chất, cấu
trúc DNA…
Ngành ngôn ngữ học: biểu diễn cây ngôn ngữ
• Các ứng dụng khác của đồ thị
Biểu diễn sự ảnh hưởng của một ai đó trong tổ chức
Biểu diễn kết quả cuộc thi thể thao
Mạng hàng không
Toán rời rạc Nguyễn Quỳnh Diệp 5
- PHÂN LOẠI ĐỒ THỊ - ĐƠN ĐỒ THỊ
Định nghĩa 1:
Một đơn đồ thị G = (V, E) gồm một tập không rỗng V mà các
phẩn tử của nó gọi là các đỉnh và một tập E mà các phần tử
của nó gọi là các cạnh là các cặp không sắp thứ tự của các
đỉnh phân biệt.
Ví dụ:
Toán rời rạc Nguyễn Quỳnh Diệp 6
- ĐA ĐỒ THỊ
Định nghĩa 2:
Một đa đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các
cạnh E và một hàm f từ E tới {(u,v)| u,v V , u v}.
Các cạnh e1 và e2 được gọi là cạnh bội nếu f(e1) = f(e2).
Ví dụ:
Toán rời rạc Nguyễn Quỳnh Diệp 7
- GIẢ ĐỒ THỊ
Định nghĩa 3:
Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các
cạnh E và một hàm f từ E tới {{u,v}| u,v V }.
Một cạnh là khuyên nếu f(e) = { u, u } = {u} với một đỉnh u
nào đó
Ví dụ:
Toán rời rạc Nguyễn Quỳnh Diệp 8
- ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 4:
Một đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một
tập các cạnh E là các cặp có thứ tự của các phần tử thuộc V.
Ví dụ:
Toán rời rạc Nguyễn Quỳnh Diệp 9
- ĐA ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 5:
Một đa đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một
tập các cạnh E và một hàm f từ E tới {(u,v)| u, v V}.
Cạnh e1 và e2 là các cạnh bội nếu f(e1) = f(e2).
Ví dụ:
Toán rời rạc Nguyễn Quỳnh Diệp 10
- ĐỒ THỊ
Bảng thuật ngữ đồ thị:
Loại Cạnh Cạnh bội ? Có khuyên ?
Đơn đồ thị Vô hướng Không Không
Đa đồ thị Vô hướng Có Không
Giả đồ thị Vô hướng Có Có
Đồ thị có hướng Có hướng Không Có
Đa đồ thị có hướng Có hướng Có Có
Toán rời rạc Nguyễn Quỳnh Diệp 11
- CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 1: Mạng xã hội
Toán rời rạc Nguyễn Quỳnh Diệp 12
- CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 2: Đồ thị ảnh hưởng
Toán rời rạc Nguyễn Quỳnh Diệp 13
- CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 3: Đồ thị các môđun phụ thuộc
Toán rời rạc Nguyễn Quỳnh Diệp 14
- CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 4: Đồ thị thi đấu
Toán rời rạc Nguyễn Quỳnh Diệp 15
- BÀI TẬP
Bài 1: Xác định các loại đồ thị cho hình bên dưới
16
Toán rời rạc Nguyễn Quỳnh Diệp 16
- BÀI TẬP
Bài 2: Xác định các loại đồ thị cho hình bên dưới
17
Toán rời rạc Nguyễn Quỳnh Diệp 17
- 5.2. CÁC THUẬT NGỮ VỀ ĐỒ THỊ
Toán rời rạc Nguyễn Quỳnh Diệp 18
- ĐỒ THỊ VÔ HƯỚNG
Định nghĩa 1:
Cho đồ thị vô hướng G, hai đỉnh u và v được gọi là liền kề
(hoặc láng giềng) nếu {u, v} là một cạnh của G.
Nếu e = {u, v} thì e gọi là cạnh liên thuộc hoặc cạnh nối với
các đỉnh u và v.
Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}.
Định nghĩa 2:
Trong đồ thị vô hướng, bậc của một đỉnh 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ó. Kí hiệu bậc của đỉnh v là deg(v)
Toán rời rạc Nguyễn Quỳnh Diệp 19
- ĐỒ THỊ VÔ HƯỚNG
Ví dụ 1: Bậc của các đỉnh trong các đồ thị sau là bao nhiêu?
• Đỉnh bậc 0 gọi là đỉnh cô lập (ví dụ đỉnh g trong G)
• Đỉnh bậc 1 gọi là đỉnh treo (ví dụ đỉnh d trong G, c trong H)
Toán rời rạc Nguyễn Quỳnh Diệp 20
nguon tai.lieu . vn
