Lí thuyết đồ thị

Trước khi đến với lí thuyết đồ thị, ta có một câu hỏi nhỏ như sau:

Thành phố Königsberg thuộc Phổ, nay là Kaliningrad thuộc Nga, là một thành phố nằm ở \(2\) bên bờ sông Pregel và có \(2\) hòn đảo lớn Kneiphof và Lomse. Trước kia, \(2\) hòn đảo được kết nối với nhau và với \(2\) bên bờ sông bằng \(7\) cây cầu.

^{Hình ảnh thành phố Königsberg - Wikimedia - Public Domain}

Bài toán đặt ra ở đây là: Hãy tìm một con đường đi qua \(7\) cây cầu ít nhất một lần và chỉ một lần duy nhất.

Bài toán này - bài toán \(7\) cầu ở Königsberg, đã được giải bởi nhà toán học Leonhard Euler vào thế kỉ \(XVIII\) và đã cho ra đời định lý đầu tiên về lý thuyết đồ thị.

Ở chương này, ta sẽ tìm hiểu về lý thuyết đồ thị: định nghĩa, các dạng của đồ thị, một số khái niệm, tính chất liên quan, cách lưu trữ đồ thị trong chương trình và một số thuật toán liên quan đến đồ thị.

Lời giải cho bài toán bài toán \(7\) cầu ở Königsberg nằm ở phần đường đi Euler.