Bài giảng Toán rời rạc: Chương 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! | 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ố
