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

Chia sẻ: Minh Dat Pham | Ngày: | Loại File: PPT | Số trang:42

0
121
lượt xem
36
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Giới thiệu về EULER và bài toán

  1. Trườ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í 0112048
  2. Tổng quan về đồ thị Euler Phần I : GIỚI THIỆU VỀ EULER & BÀI TOÁN
  3. Tổng quan về đồ thị Euler EULER Leonhard Euler (1707 - 1783)
  4. Tổng quan về đồ thị Euler Thành phố Basel - Thụy Sĩ
  5. Tổng quan về đồ thị Euler Thành phố St – Petersburg - Nga
  6. Tổng quan về đồ thị Euler BÀI TOÁN VỀ 7 CÂY CẦU 7 cây cầu ở Konigsburg - Lithuania
  7. Tổng quan về đồ thị Euler Mô hình hóa
  8. Tổng quan về đồ thị Euler Biểu diễn bằng đồ thị D A B C
  9. Tổng quan về đồ thị Euler Phần II : Các định nghĩa và ví dụ
  10. 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>>
  11. Tổng quan về đồ thị Euler Dâ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.
  12. Tổng quan về đồ thị Euler Dâ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.
  13. 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ị
  14. Tổng quan về đồ thị Euler Dâ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.
  15. Tổng quan về đồ thị Euler Dâ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 .
  16. Tổng quan về đồ thị Euler U9 Ví Dụ : A U1 U3 U4 D E B U2 U6 U7 U5 C U8 Trong 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ị
  17. 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.
  18. 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ông
  19. Tổng quan về đồ thị Euler Bài toán Euler • Dây chuyền Euler • Chu trình Euler • Mạch Euler • Đường đi Euler
  20. Tổng quan về đồ thị Euler Bài toán Euler Dâ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.
Đồng bộ tài khoản