Xem mẫu
- TOÁN RỜI RẠC
Chương 06:
Đồ thị
Giảng viên: ThS. Trần Quang Khải
- Nội dung
1. Giới thiệu về lý thuyết đồ thị.
2. Đồ thị vô hướng – Đồ thị có hướng.
3. Bậc của đỉnh.
4. Một số dạng đồ thị đặc biệt.
5. Biểu diễn đồ thị trên máy tính.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 2
- Giới thiệu
Những câu hỏi cũ:
Đường nào nhanh nhất tới nhà người yêu?
Đường nào gần nhất tới café Gió và Nước?
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 3
- Giới thiệu
Câu hỏi khác:
Thế kế mạng LAN cho tòa nhà 20 tầng thế nào đây?
Sắp đặt các links trong website sao cho hợp lý?
Sắp xếp cả núi công việc để hoàn thành sớm nhất?
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 4
- Giới thiệu
Định nghĩa đồ thị (graph): cấu trúc rời rạc gồm
Các đỉnh (vertices or nodes).
Các cạnh (edges) nối các đỉnh.
Biểu diễn:
Đỉnh: các điểm.
Cạnh: đường thẳng/cong.
Hai loại:
Đồ thị vô hướng (undirected graph).
Đồ thị có hướng (directed graph).
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 5
- Giới thiệu
Lý thuyết đồ thị:
Là một lý thuyết kinh điển.
Ứng dụng rộng rãi ngày nay, trong nhiều lĩnh vực:
• Nghiên cứu Khoa học.
• Công nghiệp.
Khởi xướng:
Leonard Euler (thế kỷ 18).
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 6
- Chương 06
Đồ thị vô hướng
Đồ thị có hướng
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012
- Đồ thị đơn cạnh
Simple graph (đơn đồ thị): G = (V, E)
V: một tập hợp không rỗng của các đỉnh.
E: tập các cặp đỉnh (tức các cạnh) không-thứ-tự.
Các cạnh nối (connect) các đỉnh lại với nhau.
Giữa 2 đỉnh chỉ có đúng 1 cạnh.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 8
- Đồ thị đa cạnh
Multi-graph (đa đồ thị): G = (V, E)
E: cho phép nhiều cạnh nối một cặp đỉnh.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 9
- Đồ thị “giả”
Pseudo-graph (giả đồ thị): G = (V, E)
E: cho phép lặp (loop) tại các đỉnh.
(Còn gọi là chứa các khuyên)
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 10
- Đồ thị có hướng
Directed graph: G = (V, E)
V: một tập hợp không rỗng của các đỉnh.
E: tập các cặp đỉnh có-thứ-tự.
Cạnh nối 2 đỉnh gọi là cung (arc).
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 11
- Chương 06
Bậc của đỉnh
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012
- Một số thuật ngữ cơ bản
Đồ thị vô hướng:
Cho G = (V, E) là đồ thị vô hướng và e (u, v) E
u và v gọi là 2 đỉnh liền kề (adjacent).
e gọi là cạnh nối (cạnh kề: incident) của u và v.
u và v gọi là điểm cuối của e.
Bậc (degree) của đỉnh là số các cạnh nối với nó.
Kí hiệu: deg(e) = …
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 13
- Bậc của đỉnh – Ví dụ
Điểm “bị treo”
( )
Điểm
“cô lập”
( )
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 14
- Một số thuật ngữ cơ bản
Đồ thị có hướng:
Cho G = (V, E) là đồ thị có hướng và e (u, v) E
u gọi là nối tới v, v gọi là được nối từ u.
u gọi là đỉnh đầu, v gọi là đỉnh cuối.
Khi đó:
deg−(u): bậc “vào” (in-degree) của u.
deg+(u): bậc “ra” (out-degree) của u.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 15
- Bậc của đỉnh – Ví dụ
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 16
- Bậc của đỉnh – Định lý
Định lý 1:
Cho G = (V, E) là đồ thị vô hướng:
2 E deg (v )
vV
(Handshaking theorem)
Một đồ thị luôn có 1 số chẵn các đỉnh bậc lẻ.
Lưu ý: định lý 1 đúng ngay cả khi đồ thị là đa
cạnh hoặc có chứa khuyên.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 17
- Bậc của đỉnh – Định lý
Định lý 2:
Cho G = (V, E) là đồ thị có hướng:
E deg (v ) deg (v )
vV vV
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 18
- Một số dạng đồ thị đặc biệt
1. Đồ thị đầy đủ (complete): n đỉnh
Mỗi cặp đỉnh đều có đúng 1 cạnh nối. Kí hiệu: Kn.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 19
- Một số dạng đồ thị đặc biệt
2. Đồ thị chu trình (cycle - vòng): n ≥ 3 đỉnh
Kí hiệu: Cn.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 20
nguon tai.lieu . vn
