tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 1 được biên soạn gồm các nội dung chính sau: Định nghĩa đồ thị; Các loại đồ thị; Các thuật ngữ cơ bản trong đồ thị; Đường đi, chu trình; Đồ thị liên thông; Một số dạng đồ thị đặc biệt. Mời các bạn cùng tham khảo! | LÝ THUYẾT ĐỒ THỊ TS. Lê Nhật Duy Blog htps Email Nội dung chương trình Mục tiêu môn học Cung cấp cho sinh viên các khái niệm cơ bản của lý thuyết đồ thị đồ thị Euler Hamilton cây và cây khung bé nhất của đồ thị bài toán đường đi ngắn nhất và bài toán luồng cực đại trong mạng gt Giúp sinh viên có thể sử dụng mô hình lý thuyết đồ thị để mô hình hóa vấn đề bài toán thực tế một cách hiệu quả. Học phần này trang bị những kiến thức toán nền tảng phục vụ cho các chuyên ngành thuộc lĩnh vực CNTT. Thời lượng Lý thuyết 45 tiết 2 Kiểm tra đánh giá Kiểm tra giữa kỳ Tiểu luận bài tập lớn theo nhóm Thi kết thúc môn Giáo trình và TLTK Giáo trình Kenneth Toán rời rạc - Ứng dụng trong tin học NXB Khoa học kỹ thuật. Hà nội-1997. Phạm Văn Thiều và Đặng Hữu Thịnh dịch . Tài liệu tham khảo Slides bài giảng của giảng viên. Rules Lý thuyết đồ thị Chương 1 Các khái niệm cơ bản Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 Các khái niệm cơ bản 2 Lý thuyết đồ thị I. Định nghĩa đồ thị Bài toán Euler Konigsber 1736 Có thể chỉ một lần đi qua tất cả 7 chiếc cầu này hay không Chương 1 Các khái niệm cơ bản 3 Lý thuyết đồ thị I. Định nghĩa đồ thị Chuyển bài toán về dạng đồ thị Mỗi vùng là 1 đỉnh Mỗi chiếc cầu là 1 cạnh Chương 1 Các khái niệm cơ bản 4 Lý thuyết đồ thị I. Định nghĩa đồ thị Đồ thị được xây dựng từ bài toán Euler Có thể đi qua tất cả các cạnh của đồ thị sao cho mỗi cạnh chỉ đi qua đúng một lần được không Chương 1 Các khái niệm cơ bản 5 Lý thuyết đồ thị I. Định nghĩa đồ thị Định nghĩa Đồ thị G là một tập hợp gồm các đỉnh và các cạnh. Ta thường ký hiệu G V E trong đó V Là tập các đỉnh E Là tập các cạnh V 1 2 3 4 E a b c d e Chương 1 Các khái niệm cơ bản 6 Lý thuyết đồ thị Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi chu trình V. Đồ thị liên thông VI. Một số dạng