Đại Học Toán K9
Chúc mừng ngày nhà giáo Việt Nam 20/11
|
| | |
| BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT " |  |
| |  Tue Oct 26, 2010 5:15 pm | | [Thành viên] - Admin
»♥(¯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 : 33
Đến từ : Niềm đam mê
 |
| |  Tiêu đề: BÀI TẬP LỚN LÝ THUYẾT ĐỒ THỊ _ " PHẦN LÝ THUYẾT " | |
| |  |  |  | |
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
| |  |  |  |
|
|
|
