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

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....
Nội dung trích xuất từ tài liệu:
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 -................................................. ...