CHƯƠNG 1 ĐẠI CƯƠNG VỀ ĐỒ THỊ
Bài toán bảy cây cầu Euler, còn gọi là Bảy cơ sở phát triển của Lý thuyết đồ thị cầu ở Königsberg (nay là Kaliningrad, Nga) bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu Bài toán đặt ra là 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). bài toán này là không có lời giải. Kết quả này là đó thay thế mỗi vùng đất bằng một điểm, gọi là đỉnh hoặc nút, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liên kết. Cấu trúc toán - Điểm xuất phát trùng với điểm đến: Đồ thị không được có đỉnh bậc lẻ- Điểm xuất phát và điểm đến tùy ý: Đồ thị không quá 2 đỉnh bậc lẻ.
GIỚI THIỆU
Lời giải bài toán bảy cây cầu Euler:
Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau học thu được được gọi là một đồ thị
Hiện nay chưa có quy tắc cần và đủ để kiểm tra xem một đồ thị có là Hamilton không. Các kết quả có được hiện nay chỉ là các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có đường đi Hamilton
• Đồ thị đủ luôn là đồ thị Hamilton. Với n lẻ và n ≥ 3 thì Kn có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung
• Giả sử G là đồ thị phân đôi với hai tập đỉnh X1, X2 và |X1| = |X2| = n. Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton
SLIDE BÀI GIẢNG
TRANG TỔNG HỢP LÝ THUYẾT ĐỒ THỊ TẠI ĐÂY