Giới thiệu :
Lý thuyết đồ thị đợc nghiên cứu và phát triển do nẩy sinh từ nhu cầu giải quyết
các vấn đề thực tiễn, có nhiều ứng dụng trong các ngành khoa học kỹ thuật khác
nhau. Đề tài thực hiện là "Một số vấn đề ứng dụng của đồ thị trong Tin học",
đây là đề tài nghiên cứu lý thuyết giải quyết nhiệm vụ là làm sáng tỏ hơn cơ sở
toán cho Tin học đồng thời nêu ra những khả năng ứng dụng của đồ thị trong Tin
học theo từng nội dung của Lý thuyết đồ thị.
Lý thuyết đồ thị đóng vai trò làm cơ sở toán cho Tin học vì đồ thị là một bộ
phận của Toán rời rạc, bản chất và cấu trúc của đồ thị mang tính rời rạc mà công
cụ chính trong Tin học là máy tính, các quá trình xử lý lu trữ thông tin trong máy
tính cũng mang tính rời rạc, nên điều này tơng hợp giữa đồ thị và máy tính.
Lý thuyết đồ thị có cả một khối lợng kiến thức lý thuyết đồ sộ, ứng dụng của đồ
thị cũng rất rộng, đề tài đợc thực hiện chỉ bao gồm những nội dung cơ sở và trọng
tâm của đồ thị, vào mỗi nội dung lý thuyết sẽ đa ra những ví dụ ứng dụng minh
hoạ nhằm làm rõ sự ứng dụng của phần lý thuyết đó. Trong các ứng dụng rất rộng
lớn của đồ thị các ví dụ đợc đa ra cũng cha đầy đủ nhng thực sự đó cũng là đại
diện và phần nào làm sáng tỏ các vấn đề ứng dụng của đồ thị.
Luận văn đợc thực hiện đi theo từng phần nội dung của lý thuyết đồ thị gồm 5
chơng nh sau :
Chơng I Một số vấn đề cơ bản của đồ thị
Nghiên cứu các vấn đề ứng dụng của đồ thị, trớc hết phải tìm hiểu các vấn đề cơ
bản của lý thuyết đồ thị, đây là cơ sở để tìm hiểu sâu sắc hơn các vấn đề tiếp theo.
Trong chơng sẽ trình bày các định nghĩa và tính chất cơ bản của đồ thị, nhng tóm
lại ta quan tâm đến các vấn đề chính sau:
- Tính rời rạc : Đồ thị là cấu trúc rời rạc gồm các đỉnh và cạnh, thể hiện đúng
nh các yếu tố rời rạc trong máy tính. Các yếu tố rời rạc nhau nhng không hoàn
toàn độc lập nhau mà giữa chúng có sự liên hệ, có mối quan hệ với nhau. Nghiên
cứu mối quan hệ giữa các yếu tố rời rạc là quan trọng, điều này quy định bản chất
và cấu trúc của đồ thị.
- Cách biểu diễn và lu trữ của đồ thị trên máy tính : Cấu trúc dữ liệu liên quan
chặt chẽ đến giải thuật, cách thức biểu diễn đồ thị trên máy tính ảnh hởng nhiều

truyền tin dự phòng khác, để xem xét các đờng truyền dự phòng ta cần xem xét
đến đờng đi, số đờng đi giữa 2 điểm truyền tin đó. Nh vậy ta thấy ứng dụng này
liên quan tới đờng đi, số đờng đi giữa 2 đỉnh trong mô hình đồ thị tơng ứng.
Chơng II. Số ổn định và tô màu đồ thị
Chơng gồm 2 nội dung chính: Số ổn định và sắc số đồ thị. Số ổn định là số ổn
định trong, số ổn định ngoài và nhân đồ thị. Nh đã nêu trên, mối quan hệ giữa các
yếu tố rời rạc là quan trọng, đề cập tới các vấn đề này ta lại thấy đợc rõ mối quan
hệ giữa các tập đỉnh. Tập ổn định trong lại tập các đỉnh của đồ thị sao cho những
đỉnh trong tập này có mối quan hệ là không kề nhau. Tập ổn định ngoài hay còn
gọi là tập thống trị, những đỉnh trong tập này có mối quan hệ "thống trị" các đỉnh
2
khác ngoài tập, quan hệ "thống trị" này đợc hiểu là luôn tồn tại 1 đỉnh thuộc tập
thống trị sao cho nó kề với 1 đỉnh bất kỳ ngoài tập. Nhân đồ thị chính là tập vừa là
tập ổn định trong vừa là tập ổn định ngoài, đối với tập ổn định trong ta quan tâm
tới tập có lực lợng cực đại, với tập ổn định ngoài ta quan tâm tới tập có lực lợng
cực tiểu.
Về mặt ứng dụng của số ổn định : số ổn định ngoài thờng đợc áp dụng cho bài
toán đặt vọng gác, từ ý tởng này ta xét 1 ứng dụng phục vụ cho việc lập trình chơi
cờ ca rô. Trong kỹ thuật chơi cờ Ca rô quân có khả năng thắng nhiều hơn là quân
có khả năng thống trị đợc quân đối phơng, sử dụng cấu trúc dữ liệu là đồ thị cho
thế cờ ta có thể áp dụng phơng pháp tìm tập ổn định trong để tính nớc đi có lợi
nhất cho cờ ca rô, hơn nữa việc tính toán đờng đi, nớc đi cũng sẽ đợc thuận lợi
hơn.
Vấn đề tô màu đồ thị là việc tìm số màu tối thiểu để tô các đỉnh đồ thị sao cho
những đỉnh kề nhau phải khác màu nhau hay còn gọi là tìm sắc số đồ thị. Về mặt
ứng dụng ta có thể thấy đợc áp dụng cho bài toán lập lịch. Lập lịch là việc bố trí
hợp lý để sao cho không có sự trùng lặp nh là về thời gian và địa điểm... thì tơng
ứng trong đồ thị phải tô màu các đỉnh sao cho 2 đỉnh kề nhau thì không trùng
màu. Vậy nên chăng phát triển nghiên cứu vấn đề tô màu đồ thị một cách đầy đủ
hơn để phục vụ cho bài toán lập lịch.

c[u, v] là ma trận trọng số.
T tởng của thuật toán Dijkstra là xây dựng dần dần tập S các đỉnh có trọng số
nhỏ nhất: mỗi lần tìm đợc đỉnh có trọng số nhỏ nhất thì dùng nó để điều chỉnh
trọng số các đỉnh kề với nó sau đó đa đỉnh có trọng số nhỏ nhất vừa tìm đợc vào
tập S.
Về mặt ứng dụng : Trong lĩnh vực Tin học, xét ở 1 mạng máy tính nhiều khi ngời
ta cần xác định một đờng truyền có thời gian truyền tin ngắn nhất giữa 2 máy nào
đó. Để thực hiện điều này có thể mô hình mạng bằng đồ thị sau đó vận dụng thuật
toán tìm đờng đi ngắn nhất để giải quyết.
Các ứng dụng thì có nhiều, trong chơng này ta sẽ đề cập một cách cụ thể về thuật
toán Viterbi vận dụng lý thuyết đờng đi ngắn nhất để sửa gói tin bị truyền sai
trong 1 hệ thống thông tin, đây là 1 ứng dụng khá thiết thực vì nó hay bắt gặp
trong 1 hệ thống truyền tin. Khi nói đến bài toán tìm đờng đi ngắn nhất, ngời ta
cũng hay mở rộng thành bài toán tìm đờng đi dài nhất. Với vấn đề này trong ch-
ơng cũng nêu ra cụ thể ứng dụng đồ thị cho việc lập lịch thi công 1 công trình lớn.
Đây là 1 ứng dụng thuộc loại bài toán tối u vận dụng đờng đi dài nhất và đồng
thời cũng là ứng dụng cho công tác lập lịch. Đồ thị cho ứng dụng này gọi là sơ đồ
mạng Pert, đây cũng là loại đồ thị có u tiên trớc sau và cuối chơng sẽ xét đến ứng
dụng của loại đồ thị này trong việc lập trình song song.
Chơng V. Một số vấn đề về cây
Là nội dung cuối cùng của luận văn, chơng này sẽ đề cập đến nhiều ứng dụng
của cây cho việc áp dụng, phân tích các giải thuật cơ sở trong kỹ năng lập trình.
Cây là trờng hợp riêng của đồ thị, có những đặc trng riêng dễ nhận thấy đó là luôn
tồn tại 1 đờng đi duy nhất giữa mọi cặp đỉnh, biết đợc số đỉnh thì luôn biết đợc số
cạnh... Để nghiên cứu hết các tính chất về cây thì đó là cả 1 khối lợng kiến thức
4
lớn, chơng này chỉ đề cập tới những vấn đề cơ bản nhất về cây và tập trung khai
thác những ứng dụng của nó.
Sự ứng dụng cây trong việc phân tích các giải thuật đó là nhiều thuật toán có thể
mô hình bằng cây, hay nói cách khác là dùng cây để thể hiện, biểu diễn thuật

từng nội dung lý thuyết đồ thị thì chỉ nêu đợc các ứng dụng của phần nội dung lý
thuyết đó mà cha nêu đợc các ứng dụng của tổng hợp nhiều nội dung lý thuyết đồ
thị.
5