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!
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 1 - TS. Lê Nhật Duy LÝ THUYẾT ĐỒ THỊ TS. Lê Nhật Duy Blog: htps://Lnduy.wordpress.com Email: Ln.duy@mail.ru 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 => 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 H.Rosen, 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 đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 7 Lý thuyết đồ thị II. Các loại đồ thị Đồ thị Đồ thị vô hướng Đơn đồ thị Đa đồ thị Giả đồ thị Đồ thị có hướng Đơn đồ thị Đa đồ thị Chương 1 – Các khái niệm cơ bản 8 Lý thuyết đồ thị II. Các loại đồ thị Đơn đồ thị vô huớng Đồ thị G=(V, E) được gọi là đơn đồ thị vô hướng: V: Là tập các đỉnh E: là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V. V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)} Chương 1 – Các khái niệm cơ bản 9 Lý thuyết đồ thị II. Các loại đồ thị Đa đồ thị vô huớng Đồ thị G=(V, E) được gọi là đa đồ thị vô hướng: V: Là tập các đỉnh E: Là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V. Hai cạnh e1, e2 gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3, 5) } Chương 1 – Các khái niệm cơ bản 10 Lý thuyết đồ thị II. Các loại đồ thị Giả đồ thị vô huớng Đồ thị G=(V, E) được gọi là giả đồ thị vô hướng: V: Là tập các đỉnh E: Là họ các cặp không có thứ tự gồm hai phần tử không nhất thiết khác nhau của V. Cạnh e được gọi là khuyên nếu nó có dạng: e=(u, u) V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3, 5), (2, 2), (3, 3) } Chương 1 – Các khái niệm cơ bản 11 Lý thuyết đồ thị II. Các loại đồ thị Đơn đồ thị có hướng Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng: V: Là tập các đỉnh E: Là tập các cặp có thứ tự gồm hai phần tử khác nhau của V. (tập các cung) V={1, 2, 3, 4, 5} E={(2, 1), (1, 3), (5, 1), (4, 2), (3, 4), (3, 5), (5, 4)} Chương 1 – Các khái niệm cơ bản 12 Lý thuyết đồ thị II. Các loại đồ thị Đa đồ thị có hướng Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng: V: Là tập các đỉnh E: Là họ các cặp có thứ tự gồm hai phần tử khác nhau của V. (tập các cung) Hai cung e1, e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh. V={1, 2, 3, 4, 5} E={(2, 1), (1, 3), (6, 2), (3, 4), (6, 3), (4, 6), (5, 4), (5, 6), (3,1), (6,2)} Chương 1 – Các khái niệm cơ bản 13 Lý thuyết đồ thị II. Các loại đồ thị Đồ thị Không có thứ tự Đồ thị vô hướng Không cạnh lặp, không khuyên Đơn đồ thị Có cạnh lặp, không khuyên Đa đồ thị ...