Bài 1: Giới thiệu Graph Theory

Tham khảo Video sau đây :

Sau đây là lý thuyết mình co động lại (không nhất thiết phải xem Video)

1. Định nghĩa

Graph Theory nghiên cứu các tính chất của graph là một tập các đối tượng gọi là các đỉnh (nút) nối với nhau bởi các cạnh (cung).

Cạnh có thể có hướng hoặc vô hướng

💡 MẸO

Graph thường được vẽ dưới dạng một tập các điểm (các đỉnh) nối với nhau bằng cách đoạn thẳng (các cạnh)

2. Nguồn gốc

Bài toán bảy cây cầu Euler (bảy cầu ở Königsberg ở Nga) bao gồm hai hòn đảo lớn nối với nhau và với đất liền với bảy cây cầu như sau :

YÊU CẦU

Tìm một tuyến đường mà đi qua mỗi cây cầu một lần và chỉ đúng một lần (bất kể điểm xuất phát hay điểm tới)

==> Năm 1736, Leonhard Euler đã chứng minh rằng bài toán không có lời giải ==> Kết quả này là cơ sở phát triển Graph Theory

3. Lịch sử

Vào năm 1852, Francis Guthrie đưa ra bài toán bốn màu:

HỎI RẰNG

Liệu chỉ với bốn màu có thể tô màu một bản đồ bất kỳ sao cho KHÔNG có 2 nước nào cùng biên giới được tô cùng màu ?

==> Bài toán được như khai sinh ra Graph Theory, và nó được giải vào năm 1967 bởi Kenneth Appel và Wolfgang Haken

Tên	Ảnh	Năm sinh
Francis Guthrie		1831 - 1899
Kenneth Appel		1932 - 2013
Wolfgang Haken		1928 - ...