TAILIEUCHUNG - Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị

Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị sau đây để hiểu rõ hơn về khái niệm đồ thị, biểu diễn đồ thị, một số đồ thị đặc biệt, đồ thị có hướng,. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết. | TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC Giảng viên: Cao Thanh Tình (Email: tinhct@) Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM Nội dung môn học Phần 1: Lý thuyết đồ thị Đại cương về đồ thị Các bài toán về đường đi Đồ thị phẳng và bài toán tô màu đồ thị Cây Phần 2: Đại số Boole Đại số Boole Cổng logic Cực tiểu hóa hàm Boole Các khái niệm cơ bản Đồ thị (Graph) G = (V, E) với V≠ V: tập các đỉnh E: tập các cạnh Cạnh e E ứng với 2 đỉnh u, v V v, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w Ký hiệu: e = vw ( ) u v: e được gọi là vòng (khuyên) tại u - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Các khái niệm cơ bản Đồ thị (Graph) Cạnh bội (song song) Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh Đơn đồ thị Đồ thị không có vòng và cạnh song song Đa đồ thị Các đồ thị không phải là đơn đồ thị - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Các khái niệm cơ bản Đồ thị (Graph) Đồ thị đầy đủ Đồ thị mà mọi cặp đỉnh đều kề nhau Kn: đơn đồ thị đầy đủ Đồ thị con Đồ thị G’ = (V’, E’) V’ V, E’ E Đồ thị hữu hạn E và V hữu hạn Đồ thị vô hạn - Đồ thị dùng biểu diễn mối tương quan giữa 2 hay nhiều đối tượng Biểu diễn đồ thị Biểu diễn hình học Mỗi đỉnh một điểm Mỗi cạnh một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó Biểu diễn bằng ma trận Thường được dùng để biểu diễn trên máy tính 2 cách biểu diễn thường dùng Ma trận kề Ma trận liên thuộc Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ma trận vuông cấp n (số đỉnh của đồ thị) Các phần tử aij được xác định bởi aij = 1: Nếu vivj là một cạnh của G aij = 0: Nếu vivj không là một cạnh của G Tính chất Phụ thuộc vào thứ tự liệt kê của các đỉnh Ma trận là đối xứng Một vòng được tính là một cạnh (akk = 1) Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ví dụ 1 Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận kề Ví dụ 2 Biểu diễn đồ thị Biểu diễn bằng ma trận Ma trận liên thuộc Ma trận M = (mij)nxm Các phần .

• Toán học
• Toán rời rạc
• Bài giảng Toán rời rạc
• Toán rời rạc ứng dụng trong tin học
• Đại cương về đồ thị
• Biểu diễn đồ thị
• Đồ thị có hướng
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc