YOMEDIA
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
182
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.
AMBIENT/
Chủ đề:
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.
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
