BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT "Forum ĐH Toán K9 - Mái Nhà Tình Bạn


BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT "Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Tue Oct 26, 2010 5:15 pm
avatar
[Thành viên] - Admin
»♥(¯Administartor¯)♥«
»♥(¯Administartor¯)♥«
Tổng số bài gửi : 127
Points : 381
Được cám ơn : 5
Bị dụ dỗ ngày : 18/10/2010
Age : 26
Đến từ : Niềm đam mê

Bài gửiTiêu đề: BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT "
Xem lý lịch thành viên http://dhtoank9.4umer.com


Câu 1: Trình bày đầy đủ định nghĩa và các ví dụ về đường chu trình, chú trọng đặc biệt về đường chu trình Euler và Hamilton?
- Định nghĩa đường đi: Cho V0 và Vn là hai đỉnh của đồ thị . Một đường đi từ V0 đến Vn có chiều dài n là một dãy có (n+1) đỉnh và n cạnh bắt đầu từ đỉnh V0 và kết thúc tại Vn.
( v0,e1,v1,e2,…,vn-1,en,vn )
ei nối vi-1 với vi. Có thể vi = vj (i#j)
+ Đường đi từ v0 đến vn có thể được định hướng nhất định được gọi là đường định hướng.
+ Một đường đi từ v0 được gọi là sơ cấp nếu như vi # vj với "i # j.
+ Đường định hướng được gọi là định hướng sơ cấp nếu một đỉnh chỉ đi
qua một lần
- Định nghĩa chu trình :Chu trình (mạch) là đường có định hướng có độ dài khác không và không đi qua một cạnh quá một lần.
+ Chu trình (mạch) được gọi là sơ cấp từ v0 đến vn không đi quá 1 lần
ngoại trừ v.
- Định nghĩa đường Euler : Một đường được gọi là đường Euler đi từ v đến w nếu như đường đó chứa tất cả các đỉnh và các cạnh của đồ thị
- Định nghĩa chu trình Euler :Một chu trình được gọi là chu trình Euler là một chu trình chứa tất cả các đỉnh của đồ thị
- Định lý 1:Đồ thị G có chu trình Euler nếu và chỉ nếu G có tất cả các bậc là chẵn khác không.
- Định lý 2:Đồ thị G có đường Euler từ v đến w (v≠w) nếu và chỉ nếu G liên thông và có đúng hai đỉnh bậc lẻ


- Định nghĩa chu trình Hamilton : Là một chu trình sơ cấp và chứa tất cả các đỉnh của đồ thị
+ Đồ thị n đỉnh có chu trình Hamilton thì phải có n cạnh
* Lưu ý: Nếu đồ thị có chu trình Hamilton thì các đỉnh nằm trong chu trình đó điều là bậc hai
- Đường Halminton : nếu ta hủy đi một cạnh trong chu trình Halmiton thì sẽ nhận dược một đường Halmiton..
Ví dụ :
Cho quân mã đi trên bàn cờ vua sao cho nó đi qua mỗi ô đúng một lần (bài
toán mã đi tuần).
- Các Ví dụ về đường chu trình Euler và Hamilton:




Đồ thị trên có chu trình Euler nhưng không có chu trình Halminton.



Đồ thị trên vừa không có chu trình Euler vừa không có chu trình Halminton.





Đồ thị trên vừa có chu trình Euler vừa có chu trình Halminton.



Đồ thị này có chu trình Halminton nhưng không có chu trình Euler

- Định lý 3: Cho một đồ thị đầy đủ Kn với n lẻ và n ≥ 3 thì đồ thị G có
(n-1)/2 chu trình Hamilton từng đôi một không giao nhau
- Định lý 4: Cho G là một đồ thị đơn giản có đỉnh n lớn hơn bậc 3 nếu
δ(v) ≥ n/2 với mọi đỉnh v Î G thì G có chu trình Hamilton




Một số nhận xét:
1. Đồ thị có đỉnh có bậc ≤ 1 thì không có chu trình Hamilton.
2. Đồ thị có các đỉnh đều có bậc ≥ 2. Nếu có đỉnh nào có bậc bằng 2 thì mọi
chu trình Hamilton (nếu có) phải đi qua hai cạnh kề với đỉnh này.
3. Nếu trong đồ thị có đỉnh có ba đỉnh bậc 2 kề với nó thì đồ thị không có chu
trình Hamilton.
4. Nếu đỉnh a có hai đỉnh kề bậc 2 là b và c thì mọi cạnh (a, x), x Ï{b, c} sẽ
không thuộc bất kỳ chu trình Hamilton nào.
5. Đồ thị có đường đi vô hướng < a1 , a2 , ... , ak >. Với chỉ số k < n và các đỉnh
trên đường đi (trừ a1 và ak) đều có bậc 2 thì cạnh (a1, ak) sẽ không thuộc
bất kỳ chu trình Hamilton nào.
6. Đồ thị hai phần G = (V1,V2, F) với | V1 | ≠ | V2 | sẽ không có một chu trình
Hamilton nào



Number one


Tue Oct 26, 2010 5:20 pm
avatar
[Thành viên] - Admin
»♥(¯Administartor¯)♥«
»♥(¯Administartor¯)♥«
Tổng số bài gửi : 127
Points : 381
Được cám ơn : 5
Bị dụ dỗ ngày : 18/10/2010
Age : 26
Đến từ : Niềm đam mê

Bài gửiTiêu đề: Re: BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT "
Xem lý lịch thành viên http://dhtoank9.4umer.com

Do vẽ đồ thị hơi mất thời gian hihi, t đưa luôn link down về các bạn xem nha

http://www.mediafire.com/?2dgkjjf5jny

có vẫn đề gì thì pm lại cho tớ ha . . .




Number one


BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT "

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang
Trang 1 trong tổng số 1 trang
* Không dùng những ngôn từ thiếu lịch sự.
* Bài viết sưu tầm nên ghi rõ nguồn.
* Tránh spam nhảm không liên quan đến chủ đề.
Mong các bạn viết tiếng Việt có dấu.
Permissions in this forum:Bạn không có quyền trả lời bài viết
Đại Học Toán K9 :: Góc học tập :: Tài liệu học tập :: Lý thuyết đồ thị-
Bài Viết Mới Bài viết mớiKhông Có Bài Viết Mới Không có bài viết mớiDiễn đàn đã bị khóa Diễn đàn đã bị khóa
Đại Học Toán K9 _ Đại Học Hải Phòng
@ 2010 ĐH Hải Phòng dhtoank9.4umer.com
Hãy cùng nhau vun đắp những kỷ niệm đẹp nhất thời sinh viên
Xem tốt nhất với Firefox và màn hình > 1280x1024
Get Firefox Now Get Windows Media Player Now
Free forum | © phpBB | Free forum support | Liên hệ | Report an abuse | www.sosblogs.com