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

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!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 6.1 - ThS. Trần Quang KhảiTOÁ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ảiToá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ảiToá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ệt1. Đồ 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ệt2. Đồ thị chu trình (cycle - vòng): n ≥ 3 đỉnh Kí hiệu: Cn. ...