1
Ths. Nguyễn Khắc Quốc
IT.Deparment – Tra Vinh University
BÀI GIẢNG MÔN
LÝ THUYẾT ĐỒ THỊ
ThS. Nguyễn Khắc Quốc 2
Chương 1
ĐỒ THỊ
- Lý thuyết đồ thị là một ngành khoa học được phát triển
từ lâu - có nhiều ứng dụng hiện đại.
- Những ý tưởng cơ bản được đưa ra từ thế kỷ 18 bởi
nhà toán học Thụy Sĩ tên là Leonhard Euler.
- Giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng.
Dùng để giải các bài toán trong nhiều lĩnh vực:
+ Xác định xem có thực hiện một mạch điện trên
một bảng điện phẳng được không.
+ phân biệt hai hợp chất hóa học có cùng công
thức phân tử nhưng có cấu trúc khác nhau
Đồ thị với các trọng số dùng để giải các bài toán:
+ Tìm đường đi ngắn nhất.
+ Lập lịch thi đấu
+ Chia kênh cho các đài truyền hình.
ThS. Nguyễn Khắc Quốc 3
1.1. ĐỊNH NGHĨA VÀ THÍ DỤ.
Phân loại:
+ Theo đặc tính
+ Số các cạnh nối các
cặp đỉnh của đồ thị.
Đồ thị vô hướng
Đồ thị có hướng
-Đồ thị là một cấu trúc rời
rạc gồm các đỉnh và các
cạnh (vô hướng hoặc có
hướng) nối các đỉnh đó.
ThS. Nguyễn Khắc Quốc 4
1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt).
Ứng dụng:
- Biểu diễn sự cạnh tranh các loài trong một môi
trường sinh thái,
- Biểu diễn ai có ảnh hưởng lên ai trong một tổ
chức nào đó,
- Biểu diễn các kết cục của cuộc thi đấu thể thao.
- Tính số các tổ hợp khác nhau của các chuyến
bay giữa hai thành phố trong một mạng hàng không,
- Đi tham quan tất cả các đường phố của một
thành phố sao cho mỗi đường phố đi qua đúng một lần,
- Tìm số các màu cần thiết để tô các vùng khác
nhau của một bản đồ.
ThS. Nguyễn Khắc Quốc 5
1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt).
1.1.1. Định nghĩa:
Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V
mà các phần tử của nó gọi là các đỉnh và một tập E mà
các phần tử của nó gọi là các cạnh, đó là các cặp không
có thứ tự của các đỉnh phân biệt.