Bài giảng Toán rời rạc và lý thuyết đồ thị: Bài 5 - Võ Tấn Dũng

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