Graph và một số ứng dụng trong chương trình THPT

Chia sẻ: Vi Văn Sơn | Ngày: | Loại File: DOC | Số trang:78

Thêm vào BST

Báo xấu

97
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thụy Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Graph và một số ứng dụng trong chương trình THPT

DANH MỤC HÌNH VẼ Trang Hình 1.1 Đồ thị hàm số y = sinx......................................................................4 Hình 1.2 Đồ thị biểu diễn ví dụ 1...................................................................5 Hình 1.3 Đồ thị biểu diễn ví dụ 2...................................................................6 Hình 1.4 Đồ thị biểu diễn ví dụ 3...................................................................6 Hình 1.5 Biểu diễn phẳng của Graph.............................................................7 Hình 1.6 Biểu diễn Graph con và Graph thành phần......................................8 Hình 1.7 Biểu diễn bậc của đỉnh.....................................................................9 Hình 1.8 Dãy cạnh kế tiếp...............................................................................9 Hình 1.9 Biểu diễn cạnh có hướng...............................................................12 Hình 2.1 Ma trận kề đồ thị vô hướng không trọng số và đồ thị có hướng có tróng số...........................................................................................................14 Hình 2.2 Biểu diễn cài đặt đồ thị bằng danh sách cạnh trên mảng và trên danh sách móc nối..........................................................................................17 Hình 2.3 Đồ thị vô hướng không trọng số....................................................20 Hình 2.4 Biểu diễn Graph bằng danh sách kề..............................................22 Hình 2.5 Đồ thị vô hướng..............................................................................24 Hình 2.6 Ma trận kề đồ thị trọng số vô hướng và đồ thị trọng số có hướng 31 Hình 2.7a Đồ thị trọng số có hướng .............................................................31 Hình 2.7b Biểu diễn đồ thị trọng số bằng danh sách lân cận kề.................31 Hình 2.8 Đồ thị vô hướng có trọng số ví dụ 4..............................................33 Hình 2.9 Cây khung DFS(1) và cây khung BFS(1)........................................37 Hình 2.10 Đồ thị vô hướng có trọng số ví dụ 5............................................40
MỤC LỤC Trang MỞ ĐẦU..........................................................................................................1 Chương 1 MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT GRAPH...........................................4 1.1. Khái niệm cơ bản về graph...................................................................4 1.1.1. Những bài toán và vấn đề dẫn đến khái niệm graph [1]...............4 1.1.2. Định nghĩa graph và các khái niệm cơ bản.....................................7 1.1.3. Graph con và graph thành phần.......................................................8 1.2. Phân loại graph.......................................................................................9 1.2.1. Graph vô hướng...............................................................................9 1.2.2. Graph có hướng.............................................................................12 1.3. Kết luận chương 1...............................................................................13 Chương 2 MỘT SỐ THUẬT TOÁN CƠ BẢN TRÊN GRAPH...............................14 2.1. Biểu diễn graph trên máy tính............................................................14 2.1.1. Biểu diễn bằng ma trận lân cận [6].............................................14 2.1.2. Biểu diễn bằng danh sách cạnh [6]..............................................17 2.1.3. Biểu diễn danh sách lân cận [6]....................................................19 2.2. Phép duyệt một graph..........................................................................24 2.2.1. Tìm kiếm theo chiều sâu...............................................................25 2.2.2. Tìm kiếm theo chiều rộng.............................................................26 2.2.3. Tìm đường đi và kiểm tra tính liên thông của đồ thị....................28 2.3. Đồ thị trọng số.....................................................................................30 2.3.1. Khái niệm.......................................................................................30 2.3.2. Biểu diễn đồ thị trọng số..............................................................30 2.4. Đường đi trên đồ thị trọng số..............................................................32
2.4.1. Thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác..................................................................................................32 Độ phức tạp của giải thuật: Thuật toán Dijkstra tìm đ ược đ ường đi ngắn nhất trên đồ thị sau thời gian cỡ O(n2). [2]...................................33 Ví dụ 4: Cho đồ thị vô hướng có trọng số G trong hình 2.8 dưới đấy. Tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh khác trong G.. .33 Ma trận trọng số của đồ thị có dạng:.....................................................33 Kết quả tính toán theo thuật toán được trình bày trong bảng dưới đây. Quy ước viết hai thành phần của nhãn theo thứ tự: d[v], Truoc[v]. Đ ỉnh được đánh dấu ‘*’ là đỉnh được chọn để cố định nhãn ở bước lặp đang xét, nhãn của nó không biến đổi ở các bước tiếp theo, vì th ế ta đánh dấu -.........................................................................................................34 Bước lặp..................................................................................................34 Đỉnh 1.......................................................................................................34 Đỉnh 2.......................................................................................................34 Đỉnh 3.......................................................................................................34 Đỉnh 4.......................................................................................................34 Khởi tạo...................................................................................................34 0, 1............................................................................................................34 10, 1..........................................................................................................34 6, 1............................................................................................................34 2, 1*..........................................................................................................34 1................................................................................................................34 -.................................................................................................................34 5, 4............................................................................................................34 3, 4 *.........................................................................................................34 -.................................................................................................................34 2................................................................................................................34
-.................................................................................................................34 5, 4 *.........................................................................................................34 -.................................................................................................................34 -.................................................................................................................34 .................................................................................................................34 Nhận xét: Từ bảng kết quả ta có thể truy xuất ra được đường đi từ đỉnh 1 tới tất cả các đỉnh còn lại trong đồ thị như sau:.........................34 Đường đi từ đỉnh 1 tới đỉnh 2: ................................................................34 Ta có đỉnh trước đỉnh 2 là Truoc[2] = 4 vậy 4 là đỉnh trước đỉnh 2 trên đường đi này............................................................................................34 Trước đỉnh 4 là Truoc[4] = 1 vậy 1 là đỉnh trước đỉnh 4 trên đường đi này............................................................................................................34 Dừng, ta thu được đường đi ngắn nhất từ đỉnh 1 tới đỉnh 2 là:............34 1 – 4 – 2 với độ dài đường đi ngắn nhất là d[2] = 5...........................34 Tương tự ta có các đường đi sau:............................................................34 Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là: 1 – 4 – 3 với độ dài đường đi ngắn nhất là d[3] = 3...........................................................................34 Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 là: 1 – 4 v ới đ ộ dài đ ường đi ngắn nhất là d[4]=2.................................................................................34 2.4.2. Thuật toán Floyd tìm đường đi ngắn nh ất giữa t ất c ả các c ặp đỉnh...........................................................................................................34 - Khởi tạo: ..................................................................................................36 .....................................................................................................................36 Nhận xét: Đường đi từ đỉnh 1 tới các đỉnh còn lại trong đồ thị:...............36 Đường đi từ đỉnh 1 đến đỉnh 2: .................................................................36 Trước 2 là p[1,2]=4 vậy 4 là đỉnh trước 2 trên đường đi này. ..................36 Trước 4 là p[1,4]=0, vậy đỉnh 1 đứng trước đỉnh 4 trên đường đi này.....36
Dừng, đường đi thu được là: 1 – 4 – 2 với độ dài đường đi là d[1,2] = 5. ......................................................................................................................36 Tương tự ta tìm được đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là: 1 – 4 – 3 với độ dài d[1,3] = 3. ...............................................................................37 Do p[1,4] = 0 nên đường đi từ đỉnh một tới đỉnh 4 là đường đi trực ti ếp với độ dài là p[1,4]= 2.................................................................................37 Để tìm đường đi giữa tất cả cặp đỉnh còn lại trong đồ thị ta làm tương tự..................................................................................................................37 2.5. Cây khung và cây khung với giá trị cực tiểu.......................................37 2.6. Kết luận chương 2...............................................................................46 Chương 3 ỨNG DỤNG GRAPH GIẢI MỘT SỐ BÀI TOÁN TRONG...................47 CHƯƠNG TRÌNH TIN HỌC PHỔ THÔNG............................................47 3.1. Giới thiệu một số bài toán về đồ thị trong ch ương trình tin h ọc trung học phổ thông..............................................................................................47 3.2. Một số bài toán về phép duyệt đồ thị.................................................47 3.2.1. Bài toán 1- Đếm số thành phần liên thông [4]..............................48 3.2.2. Bài toán 2 - Dự tiệc ....................................................................50 3.2.3. Bài toán 3 - Bản đồ [2]..................................................................52 3.3. Một số bài toán về đường đi trong đồ thị...........................................53 3.3.1. Bài toán 1 - Đường đi [4]...............................................................53 3.3.2. Bài toán 2 - Du lịch [4]...................................................................56 3.3.3. Bài toán 3 - Đến trường [7]...........................................................58 3.4. Một số bài toán về cây khung đồ thị...................................................61 3.4.1. Bài toán 1 - Dự án.........................................................................61 3.4.2. Bài toán 2 - Thay hệ thống [4]......................................................64 3.4.3. Bài toán 3 – Bão Sơn Tinh.............................................................67 3.5. Kết luận chương 3...............................................................................70
KẾT LUẬN....................................................................................................71 TÀI LIỆU THAM KHẢO............................................................................72
MỞ ĐẦU 1. Lý do chọn đề tài Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đ ồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thụy Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng. Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đ ại. Đặc biệt trong khoảng vài chục năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ th ị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau nh ư: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học v.v... Một trong các mục tiêu khi đưa tin học vào nhà trường là nh ằm giúp cho học sinh có khả năng phân tích, tổng hợp, trừu t ượng hóa, khái quát hóa vấn đề và đặc biệt là phát triển tư duy. Hiện nay, có nhiều bài toán trong chương trình trung học phổ thông được giải quyết nhờ vận dụng lý thuy ết đồ thị. Để tìm hiểu sâu về lý thuyết đồ thị và ứng dụng của nó trong chương trình tin học phổ thông nên em đã chọn đề tài “Graph và một số ứng dụng trong chương trình trung học phổ thông”. 2. Mục đích nghiên cứu Tìm hiểu một số vấn đề về Graph như các khái niệm cơ bản về Graph, phân loại Graph… Để hiểu sâu sắc hơn lý thuyết Graph, cài đặt một số thuật toán, từ đó ứng dụng lý thuyết Graph vào chương trình tin học phổ thông để giải quyết một số bài toán liên quan. 3. Nội dung tìm hiểu, nghiên cứu • Một số vấn đề về lý thuyết về Graph. • Một số thuật toán cơ bản trên Graph. 1
• Ứng dụng lý thuyết Graph vào giải quyết một số bài toán cụ thể trong chương trình tin học phổ thông. 4. Phương pháp nghiên cứu • Nghiên cứu tài liệu: Nghiên cứu các tài liệu về lý thuy ết đồ th ị và các bài toán liên quan. • Phương pháp thực nghiệm: Lập trình kiểm thử, tìm hiểu thông tin trong một số Website trên mạng. • Tổng kết kinh nghiệm: Tổng kết các kiến thức đã học tập được. • Tham khảo ý kiến chuyên gia: Tiếp thu ý kiến đóng góp của các thầy cô và ý kiến của các bạn bè. Cấu trúc của đề tài Mở đầu: Nêu ra lý do chọn đề tài, phương pháp, nội dung tìm hiểu và mục đích nghiên cứu, cấu trúc đề tài. Chương 1: Một số vấn đề về lý thuyết Graph. Chương 2: Một số thuật toán cơ bản trên Graph: Tìm hiểu và cài đặt các thuật toán cơ bản trên Graph cụ thể như: biểu diễn Graph trên máy tính, phép duyệt Graph, tìm đường đi và kiểm tra tính liên thông của Graph….Các thuật toán được cài đặt trên ngôn ngữ lập trình Pascal. Chương 3: Ứng dụng của Graph vào chương trình Tin học phổ thông: Đưa ra và vận dụng lý thuyết Graph vào cài đặt một s ố bài toán c ụ thể trong chương trình tin học phổ thông theo từng dạng: Bài toán duyệt đồ thị, bài toán về đường đi trên đồ thị, bài toán về cây khung đồ thị. Kết luận: Nêu ra những vấn đề đã tìm hiểu, một số công việc chính đã được thực hiện, hướng phát triển tiếp theo của đề tài trong tương lai. Em xin chân thành cảm ơn Thầy giáo, TS Nguyễn Mạnh Đức - Gi ảng viên Tin học, Khoa Toán, Đại học Sư phạm Thái Nguyên, người đã trực tiếp hướng dẫn và tận tình chỉ bảo em trong suốt quá trình làm đề tài. 2
Em xin chân thành cảm ban chủ nhiệm Khoa Toán cùng các Th ầy, Cô trong khoa đã tạo điều kiện để em thực hiện đề tài này. Tôi cũng xin cảm ơn các bạn sinh viên, người thân đã động viên, giúp đỡ trong thời gian thực hiện đề tài. Thái Nguyên, tháng 4 năm 2013 Sinh viên Vi Văn Sơn 3
Chương 1 MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT GRAPH 1.1. Khái niệm cơ bản về graph 1.1.1. Những bài toán và vấn đề dẫn đến khái niệm graph [1] Hai chữ “đồ thị” vẫn thường xuyên xuất hiện trong toán h ọc và cả trong đời sống hàng ngày. Trong các giờ học toán, chúng ta có nói tới đồ th ị của các hàm số. Chẳng hạn, trong hình dưới có biểu diễn đồ thị của hàm số y=sinx. Trong các công sở, các nhân viên phải lập các biểu đồ theo dõi số lượng tiêu thụ điện hoặc xăng dầu hàng tháng,và họ cũng có thể gọi những biểu đồ đó là đồ Hình 1.1. Đồ thị hàm số y =sinx thị... Tóm lại khái niệm đồ thị là một khái niệm toán học khá quen thuộc đối với chúng ta nhằm biểu diễn tương quan đi lại hai đối tượng hoặc nhiều đối tượng toán học khác nhau. Lý thuyết đồ thị (theo tiếng Anh và tiếng Đức đọc là: “graph”) nghiên cứu những tính chất toán học, những quan hệ mà không phụ thuộc vào b ản chất riêng của những mối quan hệ này. Để tránh khỏi bị nhầm là đồ thị của hàm số, ta sử dụng thuật ngữ “graph” trong tài liệu này ở các ph ần ti ếp theo. Graph là một mô hình toán học có thể dùng để gi ải quy ết khá nhi ều bài toán và vấn đề toán học. Một graph có thể hiểu đơn giản là một h ệ th ống các đỉnh và các cạnh nối với nhau. Gần với mô hình lí thuy ết graph là các bài toán thoáng qua như những bài toán hình học mà thực ch ất việc gi ải quyết chúng không thể chỉ sử dụng những kiến thức hình học thông thường. Trên mặt phẳng, có những bài toán dường như là bài toán hình h ọc như thế, nhưng chúng ta có thể xem xét một số ví dụ để th ấy không ch ỉ có 4
thể dùng kiến thức hình học để giải quyết được chúng. Việc muốn giải quyết những bài toán này cần đi sâu hơn nữa vào những mối quan hệ toán học của các đối tượng toán học trong bài toán. Một s ố ví d ụ có ngu ồn g ốc phát sinh từ các bài toán hình học mà bản ch ất th ực sự của nó là các bài toán về lí thuyết grap. Ví dụ 1: Có ba cái nhà và ba cái giếng. Mỗi nhà có ba đường đi từ nó tới ba cái giếng đó. Hỏi có thể làm những con đường đi như vậy sao cho không có hai con đường nào cắt nhau hay không? Để giải quyết bài toán này, chúng ta có thể giả sử là các nhà là các điểm A1, A2, A3 trên mặt phẳng và các giếng là các điểm B1, B2, B3 nào đó. Các con đường đi là các đường (liên tục) nối các đỉnh Ai với các đỉnh Bi. Hình 1.2. Đồ thị biểu diễn ví dụ 1 Khi đó, câu hỏi của bài toán là liệu có những điểm A i tới các điểm Bi trên mặt phẳng sao cho không có hai con đường nào cắt nhau hay không? Bằng cách thiết lập mô hình này, chúng ta đã thi ết l ập một graph có 6 đỉnh và 9 cạnh. Chúng ta thấy rằng để giải bài toán này, các kiến thức hình học không còn giúp gì được cho chúng ta nữa. Bài toán đòi hỏi phải có kiến thức sâu sắc hơn về mối quan hệ nào đó của quan hệ các đỉnh và các cạnh. [1] Nhưng không phải chỉ với một số bài toán hoặc một số vấn đề toán học có nguồn gốc hình học mới có thể đưa về mô hình đỉnh – cạnh như trên. Mô hình đỉnh – cạnh của chúng ta tỏ ra là mô hình rất hiệu quả để nắm bắt được chính xác bản chất toán học thật sự của nhiều đối tượng toán h ọc. Các đỉnh được biểu diễn cho các đại lượng tham gia và các cạnh n ối chúng biểu diễn mối quan hệ đi lại của chúng theo một tiêu chuẩn nào đó được đưa ra. Ví dụ 2: 5
Hãy biểu thị graph quan hệ không nguyên tố cùng nhau của các số trong tập hợp { 1, 2, 3, 4, 5, 6 }. Bài toán này được giải quyết bằng phương pháp graph như sau: Trước hết ta chọn 6 điểm trên mặt phẳng biểu diễn cho 6 số 1, 2, 3, 4, 5 và 6. Các điểm này được tô đậm để phân biệt với giao điểm của các cạnh của graph. Chúng ta nối hai đỉnh của graph bởi một đường nối ( hình 1.3) nếu hai số tương ứng với hai đỉnh của chúng không nguyên tố cùng nhau. Trong biểu diễn graph như vậy, chúng ta có thể nhận ra ngay rằng có 3 số đôi một không nguyên tố cùng nhau. Hình 1.3. Đồ thị biểu diễn ví dụ 2 Mối quan hệ giữa các đại lượng ta xét rất có thể còn là các mối quan hệ trong đời sống. Chẳng hạn, cũng graph trong hình 2 biểu thị các mối quan hệ quen biết của 6 người, được đánh số từ 1 đến 6, nếu cho biết họ quen nhau khi số thứ tự tương ứng của họ không nguyên t ố cùng nhau. Trong các ví dụ trên, các đỉnh của graph được nối bởi các cạnh cũng có thể có hướng và chỉ nối các đỉnh khác nhau với nhau. Trong lý thuy ết graph các cạnh cũng có thể có hướng. Ví dụ 3: Có một trận đấu bóng bàn có một số đấu thủ cùng tham gia. Hai đ ấu thủ bất kì phải đấu với nhau đúng một hiệp. Điểm được cho mỗi hiệp là thắng 1 điểm, thua 0 điểm (không có hòa). Hỏi có khi nào trận đấu kết thúc với kết quả là tất cả các đấu thủ đều bằng điểm nhau hay không? Ta biểu diễn các đấu thủ tương ứng thành các đỉnh của một graph Hai đỉnh x và y của graph được nối bởi một cạnh có h ướng đi t ừ x t ới y nếu như đấu thủ x thắng đấu thủ y. Bài toán được 6 Hình 1.4. Đồ thị biểu diễn ví dụ 3
đặt ra là có thể có graph tương ứng với n đấu thủ sao cho các đỉnh có s ố cạnh xuất phát từ chúng bằng nhau. Trong hình 1.4 là một graph thỏa mãn yêu cầu của bài toán với n=5. Trong nhiều trường hợp, chúng ta chấp nhận những cạnh nối một đỉnh đã cho với chính nó. Loại này được gọi là cạnh khuyên trong graph. Trong lý thuyết graph có cho phép giữa hai đỉnh có thể có nhi ều c ạnh nối. Trong trường hợp có nhiều cạnh (ít nhất là hai) nối 2 đỉnh khác nhau nào đó của một graph, thì ta gọi cạnh đó là cạnh kép. 1.1.2. Định nghĩa graph và các khái niệm cơ bản Thông thường chúng ta hay kí hiệu một graph bởi chữ G (ch ữ cái đầu của từ “Graph” trong tiếng Đức, ngôn ngữ dùng để viết cuốn sách đầu tiên về lí thuyết graph). Còn tập đỉnh thường được kí hiệu bởi ch ữ V (là ch ữ cái đầu tiên của từ “Vertices”) và tập cạnh bởi ch ữ cái E (chữ cái đầu c ủa từ “Edges”). Graph không có cạnh có hướng thường được kí hiệu là G=(V,E), còn graph có các cạnh có hướng được kí hiệu là G=[V,E]. Việc dùng kí hiệu này không bắt buộc, mà chỉ là một thói quen mà thôi. Định nghĩa đồ thị: Một đồ thị G = (V, E) bao gồm một tập h ữu h ạn V = {v1, v2,…vn} các đỉnh (nút) và 1 tập hữu hạn E = {(v i, vj), vi, vj ∈ V} các cặp đỉnh gọi là cung (hay cạnh). Nếu (v i, vj) ∈ E thì ta nói có một cung nối vi với vj. Nếu cung (vi, vj) khác cung (vj, vi) thì G là đồ thị có hướng, ngược lại là không hướng. Một graph được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có cạnh nào cắt nhau (ở một điểm không ph ải là đi ểm mút của các cạnh). Hình vẽ như thế được gọi là một biểu di ễn ph ẳng c ủa graph. Hình 1.5. Biểu diễn phẳng của Graph 7
Như chúng ta đã thấy trong các ví dụ trên, graph thường được bi ểu di ễn trên mặt phẳng: các đỉnh được tô đậm và các cạnh nối các đỉnh là các đoạn thẳng hoặc là các đường cong nối các đỉnh này với nhau. Ngoài ra, chúng ta phải lưu ý rằng một graph có thể có nhiều biểu diễn trên mặt ph ẳng khác nhau. Trong hình 1.5 chúng ta có hai biểu diễn trên mặt phẳng khác nhau của một graph. Graph được phân loại theo tính chất cạnh của chúng. Trong mỗi graph các cạnh của graph thẳng hay cong, dài hay ngắn, các đỉnh ở v ị trí nào, đ ều không phải là điều quan trọng. Mà điều quan trọng là graph có bao nhiêu cạnh và đỉnh nào được nối với đỉnh nào. Một graph được gọi là graph vô hướng nếu tất cả các cạnh của nó đều là cạnh vô hướng. Graph được gọi là graph có hướng nếu tất cả các cạnh của nó đều là cạnh có hướng. Đỉnh xuất phát của một cạnh có hướng được gọi là đỉnh đầu, và đỉnh kết thúc của cạnh được gọi là đỉnh cuối của nó. Trong trường hợp graph có cả cạnh vô hướng cũng như cạnh có h ướng thì graph được gọi là graph hỗn hợp. Một graph được gọi là graph đơn nếu nó không có khuyên và không có cạnh kép. Ngoài ra, ta gọi graph điểm là graph có đúng một đỉnh và không có cạnh nào. Graph rỗng dùng để gọi một graph không có đỉnh và cạnh nào cả. 1.1.3. Graph con và graph thành phần Cho trước một graph G với tập đỉnh X và tập cạnh E. Một graph G’ với tập đỉnh X’ và tập cạnh E’ được gọi là graph con của graph G nếu X’ ⊂ X và E’ ⊂ E. Trong trường hợp X’ là tập con của X vả E’ là tập hợp tất Hình 1.6. Biểu diễn Graph con và Graph cả các cạnh của G nối hai đỉnh của X’, thì G’ đ ược thành phần 8
gọi là graph thành phần của G và còn được gọi là graph sinh bởi tập đỉnh X’. Graph trong hình 1.6 có các cạnh được tô đậm là graph con c ủa graph được biểu diễn trong hình. Nếu thêm vào nó hai cạnh a và b thì ta đ ược một graph thành phần đã cho. Graph rỗng là graph thành phần của mọi graph cho trước. 1.2. Phân loại graph 1.2.1. Graph vô hướng 1.2.1.1. Bậc của đỉnh Trong phần này chúng ta chỉ xét những graph vô hướng, tức là những graph mà các cạnh của chúng không có hướng. Ta gọi bậc của một đỉnh là s ố cạnh xuất phát từ đỉnh đó (các khuyên được tính gấp đôi). Bậc của một đỉnh là một số không âm. Một đỉnh được Hình 1.7. Biểu gọi là đỉnh cô lập nếu nó không có cạnh nào cả, tức là diễn bậc của đỉnh khi đỉnh có bậc là 0. Đỉnh có bậc bằng 1 là đỉnh treo. Graph trong hình 1.7 có A là đỉnh cô lập, D là đỉnh treo. Đ ỉnh B có b ậc là 3, đỉnh C có bậc là 2. Lưu ý rằng : trong một graph đơn vô hướng với n đỉnh thì bậc của một đỉnh bất kì luôn là một số nguyên không âm không vượt n-1. 1.2.1.2. Dãy cạnh kế tiếp Cho trước một graph G với tập đỉnh V và tập cạnh E. Hai cạnh của một graph cho trước gọi là hai cạnh kề nhau nếu như chúng có một đỉnh chung. Một dãy m Hình 1.8. Dãy cạnh kế tiếp cạnh ei = (Ai, Ai+1) với i=1, 2,…,m được gọi là một dãy cạnh nối tiếp và thường được kí hiệu là: H = (A1, e1, A2, e2 ,…, ek ,Ak+1) 9
Trong trường hợp G là một graph đơn thì ta có thể biểu diễn một dãy cạnh kế tiếp qua các đỉnh của chúng, chẳng hạn dãy cạnh kế tiếp của H của ta ở trên được kí hiệu đơn giản là: H = (A1, A2, A3,…,Ak+1) Theo định nghĩa thì một dãy các cạnh liên tiếp kề nhau (m ỗi c ạnh k ề với cạnh tiếp theo) chưa hẳn đã là dãy cạnh kế tiếp. Một dãy các c ạnh liên tiếp kề nhau là một dãy các cạnh kế tiếp ch ỉ khi đ ỉnh chung của m ột c ạnh bất kì (không phải là khuyên) với cạnh đứng trước nó và cạnh đứng sau nó khác nhau. Trong một dãy cạnh kế tiếp, một cạnh của graph có th ể xuất hiện nhiều lần. Số m các cạnh được gọi là là độ dài của dãy c ạnh k ế ti ếp. Cho trước dãy cạnh kế tiếp H = (A1, e1, A2, e2 ,…, ek ,Ak+1), đỉnh A1 được gọi là đỉnh đầu vả đỉnh Ak+1 được gọi là đỉnh cuối của H. H còn được gọi là dãy cạnh kế tiếp nối A1 với Ak+1. Trong trường hợp A1 ≠ Ak, dãy cạnh kế tiếp H được gọi là dãy cạnh kế tiếp không khép kín. Còn khi A 1 = Ak thì H được gọi là dãy cạnh kế tiếp khép kín [1]. Một dãy cạnh kế tiếp e1, e2,…, ek với ei ≠ ej cho mọi i ≠ j được gọi là một xích đơn. Một xích đơn với đỉnh đầu là A và đỉnh cuối là B được gọi là một xích đơn nối A với B. 1.2.1.3. Chỉ số liên thông Khi biểu diễn một graph trên mặt phẳng, chúng ta đã th ấy rằng có nhiều khi hình biểu diễn của chúng là những cụm tách rời nhau không được nối với nhau. Tương ứng với mỗi hình rời nhau như vậy là một graph thành phần của graph đã cho mà ta sẽ gọi là một ph ần liên thông c ủa graph cho trước. Để chính xác hóa khái niệm liên thông, trước hết chúng ta nói hai đ ỉnh của một graph cho trước là liên thông với nhau nếu có một dãy cạnh k ế tiếp nối chúng với nhau trong graph đã cho. Một đỉnh cho trước luôn được coi là liên thông với chính nó (được nối với chính nó bởi một dãy cạnh kế tiếp có độ dài 0). Một graph được gọi là liên thông n ếu hai đ ỉnh b ất kì c ủa 10
nó liên thông với nhau. Quan hệ “liên thông” có những tính ch ất c ơ bản sau [1]: a) Mỗi đỉnh a của graph liên thông với chính nó. b) Nếu a liên thông với b thì b liên thông với a. c) Nếu a liên thông với b và b liên thông với c, thì a liên thông với c. Thực chất đây là một quan hệ tương đương trong tập hợp các đỉnh của graph. Quan hệ tương đương này chia tập đỉnh của graph thành các lớp có hai tính chất sau: 1) Các đỉnh thuộc cùng một lớp thì liên thông với nhau. 2) Các đỉnh không cùng thuộc một lớp không liên thông với nhau. Các lớp đỉnh này là đỉnh của graph thành phần liên thông trong graph cho trước, được gọi là thành phần liên thông của graph đã cho. 1.2.1.4. Đường đi trong graph Trong thực tế ứng dụng của cuộc sống, ta thường gặp một khái niệm khác của dãy cạnh kế tiếp là những dãy cạnh kế tiếp được tuân thủ nguyên tắc tối ưu là chúng không đi qua đỉnh nào của graph quá một lần. Một dãy cạnh kế tiếp trong một graph cho trước được gọi là một đường đi nếu chúng không đi qua đỉnh nào của graph quá 1 lần. Cũng tương tự như với dãy cạnh kế tiếp, nếu a và b là hai đỉnh đầu tiên và đ ỉnh cu ối cùng c ủa đường W, thì ta nói rằng W nối a với b. Chúng được gọi là đ ỉnh đầu và đỉnh cuối của con đường và được xem là phải khác nhau. Thông thường, đường đi được biểu diễn thông qua các đỉnh và các cạnh nối chúng, chẳng hạn: W = (p1, e1, p2, e2, p3, e3,…, ek-1, Pk) với pi là các đỉnh và ei là các cạnh của W. Đặc biệt, khi graph cho trước là graph đơn, thì ta có thể biểu diễn một đường đi thông qua t ập đ ỉnh c ủa nó, chẳng hạn: W = (p1 , p2 , p3 ,…, Pk) Số cạnh của một đường đi được gọi là độ dài của nó. 1.2.1.5. Chu trình của graph 11
Khi định nghĩa đường đi nối hai đỉnh a và b của một graph, ta luôn gi ả thiết rằng các đỉnh a và b này phải khác nhau. Trong trường h ợp a và b được nối với nhau bởi một cạnh, thì khi thêm cạnh (a, b) vào, ta thu đ ược từ con đường đã cho một chu trình. Như vậy chu trình là m ột dãy c ạnh k ế tiếp khép kín sao cho mỗi đỉnh của graph được đi qua không quá một lần. Chu trình được kí hiệu bởi việc đưa ra các cạnh và các đ ỉnh liên ti ếp nhau trên chu trình. Chẳng hạn, nếu chu trình C đi qua các đ ỉnh p 1, p2, …, pk và các cạnh e1, e2, …, ek thì ta viết: C = (p1 , e1 , p2 , e2 , …, pk , ek , p1) Trong trường hợp graph là một đơn graph, thì thay vì viết rõ các c ạnh và các đỉnh, chu trình được xác định duy nhất qua việc gọi tên các đỉnh nó đi qua. Chẳng hạn chu trình C ở trên có thể viết thành: C = (p 1 , p2 ,…, pk , p1). Số cạnh của chu trình được gọi là độ dài của chu trình và thông th ường hay được kí hiệu bởi l(C). Một khuyên lập thành một chu trình có độ dài 1. Một graph cho trước chỉ có chu trình có độ dài 2 nếu như nó có cạnh kép. Trong một graph đơn mỗi chu trình có độ dài ít nhất là 3. Một graph không đơn hiển nhiên luôn có ít nh ất một chu trình (có độ dài 1 hoặc 2). Trong graph đơn không phải lúc nào ta cũng có th ể tìm th ấy m ột chu trình. Chẳng hạn các graph biểu diễn sơ đồ cấp điện, hoặc các sơ đồ cấp nước chẳng hạn. 1.2.2. Graph có hướng 1.2.2.1. Khái niệm cơ sở của graph có hướng Một graph được gọi là graph (hữu hạn) có hướng khi nó chỉ có các cạnh có hướng mà ta còn x u y gọi là các cung. Hình 1.9. Biểu Một cung u được xác định nhờ điểm đầu x và diễn cạnh có hướng điểm cuối y, mà ta thường kí hiệu u = [x, y], trong đó x được gọi là đỉnh xuất phát và y được gọi là đỉnh đích của u. Chúng ta cũng nói rằng u liên hợp với đỉnh x và đỉnh y. 12
Graph có hướng G với tập đỉnh X và tập cạnh E thường được kí hiệu bởi G = [X, E]. Một graph có hướng cũng được biểu di ễn trên m ặt ph ẳng bởi một hình, trong đó các đỉnh được biểu diễn thành các đi ểm tô đậm, các cạnh có hướng và các cung là các đường liên tục và đ ược b ổ sung b ởi mũi tên thể hiện chiều đi từ đỉnh xuất phát tới đỉnh đích. Các cung có cùng đ ỉnh xuất phát và đỉnh đích được gọi là các cung song song. Nếu đỉnh xuất phát và đỉnh đích có cùng một cung u trùng nhau thì cung u này được gọi là khuyên có hướng. Một graph không có cung song song và khuyên có h ướng nào cả được gọi là graph có hướng đơn. Ta nói rằng cung u liên hợp với đỉnh x, nếu như x là đỉnh xuất phát hoặc là đỉnh đích của cung u. Nếu cung u liên hợp với đỉnh x, thì cung u được gọi là liên hợp hướng ra ngoài (liên hợp hướng vào trong) đối với đỉnh x là đỉnh xuất phát (đỉnh đích) của cung u. 1.3. Kết luận chương 1 Trong chương này chúng ta đã tìm hiểu tổng quan một số vấn đề về lý thuyết đồ thị: Đưa ra một số bài và vấn đề dẫn đến khái ni ệm Graph, đ ưa ra khái niệm cơ bản về Graph, Phân loại Graph, Lý thuy ết v ề Graph vô hướng, Graph có hướng… Trong đó có các khái niệm về bậc của đ ỉnh, ch ỉ số liên thông, khái niệm về đường đi và chu trình trong Graph… 13
Chương 2 MỘT SỐ THUẬT TOÁN CƠ BẢN TRÊN GRAPH 2.1. Biểu diễn graph trên máy tính Để giải quyết các bài toán về graph bằng máy tính, chúng ta cần phải lưu giữ graph trong bộ nhớ. Có nhiều biểu diễn cấu trúc đ ược s ử d ụng đ ể biểu diễn graph. Việc lựa chọn cấu trúc nào là tùy thuộc vào các ứng d ụng và các phép xử lý cần tác động lên graph trong ứng dụng ấy. Có hai cách biểu diễn graph thường dùng: Dùng ma trận kề và dùng danh sách kề. 2.1.1. Biểu diễn bằng ma trận lân cận [6] Giả sử G=(V, E) là một graph đơn có số đỉnh (Ký hiệu |V|) là n, không mất tính tổng quát có thể coi các đỉnh được đánh số từ 1, 2,…, n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông A = [aij] cấp n. Trong đó: • aij = 1 nếu (i, j) ∈ E • aij = 0 nếu (i, j) ∉ E • Quy ước aij = 0 với ∀ i; Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có đi ều n ếu như (i, j) là cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối đỉnh i với j. Ví dụ: Hình 2.1. Ma trận kề đồ thị vô hướng không trọng số và đồ thị có hướng không trọng số. 14