# Giới thiệu về 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 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

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ị.