ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
- - - - - -
Nguyễn Thị Anh Thi
MỘT SỐ VẤN ĐỀ VỀ MẠNG LƯỚI
TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN
Ngành : Công nghệ thông tin
Chuyên ngành : Hệ thống thông tin
Mã số : 60.48.05
LUẬN VĂN THẠC SĨ
1.3.1 Các mô hình dữ liệu 19
1.3.1.1 Mô hình dữ liệu khái niệm 21
1.3.1.2 Mô hình dữ liệu logic 23
1.3.1.3 Mô hình dữ liệu vật lý 25
1.3.2 Ngôn ngữ truy vấn cho đồ thị 28
Chương 2 30
MỘT SỐ THUẬT TOÁN TÌM KIẾM TRONG MẠNG LƯỚI KHÔNG
GIAN 30
2.1 Phát biểu bài toán 30
2.2 Thuật toán Dijkstra 31
2.3 Thuật toán Bellman-Ford 37
2.4 Thuật toán A* 39
2.5 Thuật toán Floyd 45
- 2 -
2.6 Kết luận 50
Chương 3 53
PHÁT TRIỂN ỨNG DỤNG 53
3.1 Phát biểu bài toán 53
3.1.1 Lý do xây dựng chương trình 53
3.1.2 Mục tiêu, nhiệm vụ của chương trình 53
3.2 Công cụ xây dựng chương trình 54
3.2.1 MapInfo Professional 54
3.2.2 Thư viện hỗ trợ xây dựng ứng dụng bản đồ MapXtreme 57
3.2.3 Hệ quản trị cơ sở dữ liệu Access 60
3.2.4 Ngôn ngữ lập trình Microsoft Visual C#.NET 60
3.3 Dữ liệu sử dụng trong chương trình 61
3.3.1 Mô tả chi tiết các bảng dữ liệu trong MapInfo 61
3.3.2 Thiết kế dữ liệu trong Access 61
3.4 Thiết kế, đặc tả các chức năng 62
chọn tốt nhất
CPU Central Processing Unit
Đơn vị xử lý trung
tâm
DBMS Database Management System
Hệ quản trị cơ sở
dữ liệu
DDL Data Definition Language
Ngôn ngữ định
nghĩa dữ liệu
DML Data Manipulation Language
Ngôn ngữ xử lý dữ
liệu
DXF Drawing Exchange Format
ER Entity Relationship Quan hệ thực thể
ESRI Environmental Systems Research Institute
Viện nghiên cứu hệ
môi trường
GIS Geographic Information Systems
Hệ thống thông tin
địa lý
MIF MapInfo Interchange Format
Định dạng
MapInfo
NPC Non-Polynomial Complete
Lớp bài toán NP-
đầy đủ
OLE Object Linking and Embedding
Nhúng và liên kết
đối tượng
DANH MỤC HÌNH VẼ
Hình 1.1 Các thành phần của GIS 7
Hình 1.2 Phần cứng GIS 8
Hình 1.3 Các nhóm chức năng trong GIS 9
Hình 1.4 Minh họa về mô hình hóa 11
Hình 1.5 Biến đổi dữ liệu thành thông tin 12
Hình 1.6 Ba mô hình quan niệm của đối tượng không gian 13
Hình 1.7 Các mô hình dữ liệu không gian 15
Hình 1.8 Biểu diễn Raster 16
Hình 1.9 Các thành phần hình học cơ sở 17
Hình 1.10 Biểu diễn bản đồ vectơ 18
Hình 1.11 Các mức biểu diễn thông tin trong cơ sở dữ liệu 20
Hình 1.12 Mô hình đồ thị của hệ thống mạng lưới sông ngòi 22
Hình 1.13. Đồ thị mô hình của mạng lưới đường phố 22
Hình 1.14 Mô hình mạng lưới đường tàu hỏa 24
Hình 1.15. Ba cách biểu diễn đồ thị 25
Hình 2.1 Đồ thị minh họa thuật toán Dijkstra 33
Hình 2.2 Đồ thị minh họa thuật toán Bellman – Ford 37
Hình 2.3 Đồ thị minh họa thuật toán Floyd 47
Hình 3.1 Biểu đồ hoạt động chức năng tìm đường đi ngắn nhất 64
Hình 3.2 Giao diện chính của chương trình sau khi khi khởi động 68
Hình 3.3 Bản đồ mạng lưới tuyến xe buýt Hà Nội khi xem tổng thể 69
Hình 3.4 Cửa sổ bật tắt các lớp bản đồ 69
Hình 3.5 Minh họa ghi chú động trên bản đồ 70
Hình 3.6 Minh họa kích chọn điểm đi và điểm đến 70
Hình 3.7 Minh họa kết quả đường đi tìm được 71
nghệ thông tin địa lý (công nghệ GIS) được tiếp cận từ nhiều hướng khác nhau
và do đó cũng có nhiều định nghĩa khác nhau về GIS.
Cơ sở dữ liệu không gian là thành phần cốt lõi trong GIS, trong đó cơ sở
dữ liệu mạng lưới không gian chiếm vị trí quan trọng trong cơ sở dữ liệu không
gian. Hiện nay, mạng lưới không gian đang được triển khai rộng rãi trong các
ứng dụng quan trọng trên thực tế như lập kế hoạch vận chuyển, điều khiển giao
- 6 -
thông đường hàng không, các tiện ích nước, điện và gas, mạng lưới điện thoại và
quản lý kênh tưới tiêu,…
Trên đây đã điểm qua tầm quan trọng của hệ thông tin địa lý, đặc biệt là
mạng lưới cơ sở dữ liệu không gian đã cho ta thấy rõ tính cần thiết cũng như
tính thời sự của vấn đề, đồng thời có ý nghĩa khoa học và thực tiễn. Vì thế, tôi
đã thực hiện đề tài luận văn: “Một số vấn đề về mạng lưới trong cơ sở dữ liệu
không gian”.
Mục tiêu đề tài là tìm hiểu về mạng lưới cơ sở dữ liệu không gian trong hệ
thống thông tin địa lý cùng với các thuật toán áp dụng trong đồ thị. Đề tài cũng
bước đầu xây dựng một chương trình tìm kiếm đường đi tối ưu cho hành khách
tham gia trong mạng lưới tuyến xe buýt cụ thể ở Hà Nội nhằm giảm bớt lưu
lượng giao thông trên đường phố, giúp người đi xe buýt lựa chọn được tuyến xe
buýt phù hợp cho mình.
Bố cục của luận văn bao gồm phần mở đầu, phần kết luận và ba chương
nội dung được tổ chức như sau:
Chương 1: Tổng quan về hệ thông tin địa lý
Chương này trình bày tổng quan về hệ thống thông tin địa lý bao gồm các
thành phần, chức năng và các ứng dụng của GIS. Hơn nữa, đề cập đến một số
vấn đề về cơ sở dữ liệu mạng lưới không gian, các mô hình mạng lưới không
gian và kiến trúc cơ sở dữ liệu, ngôn ngữ truy vấn,…
Chương 2: Một số thuật toán tìm kiếm trong mạng lưới không gian
Trong chương này tập trung vào một số thuật toán xử lý truy vấn phân
thiết về thông tin đã làm cho công nghệ GIS càng ngày được quan tâm hơn.
Có nhiều cách tiệm cận khác nhau khi định nghĩa GIS. Nếu xét dưới góc
độ hệ thống, thì GIS có thể được hiểu như một hệ thống gồm năm thành phần chính
(hình 1.1): con người, phương pháp, phần cứng, phần mềm tin học và dữ liệu [1].
Hình 1.1 Các thành phần của GIS
- 8 -
- Con người: là chuyên viên tin học, các chuyên gia về các lĩnh vực khác
nhau, chuyên gia GIS, thao tác viên GIS, phát triển ứng dụng GIS.
- Dữ liệu: là thành phần quan trọng nhất trong hệ thống GIS, chiếm
khoảng 70% giá thành sản phẩm. Dữ liệu thống kê gắn theo các hiện tượng tự
nhiên với mức độ chính xác khác nhau. Hệ thống thước đo của chúng bao gồm
các biến tên, số thứ tự, khoảng và tỷ lệ. Ngoài bốn loại biến dữ liệu này, các hệ
GIS còn phân chia dữ liệu thành hai loại khác nhau:
+ Dữ liệu không gian (spatial): là thông tin về vị trí của các đối tượng
trong thế giới thực trên mặt đất theo một hệ quy chiếu nhất định. Thực thể
không gian có thể cấu trúc theo hai cách: cấu trúc dạng vectơ và cấu trúc
dạng raster.
+ Dữ liệu phi không gian (non-spatial): còn gọi là dữ liệu thuộc tính, là
những số hiệu, bảng biểu mô tả tính chất, đặc trưng của dữ liệu không
gian. Nó được biểu thị dưới dạng những con số hoặc chữ mô tả số lượng,
tính chất, thông số liên quan đến các đối tượng đó trên bản đồ.
Dữ liệu phi không gian được kết nối logic với dữ liệu không gian. Sự kết
nối này là cơ sở để xác định chính xác các thông tin của đối tượng địa lý và thực
hiện phép phân tích tổng hợp trong hệ thống GIS. Mỗi hệ GIS đều có các công
cụ lưu trữ dữ liệu thuộc tính cùng với dữ liệu không gian.
Hình 1.2 Phần cứng GIS
- Công cụ phần mềm: Một hệ thống GIS bao gồm nhiều modul phần
các chức năng tìm kiếm và phân tích không gian. Kết quả tìm kiếm và phân tích
được xem như diễn giải dữ liệu, đó là tổ hợp hay biến đổi đặc biệt của dữ liệu có
cấu trúc. Hệ thống GIS phải có phần mềm công cụ để tổ chức và lưu trữ các loại
dữ liệu khác nhau, từ dữ liệu thô đến dữ liệu diễn giải. Phần mềm công cụ này
phải có các thao tác lưu trữ, truy nhập; đồng thời có khả năng hiển thị, tương tác
đồ họa với tất cả loại dữ liệu.
1.1.3 Ứng dụng của GIS
Vì GIS được thiết kế như một hệ thống chung để quản lý dữ liệu không
gian nên có rất nhiều ứng dụng trong các lĩnh vực thường thấy trong thực tế.
GIS đóng vai trò như là một công cụ hỗ trợ quyết định cho việc lập kế hoạch
hoạt động [1].
- Quản lý và lập kế hoạch mạng lưới đường phố: bao gồm các chức năng
tìm kiếm địa chỉ, tìm vị trí khi biết trước địa chỉ đường phố; điều khiển đường
đi, lập kế hoạch lưu thông xe cộ; phân tích vị trí, chọn địa điểm xây dựng các
công trình công cộng; lập kế hoạch phát triển đường giao thông.
- Giám sát tài nguyên, thiên nhiên, môi trường: bao gồm các chức năng
quản lý sông ngòi, các vùng lụt, vùng đất nông nghiệp, có mưa, đất rừng, sống
hoang dã; phân tích tác động môi trường; vị trí của các công trình công cộng, …
- Quản lý đất đai: bao gồm các chức năng lập kế hoạch vùng, miền sử
dụng đất; quản lý nước tưới tiêu; kiến trúc mặt bằng sử dụng đất …
- Quản lý và lập kế hoạch các dịch vụ công cộng: bao gồm các chức năng
tìm địa điểm cho các công trình ngầm: ống dẫn, đường điện,…; cân đối tải điện;
lập kế hoạch bảo dưỡng các công trình công cộng…
- Phân tích tổng điều tra dân số, lập bản đồ các dịch vụ y tế, bưu điện và
nhiều ứng dụng khác.
1.2 Mô hình cơ sở dữ liệu không gian (Spatial database)
1.2.1 Khái quát về cơ sở dữ liệu không gian
Thế giới quá phức tạp đến mức chúng ta không thể hiểu ngay và hiểu trực
tiếp chúng được. Chúng ta phải lập mô hình của hiện thực, nó có tính tương tự
Dữ liệu (data) và thông tin (information) là hai khái niệm khác biệt nhau.
Dữ liệu là các con số hay sự kiện được tập hợp có hệ thống cho một hay nhiều
mục đích cụ thể. Chúng có thể tồn tại dưới nhiều hình thức khác nhau như ngôn
ngữ tự nhiên (tên, địa chỉ,…), biểu tượng (biển hiệu giao thông), biểu thức toán
học hay tín hiệu (sóng điện từ). Thông tin được xem như dữ liệu đã được xử lý
dưới khuôn mẫu hữu ích cho người dùng và là những giá trị nhận thức được cho
công tác lập quyết định. Dữ liệu là thông tin nhưng không phải mọi dữ liệu đều
có ích. Thông tin chỉ có ích khi nó có liên quan, tin cậy, chính xác, kịp thời, đầy
đủ, dễ hiểu, phù hợp và dễ quản lý. Hệ thống thông tin có nhiệm vụ chuyển đổi
dữ liệu thành thông tin theo các tiến trình khác nhau như biến đổi, tổ chức, cấu
trúc hóa và mô hình hóa. Hình 1.5 cho thấy các chức năng của quá trình biến đổi
dữ liệu thành thông tin trong một hệ thống thông tin.
Dữ liệu địa lý là loại đặc biệt của dữ liệu. Chúng được nhận biết bởi tọa
độ địa lý và được hình thành từ phần tử mô tả và phần tử đồ họa. Thông tin địa
lý thu được từ xử lý dữ liệu địa lý. Tổ chức thông tin biểu diễn quan sát dữ liệu
của người sử dụng (khái niệm về thế giới thực) và nó được thể hiện bằng mô
hình dữ liệu.
Mô hình dữ liệu địa lý là các quy tắc được sử dụng để biến đổi đặc trưng
địa lý của thế giới thực thành các đối tượng rời rạc. Mô hình dữ liệu được sử
dụng để biểu diễn thực thể với mức độ phức tạp khác nhau. Thực thể là nhận
thức vì thế giới thực quá phức tạp, không thể chỉ ra mọi khía cạnh của chúng.
Việc lựa chọn mô hình dữ liệu phụ thuộc vào loại ứng dụng và kết quả mong đợi.
Hình 1.5 Biến đổi dữ liệu thành thông tin
- 13 -
1.2.2 Mô hình thông tin không gian
Dữ liệu là trung tâm của hệ thống GIS, hệ thống GIS chứa càng nhiều dữ
liệu thì chúng càng có ý nghĩa. Dữ liệu của hệ GIS được lưu trữ trong cơ sở dữ
liệu và chúng được thu nhập thông qua các mô hình thế giới thực. Dữ liệu trong
tượng, có thể tách rời khỏi hiện tượng láng giềng. Đối tượng lại có thể bao gồm
các đối tượng khác và chúng có quan hệ đặc biệt với các đối tượng tách biệt.
Một vài hiện tượng tự nhiên như hồ, sông, đảo, rừng cũng thường được biểu
diễn bằng mô hình đối tượng vì chúng cần được xử lý như hiện tượng rời rạc.
Nhưng cần phải chú ý rằng đường biên của các hiện tượng này là không cố định,
chúng thay đổi theo thời gian.
• Mô hình không gian trên cơ sở mạng chia sẻ một vài khía cạnh của
mô hình đối tượng vì chúng đề cập đến các hiện tượng rời rạc, nhưng đặc trưng
chính là nhu cầu xem xét tương tác giữa các đối tượng, thường là đường đi để
nối chúng. Hình dạng chính xác của các đối tượng có thể là không thực sự quan
trọng. Cái quan trọng ở đây là thước đo khoảng cách giữa các hiện tượng nghiên
cứu. Ví dụ điển hình phù hợp với mô hình mạng là nghiên cứu giao thông đường
bộ, đường biển và đường hàng không, chỉ ra tuyến đường đi của xe buýt; phân
tích luồng nước, ga và điện trong ống dẫn và dây cáp.
• Mô hình không gian trên cơ sở nền phù hợp cho mô hình hóa hiện
tượng quan tâm đến các vật liên tục trải trên vài vùng không gian. Ví dụ, hiện
tượng phù hợp với mô hình nền là ô nhiễm trong khí quyển, nhiệt độ trên bề mặt
Trái Đất, độ ẩm của đất trồng, tốc độ và hướng gió, nước chảy. Nền có thể được
biểu diễn hai hay ba chiều không gian tùy thuộc loại ứng dụng.
Một số kiểu dữ liệu đôi khi được coi như nền, đôi khi chúng lại được coi
là đối tượng. Lựa chọn mô hình cho chúng phụ thuộc vào hình thức thu thập dữ
liệu. Nếu ứng dụng liên quan đến phân vùng thì mô hình nền có thể chuyển đổi
mô hình đối tượng vì nó phù hợp hơn cho đo đạc và phân tích các đặc trưng
đường, vùng rời rạc.
1.2.3 Các mô hình dữ liệu không gian chính
Mỗi GIS đều có mô hình dữ liệu quan niệm riêng để biểu diễn mô hình dữ
liệu vật lý duy nhất. Hệ thông tin địa lý cung cấp các phương pháp để người sử
dụng làm theo các mô hình quan niệm tương tự như ba lớp mô hình mô tả trên [1].
Với người dùng thì các quan niệm dữ liệu không gian liên quan chặt chẽ
với dữ liệu nguồn để xây dựng nên mô hình không gian trên máy tính. Các đơn
giá trị). Bản đồ được phân ra thành nhiều tầng (layer). Mỗi tầng bản đồ có thể
bao gồm hàng triệu tế bào.
Lợi thế lớn nhất của hệ thống raster là dữ liệu hình thành bản đồ trong bộ
nhớ máy tính. Do vậy, các thao tác kiểu như so sánh lưới tế bào được thực hiện
dễ dàng. Tuy nhiên, hệ thống raster sẽ không thuận tiện cho biểu diễn đường,
điểm vì mỗi loại là tập tế bào trong lưới. Đường thẳng có thể bị đứt đoạn hay
rộng hơn.
Phương pháp raster được hình thành trên cơ sở quan sát “nền” thế giới
thực. Quan sát nền là phương pháp tổ chức thông tin trong hệ thống phân tích
ảnh vệ tinh và hệ thống GIS hướng tài nguyên và môi trường.
Khó khăn lớn nhất khi xử lý dữ liệu raster là vấn đề “tế bào trộn”. Cũng
như mô hình vectơ, mô hình raster có các tầng bản đồ cho địa hình, hệ thống
thủy lợi, sử dụng đất, loại đất Tuy nhiên do cách thức xử lý thông tin thuộc
tính khác nhau cho nên mô hình raster thường có nhiều tầng bản đồ hơn.
1.2.3.2 Mô hình dữ liệu VECTƠ
Mô hình dữ liệu vectơ coi hiện tượng là tập các thực thể không gian cơ sở
và tổ hợp giữa chúng. Trong mô hình 2D thì thực thể sơ đẳng bao gồm điểm,
đường và vùng; mô hình 3D còn áp dụng bề mặt ba chiều và khối (hình 1.9).
Các thực thể sơ đẳng được hình thành trên cơ sở các vectơ hay tọa độ của các
điểm trong một hệ trục tọa độ nào đó.
- 17 -
Hình 1.9 Các thành phần hình học cơ sở
Điểm là thành phần sơ cấp của dữ liệu địa lý ở mô hình này. Các điểm
được nối với nhau bằng đoạn thẳng hay các đường cong để tạo thành các thực
thể khác nhau như đường hay vùng.
Loại thực thể sơ đẳng được sử dụng phụ thuộc vào tỷ lệ quan sát hay mức
độ khái quát. Với tỷ lệ nhỏ thì thành phố được biểu diễn bằng điểm, còn đường
đi và sông ngòi được biểu diễn bằng đường. Khi tăng tỷ lệ biểu diễn thì phải
ÏTóm lại, mỗi mô hình đều có ưu - nhược điểm riêng theo bảng sau:
Mô hình raster Mô hình vectơ
Ưu điểm
Mô hình hiệu quả
Dễ tổ hợp, nạp chồng
Hướng ảnh vệ tinh
Dễ phân tích dữ liệu
Có khả năng mô phỏng
Thuận tiện biểu diễn hiện tượng tự nhiên
Mô hình cô đọng
Có khả năng tại lập topo lưới
Thao tác hình học dễ, chính xác
Có khả năng tổng quát hóa, dễ sửa đổi
Nhược điểm
Chất lượng đồ họa hạn chế
Khó mô hình hóa mạng
Biến đổi phi tuyến phức tạp
Cấu trúc dữ liệu phức tạp Bảng 1.1 So sánh mô hình raster và mô hình vectơ
- 19 -
1.3 Mạng lưới trong cơ sở dữ liệu không gian
Cơ sở dữ liệu mạng lưới không gian là thành phần quan trọng của các cơ
sở dữ liệu không gian, cơ sở dữ liệu mạng lưới không gian (SNDB) hình thành
phần cốt lõi của nhiều ứng dụng quan trọng gồm lập kế hoạch vận chuyển, điều
khiển giao thông đường hàng không, các tiện ích nước, điện và gas, mạng lưới
điện thoại và quản lý kênh tưới tiêu. Cho đến bây giờ, chúng ta tập trung vào các
đối tượng không gian và các mối tương quan của chúng mà dựa trên quan điểm
hình ngoài và mô hình khái niệm độc lập với cấu trúc dữ liệu và cơ chế khai thác
dữ liệu trong cơ sở dữ liệu. Phần lớn các DBMS trên thị trường được cài đặt
theo một trong ba mô hình dữ liệu quen thuộc: mô hình phân cấp, mạng và quan
hệ. Các mô hình dữ liệu này có tên chúng là mô hình logic hay mô hình trong
(internal model). Gần đây xuất hiện mô hình hướng đối tượng và mô hình trên
cơ sở lôgic hay suy diễn (deductive). Tuy nhiên, chúng vẫn chưa được sử dụng
rộng rãi. Mức này của kiến trúc cơ sở dữ liệu xác định cấu trúc bản ghi logic và
đường dẫn xâm nhập tương ứng với dữ liệu xác định trong các mô hình khái
niệm và mô hình ngoài. Đề cập đến đường dẫn xâm nhập có nghĩa là đề cập đến
các khái niệm trường khóa, chỉ số, dãy con trỏ… Không như mô hình khái niệm,
mô hình logic chắc chắn phụ thuộc vào các công việc của DBMS, nhưng chúng
vẫn độc lập với tổ chức vật lý của dữ liệu trên các thiết bị nhớ. Mức cấu trúc cơ
sở dữ liệu thấp nhất là mô hình vật lý. Trong mô hình này phải định nghĩa các
tham số cho dữ liệu như tổng số byte cho một khối dữ liệu và địa chỉ của chúng
trong bộ nhớ vật lý [1].
Hình 1.11 Các mức biểu diễn thông tin trong cơ sở dữ liệu
Ta đã xem xét phương tiện xây dựng cơ sở dữ liệu, đó là ngôn ngữ định
nghĩa dữ liệu DDL. Ta cũng cần phải có cơ chế khai thác dữ liệu, cũng như bổ
sung, thay đổi, loại bỏ chúng trong cơ sở dữ liệu, đó là ngôn ngữ xử lý dữ liệu
(data manipulation language - DML). Thông thường ta có khả năng truy nhập
dữ liệu trong cơ sở dữ liệu từ chương trình ứng dụng theo thủ tục đặc biệt hay
chương trình con và từ ngôn ngữ truy vấn như SQL, QBE,… các ngôn ngữ này
cho phép tương tác với DBMS. Thực hiện truy vấn cơ sở dữ liệu là yêu cầu
- 21 -
DBMS tìm ra mục dữ liệu hay lớp của mục chuyển đổi từ mô hình ngoài sang
mô hình khái niệm, từ mô hình khái niệm sang mô hình trong và từ mô hình
trong sang mô hình vật lý. Nhưng thực tế, để cho hiệu quả thì một số chuyển đổi
giữa các mô hình được bỏ qua. Phần lớn các DBMS sử dụng từ điển dữ liệu
hướng hoặc vô hướng tùy thuộc vào các ứng dụng, nhưng mạng lưới sông ngòi
- 22 -
được mô tả tự nhiên nhất như là đồ thị có hướng.
Hình 1.12 Mô hình đồ thị của hệ thống mạng lưới sông ngòi
Giả sử quá trình số hóa tạo ra đồ thị mô hình từ mạng lưới không gian đầu
vào trong ví dụ sau. Xét mạng lưới đường phố trong hình 1.13 a), các nút đồ thị
được sinh ra trong tiến trình này là: (i) những chỗ giao nhau của các con đường
trong mạng lưới (ví dụ các điểm đen trong hình 1.13 a), (ii) điểm bắt đầu/điểm
kết thúc của đoạn đường (điểm màu trắng) và (iii) phụ thuộc vào các ứng dụng,
các điểm thêm vào (màu xám) như các nút tại chỗ cong hoặc các thay đổi hạn
chế tốc độ. Các cạnh đồ thị duy trì tính liên thông trong mạng lưới ban đầu.
Hình 1.13b) chỉ ra đồ thị (mô hình) của mạng lưới trong hình 1.13 a); các nút tại
ranh giới của không gian dữ liệu và khoảng cách mạng lưới của hầu hết các cạnh
được bỏ qua sự rõ ràng [5].(a) Mạng lưới đường phố (b) Đồ thị mô hình
Hình 1.13. Đồ thị mô hình của mạng lưới đường phố
Đôi khi các nhãn (label) và trọng số (weight) được gắn vào các nút và các
đường nối của đồ thị để mã hóa các thông tin bổ sung. Ví dụ, tên, tọa độ địa lý
hoặc cả hai có thể được gắn vào các nút của hệ thống đường tàu lửa và khoảng
- 23 -
cách giữa các trạm có thể được giữ trọng số của cạnh.
Hai cạnh được gọi là liền kề nhau nếu chúng có chung một nút. Dãy các
cạnh liền kề tạo thành một đường đi (path). Ví dụ, dãy (v
0
Public class Graph
{ public void add(Object label); // label miêu tả đỉnh thêm vào
public void addEdge(Object v1, Object v2, Object label);
// một cạnh được chèn vào giữa hai đỉnh v1 và v2
public Object delete(Object label); // xóa một đỉnh
public Object deleteEdge(Object v1, Object v2);
//xóa cạnh nối đỉnh v1 và v2
public Object get(Object label); // trả về nhãn đỉnh
public Edge getEdge(Object v1, Object v2);
// trả về nhãn của cạnh nối v1 và v2
public Object get-a-Successor(Object label);
// trả về nút liền kề với đỉnh
public Iterator getSuccessors(Object label);
// trả về tất cả các láng giềng liền kề
public Iteator getPredecessors(Object label); // trả về tất cả các nút cha
public boolean isDirected(); // trả về True nếu đồ thị có hướng
}
Copyright: Tài liệu đại học ©