ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TOÁN
---------(((---------










Đề tài:






Giáo viên hướng dẫn : PGS.TSKH Trần Quốc Chiến
Sinh viên thực hiện : Lưu Thị The
Nguyễn Thị Nguyệt
Bùi Thị Xuân
Nguyễn Thị Bích Thùy
Trịnh Thị Thoa
Nhóm 1 – Lớp 07 CTT1,2











PHẦN MỞ ĐẦU
1. Giới thiệu chung
2. Mục đích nghiên cứu
PHẦN NỘI DUNG
Chương 1: LÝ THUYẾT
I. Các khái niệm liên quan
II. Vectơ đồ thị
Chương 2: PHÂN TÍCH VÀ THIẾT KẾ
I. Cấu trúc dữ liệu
II. Thiết kế và giải thuật
III. Sơ đồ khối
IV. Cấu trúc chương trình
Chương 3: CÀI ĐẶT VÀ SỬ DỤNG THUẬT TOÁN
I. Giới thiệu ngôn ngữ lập trình
II. Chức năng và giao diện chương trình
PHẦN KẾT LUẬN




PHẦN MỞ ĐẦU

1. Giới thiệu chung
Lí thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó đã được nhà toán học Thụy Sĩ vĩ đại Leonhard Euler đưa ra từ thế kỷ 18.
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là công cụ hữu hiệu để mô hình hoá và giải quyết các bài toán trong nhiều lĩnh vực khác nhau như: khoa học, kỹ thuật, kinh tế, xã hội… Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xem các trang web có thể liên kết với nhau hay không nhờ mạng đồ thị của các trang web. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông. Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa biểu, và phân bố tần số cho các trạm phát thanh và truyền hình…
Giả sử ta có các trang web liên kết với nhau bởi các đường dẫn. Chúng ta có thể biểu diễn các trang web bằng các điểm và các đường dẫn bằng các đoạn thẳng như hình vẽ:











.
Ta thấy rằng ở hình trên, giữa hai trang web chỉ có nhiều nhất là một đường dẫn nối chúng, đường dẫn này cho phép liên lạc cả hai chiều và không có trang web nào lại được nối với chính nó. Sơ đồ mạng trang web là một vecto đồ thị. Để nghiên cứu sâu hơn về vectơ đồ thị chúng em chọn đề tài VECTƠ BẬC ĐỒ THỊ.
2. Mục đích nghiên cứu
- Thông qua việc nghiên cứu, học tập và thực hiện đề tài VECTƠ BẬC ĐỒ THỊ chúng em có thể hiểu sâu sắc hơn về bộ môn LÍ THUYẾT ĐỒ THỊ.
- Qua việc cài đặt chương trình cho thuật toán VECTƠ BẬC ĐỒ THỊ chúng em hoàn thiện hơn về khả năng lập trình. Đồng thời với việc cùng nhau nghiên cứu học tập thì chúng em có thể xiết chặt tinh thần đoàn kết và tạo điều kiện thuận lợi cho việc học tập, nghiên cứu của mình.


PHẦN NỘI DUNG

Chương 1: LÝ THUYẾT

I. Các khái niệm liên quan
Định nghĩa 1: Đồ thị vô hướng G = (V,E) gồm một tập V các đỉnh và tập E các cạnh, mỗi cạnh e E được liên kết với một cặp đỉnh v, w (không kể thứ tự), như hình sau:

v e w

Định nghĩa 2: Đồ thị có hướng G = (V, E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung, mỗi cung e E được liên kết với một cặp đỉnh v, w có thứ tự, như hình sau:

v e w
* Cho đồ thị (vô hướng và có hướng) G = (V, E)
Nếu cạnh e liên kết với đỉnh v, w thì ta nói cạnh e liên thuộc đỉnh v, w, các đỉnh v, w liên thuộc cạnh e, các đỉnh v, w là các đỉnh biên của e và đỉnh v kề với đỉnh w.
V được gọi là đỉnh đầu và w được gọi là đỉnh cuối nếu e là cung.
Các cạnh song song là các