Bài giảng Toán rời rạc: Chương 6.1 - ThS. Trần Quang Khải

Chia sẻ: Cuchoami2510 | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

19
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Chương 6.1 cung cấp cho người học những kiến thức như: Giới thiệu về lý thuyết đồ thị; Đồ thị vô hướng – Đồ thị có hướng; Bậc của đỉnh; Một số dạng đồ thị đặc biệt; Biểu diễn đồ thị trên máy tính. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 6.1 - ThS. Trần Quang Khải

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 ) vV (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 )   vV vV 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