Luận văn tốt nghiệp Phan Thanh Long
Lời nói đầu
Bớc sang năm bản lề của thế kỷ 21, nhìn lại thế kỷ 20 là thế kỷ mà con ngời đạt
đợc nhiều thành tựu khoa học rực rỡ nhất, một trong những thành tựu đó là sự
bùng nổ của ngành khoa học máy tính. Sự phát triển kỳ diệu của máy tính trong
thế kỷ này gắn liền với sự phát triển toán học hiện đại, đó là toán rời rạc.
Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục.
Toán rời rạc bao gồm các lĩnh vực nh quan hệ, lý thuyết đồ thị, lôgíc toán, ngôn
ngữ hình thức... trong đó lý thuyết đồ thị là một bộ phận trọng tâm với nhiều khối
lợng kiến thức khá lý thú và đợc nghiên cứu nhiều nhất.
Toán rời rạc nói chung và lý thuyết đồ thị nói riêng là công cụ thiết yếu cho
nhiều ngành khoa học kỹ thuật, và là một thành phần quan trọng trong học vấn
đối với sinh viên các ngành kỹ thuật đặc biệt sinh viên ngành Tin học. Lý thuyết
đồ thị, với cách tiếp cận đối tợng nghiên cứu và phơng pháp t duy khá độc đáo
thực sự ngày càng hữu ích có nhiều ứng dụng phong phú và gây không ít bất ngờ.
Máy tính mà bản thân nó với các quá trình làm việc mang tính rời rạc, nên điều
này tơng hợp gắn chặt lý thuyết đồ thị với công nghệ máy tính trong việc nghiên
cứu các đối tợng có tính chất rời rạc.
Lý thuyết đồ thị có nhiều ứng dụng thực tiễn đặc biệt là trong lĩnh vực Tin học,
muốn hiểu biết sâu sắc các vấn đề Tin học cần nắm vững các kiến thức về Toán
học rời rạc mà trong đó đặc biệt là lý thuyết đồ thị. Từ những nhận thức trên, với
đề tài "Một số vấn đề ứng dụng của đồ thị trong Tin học" đây không chỉ là
nhiệm vụ em phải thực hiện trong kỳ bảo vệ luận văn tốt nghiệp mà thực sự đây là
đề tài mà em rất quan tâm và say mê nghiên cứu.
Với tấm lòng biết ơn sâu sắc, em xin chân thành cảm ơn Thầy giáo Pgs. Ts Đỗ
Đức Giáo là ngời trực tiếp, tận tình, chu đáo giảng dạy và hớng dẫn em hoàn
thành cuốn luận văn này. Nhân dịp này em cũng xin cảm ơn sự giúp đỡ, dạy bảo
tận tình của các thầy cô giáo, cán bộ Khoa Công Nghệ Thông Tin trờng Đại học
Dân lập Đông Đô và những bạn học đã đóng góp những ý kiến bổ ích cho bản
luận văn này.
Do trình độ hiểu biết còn hạn chế, thời gian chuẩn bị không nhiều, bản luận

hiểu sâu sắc hơn các vấn đề tiếp theo. Ngoài các định nghĩa, tính chất cơ bản của
đồ thị, chơng này có trình bày đến 1 vấn đề quan trọng, đó là cách lu trữ, biểu
diễn và xử lý đồ thị trên máy tính khi đã xét những mô hình biểu diễn hình học.
Cấu trúc dữ liệu liên quan chặt chẽ đến giải thuật, việc biểu diễn đồ thị trên máy
tính nh thế nào sẽ ảnh hởng đến cách giải các bài toán ứng dụng bằng máy tính.
Trong chơng có trình bày một số phơng pháp biểu diễn đồ thị trên máy tính, mỗi
phơng pháp đều có những u và khuyết điểm riêng, vì vậy cần lựa chọn phơng pháp
sao cho phù hợp với đặc điểm từng bài toán và đạt đợc hiệu quả về thuật toán.
Khi đa các ví dụ minh họa, nhất là về phần đồ thị đặc biệt ta sẽ thấy đợc ứng
dụng của đồ thị trong mô hình về mạng máy tính.
2
Luận văn tốt nghiệp Phan Thanh Long
Ch ơng 2 Số ổn định và tô màu đồ thị
Số ổn định của đồ thị bao gồm số ổn định trong, số ổn định ngoài và nhân đồ thị,
nghiên cứu vấn đề này ta sẽ thấy đợc mối quan hệ giữa các tập đỉnh của một đồ
thị. Một ứng dụng khá lý thú khi đề cập tới vấn đề này đó là xây dựng mô hình đồ
thị cho bài toán lập trình chơi cờ carô, có sử dụng đến tập ổn định ngoài của đồ
thị.
ở chơng này ta cũng sẽ gặp đến một ứng dụng khá thiết thực khi bàn đến vấn đề
tô màu của đồ thị, hay còn gọi là sắc số của đồ thị, ứng dụng đó là bài toán lập
lịch. Lập lịch là công tác hành chính phổ biến, hay gặp ở các cơ quan, xí nghiệp,
trờng học... cũng đã có nhiều sản phẩm phần mềm phục vụ cho việc lập lịch.
Ch ơng 3 Chu trình, đờng đi Euler và Hamilton trong đồ thị
Trình bày những khái niệm về chu trình Euler, đờng Euler, chu trình Hamilton,
đờng Hamilton các tính chất của chúng đồng thời đa ra 1 số thuật toán ứng dụng
để tìm các đờng, chu trình Euler, Hamilton.
Ch ơng 4 Đờng đi ngắn nhất trong đồ thị
Bài toán đờng đi ngắn nhất hay đợc đề cập tới trong lý thuyết đồ thị, đây cũng là
loại bài toán tối u có nhiều ứng dụng rộng rãi. Trong đồ thị thờng đặt ra các loại
tìm đờng đi ngắn nhất nh sau:

các bài toán đồ thị trên máy tính nh là kỹ thuật quay lui, tìm kiếm u tiên theo
chiều rộng và chiều sâu.
4