Phần tiếp theo bài giảng "Toán rời rạc và lý thuyết đồ thị - Bài 5: Đường đi trên đồ thị" cung cấp cho người học các kiến thức: Mở đầu, đồ thị Euler, đồ thị Haminton, tìm đường đi ngắn nhất. nội dung chi tiết. | TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN MÔN TOÁN RỜI RẠC Company L/O/G/O Chương 5 ĐƯỜNG ĐI TRÊN ĐỒ THỊ GV: Võ Tấn Dũng MỞ ĐẦU Bài toán về những cây cầu ở Konigsber Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải được bài toán hóc búa nổi tiếng thời đó về những cây cầu ở Konigberg. Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. 3 1 2 4 Câu hỏi đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không. Euler đã chứng minh rằng bài toán không có lời giải bằng ngôn ngữ đồ thị. Ông biểu diễn 2 hòn đảo và 2 bờ sông bằng 4 điểm và 7 cây cầu bằng các cạnh nối các điểm như sau: 3 Việc đi qua 7 cây cầu tương đương với việc vẽ đồ thị trên bằng 1 nét. 1 2 4 Sau này ta sẽ thấy đồ thị trên không thể vẽ bằng 1 nét. ĐỒ THỊ EULER Định nghĩa Cho đồ thị vô hướng G = (V, E) Đường đi Euler: Đường đi đơn trong G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là đường đi Euler Chu trình Euler: Chu trình đơn trong đồ thị G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là chu trình .
