Giới thiệu về EULER và bài toán

Tài liệu tham khảo cho các bạn học chuyên ngành. Dây chuyền: Một dây chuyền trong đồ thị không có định hướng là một dãy liên tiếp các cạnh, sao cho mỗi một cạnh có một đỉnh chung với cạnh tiếp theo. Chu trình: Một chu trình là một dây chuyền mà có ít nhất một cạnh cá đỉnh khởi đầu và đỉnh kết thúc trùng nhau.
Nội dung trích xuất từ tài liệu:
Giới thiệu về EULER và bài toánTrường Đại Học Khoa Học Tự Nhiên Khoa Công Nghệ Thông Tin Đồ án môn Lý Thuyết Đồ Thị : GVHD : Trương Mỹ Dung SVTH : Lê Tôn Vinh 0112124 Leâ Duy Chí 0112048Tổng quan về đồ thị Euler Phần I : GIỚI THIỆU VỀ EULER & BÀI TOÁNTổng quan về đồ thị Euler EULER Leonhard Euler (1707 - 1783)Tổng quan về đồ thị Euler Thành phố Basel - Thụy SĩTổng quan về đồ thị Euler Thành phố St – Petersburg - NgaTổng quan về đồ thị EulerBÀI TOÁN VỀ 7 CÂY CẦU 7 cây cầu ở Konigsburg - LithuaniaTổng quan về đồ thị Euler Mô hình hóaTổng quan về đồ thị Euler Biểu diễn bằng đồ thị D A B CTổng quan về đồ thị Euler Phần II : Các định nghĩa và ví dụTổng quan về đồ thị Euler Dây chuyền – Chu trình - Đường đi - Mạch Tính liên thông Bài toán Euler Đồ thị Euler Next>>Tổng quan về đồ thị EulerDây chuyền – Chu trình - Đường đi -Mạch Dây chuyền : Một dây chuyền trong đồ thị không có định hướng là một dãy liên tiếp các cạnh, sao cho mỗi một cạnh có một đỉnh chung với cạnh tiếp theo.Tổng quan về đồ thị EulerDây chuyền – Chu trình - Đường đi - Mạch Chu trình : Một chu trình là một dây chuyền mà có ít nhất một cạnh cá đỉnh khởi đầu và đỉnh kết thúc trùng nhau.Tổng quan về đồ thị Euler Ví Dụ : A E U1 U3 U5 U4 B D U6 U2 U8 C Trong hình trên ta có : + A U2 C U4 E U3 B là một dây chuyền của đồ thị + A U2 C U4 E U3 B U1 A là một đường đi của đồ thịTổng quan về đồ thị EulerDây chuyền – Chu trình - Đường đi - Mạch Đường đi : Đường đi là khái niệm dây chuyền trong đồ thị có hướng.Tổng quan về đồ thị EulerDây chuyền – Chu trình - Đường đi - Mạch Mạch : Mạch là khái niệm chu trình trong đồ thị có hướng .Tổng quan về đồ thị Euler U9 Ví Dụ : A U1 U3 U4 D E B U2 U6 U7 U5 C U8Trong hình trên ta có : + A U1 B U2 D U6 C U7 E là một đường đi của đồ thị + A U1 B U2 D U6 C U7 E U9 A là một mạch của đồ thịTổng quan về đồ thị Euler Tính Liên ThôngĐịnh nghĩa : Một đồ thị vô hướng gọi là liên thông nếu mọi cặp đỉnh của nó có đường nối với nhau.Tổng quan về đồ thị Euler Ví Dụ : A E U1 U3 U5 U4 B D U6 U2 U8 C Đồ thị trên liên thôngTổng quan về đồ thị Euler Bài toán Euler • Dây chuyền Euler • Chu trình Euler • Mạch Euler • Đường đi EulerTổng quan về đồ thị Euler Bài toán EulerDây chuyền Euler : Cho G là đồ thị vô hướng liên thông. Dây chuyền Euler là dây chuyền đi qua tất cả các cạnh trong đồ thị, mỗi cạnh đi qua đúng một lần.