Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 6

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 56 | FileSize: M | File type: PDF
of x

Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 6. Bài giảng Toán học tổ hợp và cấu trúc rời rạc Chương 6 Các bài toán về đường đi trình bày các nội dung chính như: Tìm đường đi ngắn nhất, đồ thị Euler, đồ thị Hamilton,...Mời các bạn cùng tham khảo!. Cũng như những thư viện tài liệu khác được thành viên chia sẽ hoặc do sưu tầm lại và chia sẽ lại cho các bạn với mục đích nghiên cứu , chúng tôi không thu tiền từ người dùng ,nếu phát hiện nội dung phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho website ,Ngoài thư viện tài liệu này, bạn có thể download tài liệu, bài tập lớn phục vụ tham khảo Một số tài liệu tải về mất font không xem được, thì do máy tính bạn không hỗ trợ font củ, bạn tải các font .vntime củ về cài sẽ xem được.

https://tailieumienphi.vn/doc/bai-giang-toan-hoc-to-hop-va-cau-truc-roi-rac-chuong-6-w1obuq.html

Nội dung


Chương 6

CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI

Nội dung
1. Tìm đường đi ngắn nhất
2. Đồ thị Euler
3. Đồ thị Hamilton

2

1. TÌM ĐƯỜNG ĐI NGẮN
NHẤT

3

Định nghĩa
Định nghĩa. Cho G = (V,E) là đồ thị có trọng số. Với
H  G thì trọng lượng của H là tổng trọng lượng của
các cạnh của H.

w(H)   w(e)
eH

 Nếu H là đường đi, chu trình, mạch thì w(H) được

gọi là độ dài của H.
 Nếu mạch H có độ dài âm thì H được gọi là mạch

âm.
 Khoảng cách giữa 2 đỉnh u và v là độ dài ngắn

nhất của các đường đi từ u đến v.
4

Ma trận khoảng cách
Định nghĩa. Cho đồ thị G = (V, E), V = {v1,v2,…,vn}
có trọng số. Ma trận khoảng cách của G là ma
trận D= (dij) xác định như sau:
0
khi i  j

dij   w(v i v j ) khi vi v j  E

khi vi v j  E


Nhận xét. Mọi đồ thị được hoàn toàn xác định bởi
ma trận khoảng cách.

5

1116930

Tài liệu liên quan


Xem thêm