ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

Giáo dục đại cương,Toán rời rạc
  Đánh giá    Viết đánh giá
 19      479      0
Phí: Tải Miễn phí
Mã tài liệu
swvntq
Danh mục
Giáo dục đại cương,Toán rời rạc
Thể loại
ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
Ngày đăng
3/1/2014
Loại file
pdf
Số trang
13
Dung lượng
0.23 M
Lần xem
479
Lần tải
19
  DOWNLOAD

ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

HƯỚNG DẪN DOWNLOAD TÀI LIỆU

Bước 1:Tại trang tài liệu thuvienmienphi bạn muốn tải, click vào nút Download màu xanh lá cây ở phía trên.
Bước 2: Tại liên kết tải về, bạn chọn liên kết để tải File về máy tính. Tại đây sẽ có lựa chọn tải File được lưu trên thuvienmienphi
Bước 3: Một thông báo xuất hiện ở phía cuối trình duyệt, hỏi bạn muốn lưu . - Nếu click vào Save, file sẽ được lưu về máy (Quá trình tải file nhanh hay chậm phụ thuộc vào đường truyền internet, dung lượng file bạn muốn tải)
Có nhiều phần mềm hỗ trợ việc download file về máy tính với tốc độ tải file nhanh như: Internet Download Manager (IDM), Free Download Manager, ... Tùy vào sở thích của từng người mà người dùng chọn lựa phần mềm hỗ trợ download cho máy tính của mình  

NỘI DUNG TÀI LIỆU

ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

 

HÌNH ẢNH DEMO
Tài liệu ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON slide 1

Tài liệu ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON slide 2

Tài liệu ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON slide 3

Tài liệu ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON slide 4

Tài liệu ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON slide 5


Chỉ xem 5 trang đầu, hãy download Miễn Phí về để xem toàn bộ

CHƯƠNG IV
ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
4.1. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER.
Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố lời giải
“bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707-1783). Thành
phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc Nga) được chia thành bốn
vùng
ằng các
nhánh
sông Pregel, các
vùng này gồm hai
vùng bên bờ sông,
đảo
Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18, người ta xây
ảy chiếc cầu nối các vùng này với nhau.
B
B
D
A
D
A
C
C
G
Dân thành phố từng thắc mắc: “Có thể nào đi dạo qua tất cả bảy cầu, mỗi cầu chỉ
một lần thôi không?”. Nếu ta coi mỗi khu vực A, B, C, D như một đỉnh và mỗi cầu qua
lại hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị
G như hình trên.
Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần có thể được
phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong đa đồ thị G chứa
tất cả các cạnh?
4.1.1. Định nghĩa: Chu trình (t.ư. đường đi) đơn chứa tất cả các cạnh (hoặc cung) của
đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Euler. Một đồ
thị liên thông (liên thông yếu đối với đồ thị có hướng) có chứa một chu trình (t.ư. đường
đi) Euler được gọi là đồ thị Euler (t.ư. nửa Euler).
Thí dụ 1:
Đồ thị Eule
Đồ thị không nửa Eule
Đồ thị nửa Eule
54
Đồ thị Eule
Đồ thị nửa Eule
Điều kiện cần và đủ để một đồ thị là đồ thị Euler được Euler tìm ra vào năm 1736
khi ông giải quyết bài toán hóc búa nổi tiếng thời đó về bảy cái cầu ở Konigsberg và đây
là định lý đầu tiên của lý thuyết đồ thị.
4.1.2. Định lý: Đồ thị (vô hướng) liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh
của G đều có bậc chẵn.
Chứng minh:
Điều kiện cần: Giả sử G là đồ thị Euler, tức là tồn tại chu trình Euler P trong G. Khi đó
cứ mỗi lần chu trình P đi qua một đỉnh nào đó của G thì bậc của đỉnh đó tăng lên 2. Mặt
khác, mỗi cạnh của đồ thị xuất hiện trong P đúng một lần. Do đó mỗi đỉnh của đồ thị
đều có bậc chẵn.
4.1.3. Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình
đơn.
Chứng minh: Nếu G có cạnh bội hoặc có khuyên thì khẳng định của bổ đề là hiển
nhiên. Vì vậy giả sử G là một đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây
dựng theo quy nạp đường đi
v
v1
v2
......
trong đó v1 là đỉnh kề với v, còn với i  1, chọn vi+1 là đỉnh kề với vi và vi+1  vi-1 (có thể
chọn như vậy vì deg(vi)  2), v0 = v. Do tập đỉnh của G là hữu hạn, nên sau một số hữu
hạn bước ta phải quay lại một đỉnh đã xuất hiện trước đó. Gọi k là số nguyên dương đầu
tiên để vk=vi (0ii, vi+1, ..., vk-1, vk (= vi) là một chu trình đơn cần
tìm.
Điều kiện đủ: Quy nạp theo số cạnh của G. Do G liên thông và bậc của mọi đỉnh là
chẵn nên mỗi đỉnh có bậc không nhỏ hơn 2. Từ đó theo Bổ đề 4.1.3, G phải chứa một
chu trình đơn C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình Euler. Giả
sử C không đi qua tất cả các cạnh của G. Khi đó loại bỏ khỏi G các cạnh thuộc C, ta thu
được một đồ thị mới H (không nhất thiết là liên thông). Số cạnh trong H nhỏ hơn trong
G và rõ ràng mỗi đỉnh của H vẫn có bậc là chẵn. Theo giả thiết quy nạp, trong mỗi thành
phần liên thông của H đều tìm được chu trình Euler. Do G liên thông nên mỗi thành
55
phần trong H có ít nhất một đỉnh chung với chu trình C. Vì vậy, ta có thể xây dựng chu
trình Euler trong G như sau:
C
Bắt đầu từ một đỉnh nào đó của chu trình C, đi theo các cạnh của C chừng nào chưa gặp
phải đỉnh không cô lập của H. Nếu gặp phải đỉnh như vậy thì ta đi theo chu trình Eule
của thành phần liên thông của H chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của C cho
đến khi gặp phải đỉnh không cô lập của H thì lại theo chu trình Euler của thành phần liên
thông tương ứng trong H, ... Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát, tức là thu
được chu trình đi qua mỗi cạnh của đồ thị đúng một lần.
4.1.4. Hệ quả: Đồ thị liên thông G là nửa Euler (mà không là Euler) khi và chỉ khi có
đúng hai đỉnh bậc lẻ trong G.
Chứng minh: Nếu G là nửa Euler thì tồn tại một đường đi Euler trong G từ đỉnh u đến
đỉnh v. Gọi G’ là đồ thị thu được từ G bằng cách thêm vào cạnh (u,v). Khi đó G’ là đồ
thị Euler nên mọi đỉnh trong G’ đều có bậc chẵn (kể cả u và v). Vì vậy u và v là hai đỉnh
duy nhất trong G có bậc lẻ.
Đảo lại, nếu có đúng hai đỉnh bậc lẻ là u và v thì gọi G’ là đồ thị thu được từ G
ằng cách thêm vào cạnh (u,v). Khi đó mọi đỉnh của G’ đều có bậc chẵn hay G’ là đồ thị
Euler. Bỏ cạnh (u,v) đã thêm vào ra khỏi chu trình Euler trong G’ ta có được đường đi
Euler từ u đến v trong G hay G là nửa Euler.
4.1.5. Chú ý: Ta có thể vạch được một chu trình Euler trong đồ thị liên thông G có bậc
của mọi đỉnh là chẵn theo thuật toán Fleury sau đây.
Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc sau:
1. Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh cô lập (nếu có);
2. Không bao giờ đi qua một cầu, trừ phi không còn cách đi nào khác.
u
v
w
s
t
x
y
z
56

Nguồn: thuvienmienphi

 

Bạn phải gởi bình luận/ đánh giá để thấy được link tải

Nếu bạn chưa đăng nhập xin hãy chọn ĐĂNG KÝ hoặc ĐĂNG NHẬP
 
 

BÌNH LUẬN


Nội dung bậy bạ, spam tài khoản sẽ bị khóa vĩnh viễn, IP sẽ bị khóa.
Đánh giá(nếu muốn)
 BÌNH LUẬN

ĐÁNH GIÁ


ĐIỂM TRUNG BÌNH

0
0 Đánh giá
Tài liệu rất tốt (0)
Tài liệu tốt (0)
Tài liệu rất hay (0)
Tài liệu hay (0)
Bình thường (0)
Thành viên
Nội dung đánh giá

 
LINK DOWNLOAD

Do-THI-EULER-VA-Do-THI-HAMILTON.pdf[0.23 M]

File đã kiểm duyệt
     Báo vi phạm bản quyền
Pass giải nén (Nếu có):
thuvienmienphi.com
DOWNLOAD
(Miễn phí)

Tài liệu tương tự