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

Thêm vào BST

Báo xấu

179
lượt xem 39
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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
Tổng quan về đồ thị Euler Phần I : GIỚI THIỆU VỀ EULER & BÀI TOÁN
Tổ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 - Nga
Tổng quan về đồ thị Euler BÀI TOÁN VỀ 7 CÂY CẦU 7 cây cầu ở Konigsburg - Lithuania
Tổng quan về đồ thị Euler Mô hình hóa
Tổng quan về đồ thị Euler Biểu diễn bằng đồ thị D A B C
Tổ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ị 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.
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.
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ị 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.
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 .
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ị
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ông
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
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.