LỜI NÓI ĐẦU
Các bài toán trên đồ thị có nhiều ứng dụng trong các lĩnh vực khác nhau
như mạng thông tin, đồ họa, ứng dụng lập kế hoạch Các bài toán đặt ra trong
các ứng dụng như vậy thường có cơ sở dữ liệu lớn nên việc rút ngắn thời gian
tính toán để trả lời một câu truy vấn có ý nghĩa thực tiễn cao. Ngoài ra trong
thực tế, các đồ thị được sử dụng trong các bài toán có thể liên tục thay đổi
theo thời gian, ví dụ như các đỉnh hay các cạnh của nó có thể được thêm vào
hay xóa đi (đồ thị động), hoặc thay đổi độ dài, lượng thông qua
Mỗi lần có một thay đổi như vậy cấu trúc dữ liệu của bài toán, thông tin
về các đỉnh cũng như các cạnh cũng bị thay đổi theo. Trong khi đó yêu cầu đặt
ra là phải liên tục trả lời các câu hỏi về thông tin trong đồ thị như tính liên
thông của đồ thị, rừng bao trùm tối thiểu, 2 đỉnh bất kỳ có nằm trên cùng một
cây bao trùm tối thiểu hay không, đường đi ngắn nhất Một cách tiếp cận để
giải quyết các bài toán trên đồ thị động là sử dụng các cấu trúc dữ liệu và thuật
toán truyền thống trong đồ thị tĩnh và chạy lại chúng mỗi khi có sự thay đổi
trong đồ thị. Tuy nhiên cách tiếp cận như vậy không tận dụng được thông tin
của đồ thị trước khi thay đổi dẫn đến độ phức tạp để trả lời một câu truy vấn
về đồ thị sau mỗi bước thay đổi là lớn.
Trong đồ án tốt nghiệp này, em xin trình bày các nghiên cứu, khảo sát
thực nghiệm và ứng dụng một số cấu trúc dữ liệu được đưa ra gần đây nhằm
giúp quản lý các đồ thị động một cách mềm dẻo. Dựa trên các cấu trúc dữ liệu
này, một số bài toán trên đồ thị động như kiểm tra tính liên thông, xây dựng
cây bao trùm, tìm đường đi ngắn nhất được giải quyết với độ phức tạp thời
gian nhỏ hơn so với việc chạy lại các thuật toán truyền thống trên đồ thị tĩnh
mỗi khi có sự thay đổi trong đồ thị.
1
Đề tài của đồ án là “Nghiên cứu, cài đặt thuật toán giải bài toán lập
hành trình người đưa thư và ứng dụng” được đặt ra với mục tiêu:
• Nghiên cứu thuât toán giải và xây dựng ứng dụng giải quyết bài toán
tìm hành trình tối ưu nhất cho người đưa thư, báo với các điểm đưa
thư, báo cố định hoặc thay đổi tuỳ theo nhiệm vụ phân công.

trên bản đồ cụ thể.
Sau 6 tháng thực hiện đế nay em đã xây dựng được chương trình trên
ngôn ngữ C#, kết hợp với cơ sở dữ liệu MapInfo mô phỏng được các tác
nghiệp trên bản đồ. Chương trình có thể sử dụng tại các Trung tâm phát hành
báo chí tại các quận nội thành Hà Nội.
Trong quá trình thực hiện đồ án tốt nghiệp em xin chân thành cảm ơn
thầy giáo đã tận tình chỉ bảo để em có thể hoàn thành nhiệm vụ.
3
CHƯƠNG 1: TÌM HIỂU VỀ PHẦN MỀM MAPINFO 6.0
1.1.Cài đặt phần mềm MapInfo 6.0:
* Những yêu cầu về hệ thống:
Để đảm bảo cho phần mềm MapInfo 6.0 có thể chạy ổn định trên máy
tính trước khi cài đặt phần mềm phải chắc chắn đảm bảo được các yêu cầu
sau đây:
- Máy tính tối thiểu là 586 với bộ nhớ tối thiểu 32Mb RAM.
- Màn hình cần có màn hinh VGS hoặc các màn hình có độ phân giải cao
hơn.
- Môi trường hệ thống: đòi hỏi môi trường hệ thống là Windows 95/98
hoặc Windows NT 4.0
1.2. Tổ chức thông tin bản đồ trong MapInfo:
1.2.1. Tổ chức thông tin theo các tập tin:
MapInfo tổ chức tất cả các thông tin bao gồm dữ liệu không gian và dữ
liệu phi không gian dưới dạng bảng cơ sở dữ liệu(Table). Các thông tin không
gian và thông tin thuộc tính này MapInfo được liên kết với nhau một cách chặt
chẽ, không thể tách rời thông qua chỉ số ID, được lưu trữ và quản lý chúng
cho cả hai loại dữ liệu. Mỗi một bảng dữ liệu là một nhóm các tệp với các
phần đuôi mở rộng khác nhau:
- Filename.tab: mô tả cấu trúc của bảng dữ liệu.
- Filename.dat: hoặc filename.dbf hoặc filename.wks hoặc filename.xls
bao gồm dữ liệu kiểu bảng xếp thành hàng, cột, những dữ liệu được

lý bản đồ như nhãn tiêu đề, ghi chú.
Ví dụ: một lớp bao gồm các vùng với viền bao là ranh giới hành chính, tệp
thứ hai gồm các ký hiệu tuyến. Thể hiện đường giao thông, lớp thứ ba ký hiệu thể
hiện tại vị trí các thành phố thị xã, lớp thứ tư thể hiện địa danh của các thành phố
đó. Bằng cách đặt các lớp thông tin này chống lên nhau. Chúng ta đã thấy xuất
hiện một bản đồ. Cứ như vậy cùng một lúc có thể hiển thị một, hai hoặc nhiều
lớp.
Với các bản đồ được xây dựng thành từng lớp như vậy có thể dễ dàng sắp
xếp, thêm hay bớt các lớp thông tin để phù hợp với nội dung và mục đích của bản
đồ cần thành lập.
1.3. Thực đơn và các chức năng cơ bản của MapInfo:
(đọc tài liệu tham khảo”giáo trình MapInfo-Hướng dẫn sử dụng phần mềm
Mapinfor 6.0”)
1.4. Số hoá bản đồ:
1.4.1. Trước khi số hoá bản đồ:
Trước khi số hoá bản đồ cần đặt cho bản đồ một thông số tham chiếu.
Trên bản đồ số hoá phải có các tham chiếu cần thiết nếu không bản đồ số hoá
tạo ra sẽ không chính xác. Khi đăng ký toạ độ cần phải đặt những điểm khống
chế bắt buộc ít nhất là 4 điểm và có một điểm kiểm tra(toạ độ này đựơc nhập
khi MapInfor yêu cầu). Mapinfor sẽ tính toán các thông số toạ độ từ bản đồ
này, và sẽ tính toán các lỗi, nếu thoả mãn yêu cầu thì tiếp tục các công việc
tiếp theo, ngược lại thì phải làm lại từ đầu, sai số càng cao thì bản đồ càng
không chính xác
1.4.2. Bắt đầu số hoá:
6
Chọn file trên thanh menu chọn Open:
Chọn RasterImage
Chọn file bản đồ cần số hoá:
Chọn register sau đó xuất hiện hộp
thoại sau:

>=: lớn hơn hoặc bằng.
<=: nhở hơn hoặc bằng.
_: dấu gộp cho một ký tự.
%: dấu gộp cho nhiều ký tự.
b) ký tự, số, ngày tháng năm:
- Khi nhập riêng những chuỗi ký tự, số và ngày tháng trong biểu thức cần tuân
theo các nguyên tắc trình bày dưới đây:
* Với những chuỗi ký tự: khi nhập các mẫu tin ký tự vào trong một biểu thức thì
phải nhập chúng trong dấu ngoặc kép.
* Với số (numbers): khi nhập giá trị đặc biệt bằng số không sử dụng dấu phảy,
dấu đô la, hoặc bất kỳ những chữ số nào khác hơn chữ số. Có thể sử dụng mũ e
để thực hiện
* Với ngày tháng năm: năm thì có thể sử dụng hai hoặc bốn chữ số nếu muốn,
ngày tháng năm cách nhau một dấu ”-” hoặc “/”. Nếu năm không chỉ rõ thì nó sẽ
mặc định đồng hồ máy. Chú ý phải được cho vào dấu nháy kép. Ví dụ:
MM/dd/yy: “09/08/2009”
MM/dd/yyyy: “09/08/2009”
9
yy/MM/dd: “2009/08/09”
dd-MMM-yy: “09/08/2009”
c) Một số hàm toán học thông dụng:
Ads(num): cho giá trị tuyệt đối của một số.
Cos(num): cho cosin của một số, số đó phải là Radian.
Int(num): cho phần số nguyên của một số.
Maximum(num,num): cho số lớn hơn của 2 chữ số.
Curdate(): cho ngày tháng hiện thời.
Day(date): cho phần ngày.
Month(date): cho phần tháng.
Weekday(date): cho ngày của tuần (1-7)(1- là chủ nhật).
Year(date): cho năm.

để trống nếu như không tính.
Chú ý: Những cột hàm tổng thể thì không được liệt kê trong lựa chọn này, các
hàm tổng thể bao gồm:
Count(*); Sum (< expression>); avg (<expression > );
max(<expression>); min(<expression>)
Order by columns thứ tự những dãy
Cho phép phân loại những bảng kết quả nếu vào tên một cột hoặc nhiều cột theo
thứ tự thì Mapinfor sẽ sắp xếp những dòng trong bảng kết quả. Theo mặc định thì
Mapinfor sẽ sắp xếp theo thứ tự tăng dần bằng từ khoá Desc.
B3: Mapinfor tự động lựa chọn tất cả các dòng trong bảng kết quả. Như vậy sau
khi thực hiện có những toán tử với những dòng của toàn bộ bảng, nhưng có thể
thay đổi màu khác bằng việc chọn Options / region cũng có thể copy những
dòng lựa chọn. Thông thường bất kỳ sự thay đổi nào trong bảng kết quả thì sẽ
được tự động cập nhật cho bảng gốc (cơ sở) như xoá các hàng trong bảng kết
quả thì các hàng đó sẽ bị xoá trong bảng gốc, tuy nhiên đối với những câu hỏi
tính tổng số thì có thể thay đổi mà không làm thay đôi đến bảng gốc.
B4: Chọn file > save as nếu như muốn sao chép để sử dụng lâu dài và nếu như
không cất giữ thì khi thoát khỏi mainfor sẽ bị xoá.
Việc lựa chọn những cột được đưa ra trong bảng kết quả
12
Việc lựa chọn những cột được dựa vào những tính toán mà những cột đó cần thể
hiện. Những cột lựa chọn có thể là cột tạm thời, cột đặc biệt trên bảng cơ sở . Để
có thể đưa ra các cột qua một mệnh đề, thực hiện theo một thao tác sau:
1. Chọn cột có dữ liệu đưa ra
2. Tạo một biểu thức. Một biểu thức bao gồm một hoặc hơn một
cột có thể, một biểu thức bao gồm sự kết hợp giữa các toán tử và cũng
có thể nhiều hàm và những toán tử khác có thể sử dụng trong việc tạo
ra các biểu thức.
3. Có thể gắn bí danh cho cột thể hiện do biểu thức tạo ra, để
gắn bí danh thì nhập tên một bí danh trong dấu nháy kép (“ “) có thể

14
+ Dùng mô hình đối tượng MapWtreme 2005 để xây dựng bản đồ trong
ứng dụng của bạn.
2.1.2. Tables:
Các đối tượng bảng chứa đựng dữ liệu mà bạn muốn hiển thị trên bản
đồ. Các bảng nắm các hàng và các cột về thông tin mô tả đối tượng bao gồm
đối tượng geometry(hình học) , kiểu(style), và các thuộc tính(attributes).
MapXtreme 2005 hỗ trợ các bảng từ nhiều nguồn dữ liệu lớn khác nhau bao
gồm các bảng định dạng MapInfo.TAB, hệ thống quản lý cơ sở dữ liệu quan
hệ (RDBMS), dBase, MS Access, grid, seamless, views, WMS và ADO.NET.
Kiểu của bảng là sẵn có trong lớp TableInfo. Các bảng được mở và đóng
thông qua Catalog trong không gian tên MapInfo.Data.
2.1.3. Layers:
Các bản đồ được trang trí bởi các layer. Các layer chứa đựng các đối
tượng bản đồ. Và việc hiểu thứ tự của các lớp layer là rất quan trọng. Lớp
layer cuối cùng được vẽ đầu tiên và lớp đầu tiên được vẽ sau cùng. Lớp layer
chứa đựng các đối tượng. Các đối tượng này sẽ tô mờ các đối tượng của lớp
khác đặt phía dưới. Ví dụ một lớp các đối tượng vùng được đặt ở dưới lớp các
đối tượng điểm.
15
Các lớp layer MapXtreme 2005 có thể trình bày nhiều hơn các đối
tượng. Các lớp layer có thể là các ảnh raster hoặc grid, các mảnh bản đồ, chứa
đựng các nhãn hoặc các đối tượng feature mà người dùng vẽ. Interface chính
là ImapLayer.
2.1.4. Feature:
Các đối tượng (feature) được mô tả bởi đối tượng geometry, kiểu(style),
nguồn dữ liệu, khoá và các thuộc tính của chúng. Một đối tượng đặc trưng cho
một hàng trong bảng. Các đối tượng hình học (geometry) hỗ trợ bao gồm các
đối tượng khép kín bao trùm cả một khu cho sẵn(như: polygon, Multipoint) và
các đối tượng dạng đường kéo dài với một khoảng cách cho trước(như: Curve,

Mô hình đối tượng là sự lắp ghép của rất nhiều không gian tên. Dưới
đây là một vài không gian tên hay dùng trong MapXtreme 2005.
 MapInfo.Data
 MapInfo.Data.Find
 MapInfo.Engine
 MapInfo.Geometry
 Mapinfo.Mapping
 MapInfo.Raster
 MapInfo.Styles
 MapInfo.Tools…
2.2.1.1. Không gian tên MapInfo.Data:
Không gian tên này chứa các lớp và giao diện cung cấp MapInfo.Data.
Mô hình đối tượng này có nhiều lớp khác nhau để truy cập dữ liệu, phụ thuộc
vào kiểu định dạng dữ liệu được lưu mà sử dụng các lớp khác nhau để truy
cập dữ liệu.
2.2.1.2. Không gian tên MapInfo.Data.Find:
Không gian tên này chứa đựng các lớp dùng cho việc tìm kiếm thông
qua dữ liệu. Nó sẽ làm cho các thao tác tìm kiếm trở nên thuận tiện và dễ dàng
hơn bằng cách xác định rõ một bảng và cột muốn thực hiện tìm kiếm.
2.2.1.3. Không gian tên MapInfo.Engine:
Không gian tên này chứa tất cả các lớp trực tiếp liên quan tới các tính
năng trọng tâm để điều khiển toàn bộ các ứng dụng dựa trên MapXtreme
2005. Nó bao gồm cả lớp Session chính là điểm bắt đầu cho các ứng dụng
MapXtreme.
19
2.2.1.4. Không gian tên MapInfo.Geometry
Không gian tên này là một hệ đẳng cấp có thể mở rộng dựa trên các tiêu
chuẩn OCG, các thao tác với hệ toạ độ, và xử lý đối tượng.
2.2.1.5. Không gian tên MapInfo.Mapping:
Không gian tên này chứa các lớp, các interface và các liệt kê cho việc

2.3. Các đối tượng không gian và hệ toạ độ trong MapXtreme 2005:
2.3.1. Giới thiệu tổng quan về không gian tên MapInfo.Geometry:
Không gian tên MapInfo.Geometry được dùng cho việc tạo, điều khiển
các đối tượng geometry và các hệ toạ độ nơi mà chúng được dùng. Các đối
tượng Geometry được dùng trong các bản đồ để thể hiện các điểm đơn như
các thành phố, các đường bao, như các đường bao của các nước(thể hiện bằng
22
các đối tượng MultiCurve), và các vùng như các nước(thể hiện băng đối
tượng MultiCurve).
Các lớp, các interface và các bộ liệt kê trong không gian tên
MapInfo.Geometry định nghĩa các kiểu thể hiện các đối tượng geometry và
các hệ toạ độ được dùng trong việc hiển thị các đặc trưng địa lý trên bản đồ.
Các interface cho phép bạn tạo và chỉnh sửa các đối tượng geometry.
2.3.2. Các đối tượng Geometry:
Lớp Geometry cho phép bạn tạo, chỉnh sửa và điều khiển các đối tựơng
geometry, các lớp mà thừa kế từ lớp Geometry này và thể hiện các kiểu của
các đối tượng Geometry bao gồm: Point, MultiPoint, Polygon, MultiPolygon,
CurveSegment, LineString và Ring. Ngoài ra còn có các lớp sau cũng được kế
thừa từ lớp Geometry: Rectangle, RoundedRectangle, Ellipse, LegacyArc, và
LegacyText. Lớp Geometry thể hiện mức độ cao nhất của mô hình đối tượng
MapInfo Geometry.
23
Tất cả các đối tượng geometry trong MapXtreme 2005 được tạo ra với
hệ toạ độ xác định và không thể bị thay đổi. Nếu bạn cần thay đổi hệ toạ độ
của một đối tượng bạn cần tạo ra một bản sao của chính đối tượng đó trong
một hệ toạ độ mới.
Tất cả các đối tượng Geometry chứa đựng một phương thức cho việc
truy lại một interface để chỉnh sửa thay thế đối tượng trong Edit Mode.
Ví dụ: người dùng có thể tạo một đối tượng MultiPolygon và sau đó chỉnh sửa
nó. Nếu người dùng không vô ý di chuyển một nút của đường vòng trong ra

chỉ là một Line String.
• Ring: Một đối tượng đường cong tròn là một tập hợp các đoạn đường
cong mà đặt sát và kề nhau.
• Polygon: Một đối tượng Polygon là một đối tượng lắp ghép của các
đường cong tròn, một đa giác phải có ít nhất một đường cong tròn đơn mà
định nghĩa đường biên phía ngoài của đa giác.
2.3.3. Các hệ toạ độ:
Các hệ toạ độ mô tả một vùng nơi mà một đối tượng riêng biệt hoặc
một tập các đối tượng cư trú. Hệ toạ độ cho phép bạn phát hoạ, xác định các
điều kiện của đối tượng hoặc một tập các đối tượng được mô tả. Lớp
CoordSys chứa các phương thức, thuộc tính và các interface cho phép bạn tạo,
thực hiện các thao tác chỉnh sửa hệ toạ độ.
25

Trích đoạn Thuật toán tìm chu trình Euler: Mô hình bài toán thực tế: Thiết kế chương trình:

---