zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Thạc sĩ - Tiến sĩ - Cao học

Luận văn Thạc sĩ Khoa học: Ứng dụng đồ thị tìm ước số và xác định tập đồng dư

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:52

Báo xấu

12
lượt xem 4
download

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

Lý thuyết đồ thị là một chuyên ngành toán học hiện đại đã được ứng dụng vào nhiều ngành khoa học, kỹ thuật khác nhau, bởi vì lý thuyết đồ thị là phương pháp khoa học có tính khái quát cao và có tính ổn định vững chắc vì thế thông qua đồ thị có thể mã hóa các mối quan hệ của các đối tượng được nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Ứng dụng đồ thị tìm ước số và xác định tập đồng dư

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ PHẠM THỊ THỦY ỨNG DỤNG ĐỒ THỊ TÌM ƯỚC SỐ VÀ XÁC ĐỊNH TẬP ĐỒNG DƯ LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. ĐẶNG HUY RUẬN Hà Nội - Năm 2013
Mục lục MỞ ĐẦU 2 1 MỘT SỐ KHÁI NIỆM CƠ BẢN 4 1.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . 6 1.1.3 Xích, chu trình, đường và vòng . . . . . . . . . . . . . . . 7 1.1.4 Đồ thị liên thông và chu số . . . . . . . . . . . . . . . . . 10 1.2 Đồ thị được gán nhãn . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Nguồn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 CÂY SINH ƯỚC 16 2.1 Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Đặc điểm của cây và cây có hướng . . . . . . . . . . . . . . 18 2.2 Cây sinh ước . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2 Thuật toán xây dựng cây sinh ước . . . . . . . . . . . . . . 22 2.2.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 NGUỒN ĐỒNG DƯ 27 3.1 Nguồn đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Định nghĩa nguồn đồng dư . . . . . . . . . . . . . . . . . . 27 3.1.2 Định nghĩa Euclid . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.3 Thuật toán xây dựng nguồn đồng dư . . . . . . . . . . . . . 28 3.2 Nguồn giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 1
MỞ ĐẦU 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ị, logic 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. Lý thuyết đồ thị là một chuyên ngành toán học hiện đại đã được ứng dụng vào nhiều ngành khoa học, kỹ thuật khác nhau, bởi vì lý thuyết đồ thị là phương pháp khoa học có tính khái quát cao và có tính ổn định vững chắc vì thế thông qua đồ thị có thể mã hóa các mối quan hệ của các đối tượng được nghiên cứu. Vận dụng lý thuyết đồ thị để mô hình hóa các mối quan hệ trong giảng dạy sẽ chuyển thành phương pháp dạy học đặc thù và nâng cao được hiệu quả giảng dạy thúc đẩy quá trình tự học, tự nghiên cứu của học sinh theo hướng tối ưu hóa. Đặc biệt việc vận dụng lý thuyết đồ thị trong giảng dạy còn nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng tạo của học sinh. Từ nhận thức trên, đề tài "Ứng dụng đồ thị tìm ước số và xác định tập đồng dư" không những 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ự là đề tài em rất quan tâm và say mê nghiên cứu. “Ứng dụng đồ thị tìm ước số và tập đồng dư” là đề tài mang tính nghiên cứu lý thuyết, có tầm quan trọng và ý nghĩa thiết thực cao. Luận văn bao gồm phần mở đầu và ba chương: Chương 1. Một số khái niệm cơ bản Nhằm trình bày những khái niệm cơ bản nhất về đồ thị, là cơ sở tìm hiểu sâu sắc hơn các vấn đề tiếp theo. Mỗi phần gồm: Định nghĩa, định lý và các tính chất cơ bản của đồ thị. Ngoài ra, trong chương này còn trình bày một số phương pháp biểu diễn đồ thị, mỗi phương pháp đều có những ưu và nhược đ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. 2
MỞ ĐẦU Chương 2. Cây sinh ước Cây là một trường hợp riêng của đồ thị, để nghiên cứu hết các tính chất, khái niệm về cây cần cả một khối lượng kiến thức đồ sộ và đã có những đề tài nghiên cứu sâu về cây. Trong chương này chỉ đề cập tới những điểm chính nhất, cơ bản nhất về cây và tập trung khai thác những ứng dụng của nó. Những ứng dụng của cây thì rất nhiều, trong chương chỉ đề cập tới những ứng dụng cơ sở nhất, nhưng cũng thiết thực nhất. Đó là ứng dụng của cây để giải các bài toán tìm ước số. Chương 3. Nguồn đồng dư Đây là chương cuối cùng và là chương sẽ đề cập tới nhiều ứng dụng nhất. Trong chương này sẽ nhắc lại thuật toán khá gần gũi với cuộc sống. Đó là thuật toán xây dựng đồ thị xác định tập đồng dư, được gọi tắt là nguồn đồng dư. Từ cách xây dựng tập đồng dư ta có thể thấy được ứng dụng của nó vào việc chuyển các bài toán phức tạp trong tính toán về các bài toán giải đơn giản. Hà Nội, tháng 11 năm 2013. 3
Chương 1 MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1 Các khái niệm cơ bản Hai chữ “đồ thị” vẫn thường xuyên xuất hiện trong đời sống toán học và cả trong đời sống hàng ngày. Trong các giờ toán, chúng ta từng nói tới đồ thị của các hàm số. Hay trong các công sở, các nhân viên phải lập các biểu đồ theo dõi lượng tiêu thụ điện. Nói chung, khái niệm đồ thị là một khái niệm khá quen thuộc với chúng ta nhằm biểu diễn tương quan qua lại giữa hai hoặc nhiều đối tượng toán học khác nhau. Ở đây, khái niệm đồ thị vẫn được dùng theo nghĩa đó nhưng nó mang tính trừu tượng hơn. 1.1.1 Định nghĩa đồ thị Tập hợp X 6= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của X được gọi là một đồ thị,đồng thời được ký hiệu bằng G(X, E) hoặc bằng G = (X, E) hoặc bằng G(X). Các phần tử của X được gọi là đỉnh. Cặp đỉnh không sắp thứ tự gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng hay cung. Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, còn đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung thì nó được gọi là đồ thị hỗn hợp hay đồ thị hỗn tạp. Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh (hai hoặc nhiều hơn hai cung và hướng). Các cạnh (cung) này được gọi là các cạnh (cung) bội. 4
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Một cung hay một cạnh có thể bắt đầu và kết thúc tại cùng một đỉnh. Cung hay cạnh loại này được gọi là khuyên hay nút. Cặp đỉnh x, y được nối với nhau bằng cạnh (cung) a thì x, y được gọi là các đỉnh hay hai đầu của cạnh (cung) a, và a được gọi là cạnh (cung) thuộc đỉnh x, y . Nếu cung b xuất phát từ đỉnh u và đi vào đỉnh v , thì u được gọi là đỉnh đầu, còn v được gọi là đỉnh cuối của cung b. Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu x 6= y và là hai đầu của cùng một cạnh hay một cung. Đối với mọi đỉnh x dùng D(x) để chỉ tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh; D+ (x) để chỉ tập đỉnh, mà mỗi đỉnh này từ x có cung đi tới; D− (x) dùng để chỉ tập đỉnh mà mỗi đỉnh này có cung đi tới x. Hai cạnh (cung) a, b được gọi là kề nhau nếu chúng khác nhau và có chung đỉnh (nếu a, b là cung thì không phụ thuộc vào đỉnh chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của cung b). Ví dụ 1.1. Cho đồ thị hỗn hợp có khuyên G(X, E) với tập đỉnh: X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }, Tập cạnh và cung: E = {(x1 , x2 ) , (x2 , x3 ) , (x4 , x6 ) , (x5 , x6 ) , (x3 , x3 ) , (x1 , x6 ) , (x5 , x5 )} = { a1 , a2 , a3 , a4 , a5 , b1 , b2 } Trong đó a1 , a2 , a3 , a4 , a5 - các cạnh, b1 , b2 - các cung, cung b1 có x1 là đỉnh đầu, x6 là đỉnh cuối. Đồ thị G(X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường gọi là đồ thị. Đồ thị G(X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau từ hai cạnh trở lên được gọi là đa đồ thị. Đa đồ thị vô hướng là một bộ G(X, E), trong đó: (1) X 6= ∅ là tập hợp hữu hạn gồm các đỉnh của đồ thị. (2) E là một họ các cặp không có thứ tự của X gọi là các cạnh. Đa đồ thị có hướng là một bộ G(X, E), trong đó: (1) X 6= ∅ là tập hợp hữu hạn gồm các đỉnh của đồ thị. (2) E là một họ các cặp có thứ tự của X gọi là các cung. Một đồ thị hay đa đồ thị có khuyên, thì nó được gọi là đồ thị hay đa đồ thị có khuyên. 5
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Đồ thị vô hướng (có hướng) G(X, E) được gọi là đồ thị đầy đủ, nếu mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (một cung với chiều tùy ý). Đồ thị (đa đồ thị) G(X, E) được gọi là hữu hạn nếu số đỉnh của nó hữu hạn, tức tập X có lực lượng hữu hạn. Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng hoặc không có hướng. Số cạnh và cung thuộc đỉnh x được gọi là bậc của đỉnh x và ký hiệu bằng m(x). Đỉnh có bậc bằng 0 gọi là đỉnh biệt lập. Đỉnh có bậc bằng 1 gọi là đỉnh treo. Cạnh (cung) có ít nhất một đầu là đỉnh treo được gọi là cạnh (cung) treo. 1.1.2 Biểu diễn đồ thị bằng hình học Đồ thị có nhiều cách biểu diễn, nhưng trong phần này chỉ trình bày cách biểu diễn bằng hình học. Giả sử có đồ thị G(X, E) Để có dạng biểu diễn hình học của G ta cần biểu diễn đỉnh và cạnh. Biểu diễn đỉnh: Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các phần tử của tập X và dùng ngay ký hiệu các phần tử này để ghi trên các điểm tương ứng. Biểu diễn cạnh: Nếu cạnh với hai đỉnh đầu là x, y thì nó được biểu diễn bằng một đoạn thẳng hay một đoạn cong nối giữa hai điểm x, y và không đi qua các điểm tương ứng trung gian khác. Biểu diễn cung: Nếu cung có đỉnh đầu là x, đỉnh cuối là y , thì nó được biểu diễn bằng một đoạn thẳng hoặc một đoạn cong được định hướng đi từ x sang y và không qua các điểm tương ứng trung gian khác. Hình nhận được gọi là dạng biểu diễn hình học của đồ thị G(X, E). Đôi khi người ta cũng gọi dạng biểu diễn hình học là đồ thị. 6
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Ví dụ 1.2. Dạng biểu diễn hình học của đồ thị G(X, E) cho trong ví dụ 1.1: 1.1.3 Xích, chu trình, đường và vòng Đối với đồ thị (đa đồ thị) vô hướng có khái niệm xích (dây chuyền) và chu trình, còn đối với đồ thị (đa đồ thị) có hướng tồn tại khái niệm đường và vòng. Tuy vậy, người ta vẫn thường dùng khái niệm đường cho cả đồ thị và đa đồ thị vô hướng. 1.1.3.1. Xích, chu trình Giả sử G(X, E) là một đồ thị hay đa đồ thị vô hướng. Dãy α các đỉnh của G (X, E) : α = [x1 , x2 , ..., xi , xi+1 , ..., xn−1 , xn ] được gọi là một xích hay một dây chuyền, nếu ∀i (1 ≤ i ≤ n − 1) cặp đỉnh xi , xi+1 kề nhau (có cạnh nối với nhau). Các đỉnh x1 , xn được gọi là hai đỉnh đầu của xích α được gọi là độ dài của xích α, đồng thời được ký hiệu bằng |α|. Các đỉnh x1 , xn được gọi là hai đỉnh đầu của xích α. Ngoài ra, còn nói rằng xích α nối giữa các đỉnh x1 và xn . Để chỉ rõ đỉnh đầu và đỉnh cuối ta còn ký hiệu α bằng α [x1 , xn ]. Một xích với hai đầu trùng nhau, được gọi là một chu trình. Xích (chu trình) α được gọi là xích (chu trình) đơn (sơ cấp hay cơ bản) nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần. 7
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Ví dụ 1.3. Cho đồ thị: α1 = x1 x2 x3 x4 x5 x6 là xích đơn và sơ cấp. α2 = x2 x3 x4 x5 x1 x2 x5 là xích đơn, nhưng không sơ cấp. α3 = x1 x2 x4 x5 x6 x1 là chu trình đơn và sơ cấp. α4 = x1 x5 x2 x4 x5 x6 x1 là chu trình đơn, nhưng không là chu trình sơ cấp. 1.1.3.2. Đường, vòng Giả sử G(X, E) là đồ thị hay đa đồ thị có hướng. Dãy đỉnh β của G(X, E) β = [x1 , x2 , ..., xi , xi+1 , ..., xm−1 , xm ] được gọi là một đường hay một đường đi, nếu ∀i (1 ≤ i ≤ m − 1) đỉnh xi là đỉnh đầu, còn xi+1 là đỉnh cuối cùng một cung nào đó từ xi → xi+1 . Tổng số vị trí của tất cả các cung xuất hiện trong β được gọi là độ dài của đường β , đồng thời được ký hiệu bằng |β|. Đỉnh x1 được gọi là đỉnh đầu, đỉnh xm được gọi là đỉnh cuối của đường β . Người ta còn nói rằng, đường β xuất phát từ đỉnh x1 và đi tới đỉnh xm . Đường β còn được ký hiệu bằng β [x1 , xm ]. Một đường có đỉnh đầu và đỉnh cuối trùng nhau được gọi là một vòng. Đường (vòng) β được gọi là đường (vòng) đơn (sơ cấp hay cơ bản), nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần. 8
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Ví dụ 1.4. Cho đồ thị có hướng: β = [x1 x2 x3 x4 x5 x6 ] là đường đơn và đường sơ cấp. β1 = [x2 x3 x4 x5 x7 x6 x2 ] là vòng đơn và vòng sơ cấp. β2 = [x7 x2 x3 x4 x5 x7 x6 ] là đường đơn, nhưng không là đường sơ cấp. β3 = [x1 x2 x3 x4 x2 ] không là đường. β4 = [x1 x7 x2 x5 x7 x2 x4 ] không là đường đơn, nhưng không là vòng sơ cấp. β5 = [x1 x7 x2 x5 x7 x6 x1 ] là vòng đơn, nhưng không là vòng sơ cấp. Hai xích (chu trình) được gọi là rời nhau, nếu chúng không có cạnh chung. Hai đường (vòng) gọi là rời nhau nếu chúng không có cạnh chung. Để dễ hình dung ta gọi chu trình có độ dài 3, 4, 5, ..., n là chu trình tam giác, tứ giác, ngũ giác, ..., n giác. 1.1.3.3. Một số tính chất Định lý 1.1. Trong một đồ thị vô hướng với n (n ≥ 3) đỉnh và các đỉnh đều có bậc không nhỏ hơn 2 luôn luôn tồn tại chu trình sơ cấp. Chứng minh. Vì đồ thị hữu hạn, mà mỗi xích sơ cấp đi qua từng đỉnh không quá một lần, nên số xích sơ cấp trong đồ thị G(X, E) là một số hữu hạn. Bởi vậy luôn luôn xác định được xích sơ cấp có độ dài cực đại trong đồ thị G(X, E). Giả sử α = [x1 , x2 , ..., xk−1 , xk ] là một trong những xích sơ cấp có độ dài cực đại. Do bậc của mỗi đỉnh thuộc G không nhỏ hơn 2, nên x1 phải kề với một đỉnh y nào đó khác x2 . Ngược lại, nếu đỉnh y khác với đỉnh xi (3 ≤ i ≤ k) thì xích sơ cấp 9
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN α0 = [y, x1 , x2 , ..., xk−1 , xk ] có độ dài |α0 | = |α| + 1 > |α|. Như vậy, đã đi tới mâu thuẫn với tính độ dài cực đại của xích α, nên y = xi (3 ≤ i ≤ k) và trong đồ thị có chu trình sơ cấp β = [x1 , x2 , ..., xi−1 , xi , x1 ]. Định lý 1.2. Trong một đồ thị vô hướng với n đỉnh (n ≥ 4) và các đỉnh đều có bậc không nhỏ hơn 3 luôn luôn tồn tại chu trình sơ cấp có độ dài chẵn. Chứng minh. Giả sử α là một trong những xích sơ cấp độ dài cực đại α = (x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj−1 , xj , xj+1 , ..., xk−1 , xk ) Vì α có độ dài cực đại, mà bậc x1 không ít hơn 3, nên ngoài x2 thì x1 phải kề thêm với hai đỉnh khác thuộc α: xi (3 ≤ i ≤ k) , xj (3 ≤ j ≤ k). Khi đó được hai chu trình sơ cấp: α1 = (x1 , x2 , ..., xi−1 , xi , x1 ) α2 = (x1 , x2 , ..., xi , xi+1 , ..., xj−1 , xj , x1 ) Nếu một trong hai chu trình α1 , α2 có độ dài chẵn. Khẳng định được chứng minh. Ngược lại nếu cả hai chu trình α1 , α2 đều có độ dài lẻ. Khi đó xích α3 = (x1 , x2 , ..., xi−1 , xi ) có độ dài chẵn và xích α4 = (xi , xi+1 , ..., xj , xj+1 , x1 ) có độ dài chẵn,nên chu trình (x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj , xj+1 , x1 ) có độ dài chẵn. Khẳng định được chứng minh. 1.1.4 Đồ thị liên thông và chu số 1.1.4.1. Đồ thị liên thông Hai đỉnh x, y được gọi là cặp đỉnh liên thông, nếu hoặc giữa x và y có ít nhất một xích nối với nhau, hoặc tồn tại ít nhất một đường đi từ x sang y hoặc từ y sang x. Đồ thị vô hướng G(X, E) được gọi là đồ thị liên thông, nếu mọi cặp đỉnh của nó đều liên thông với nhau. Đồ thị có hướng G(X, U ) được gọi là đồ thị liên thông mạnh, nếu mọi cặp đỉnh của nó đều liên thông. Giả sử a là đỉnh bất kì của đồ thị G. Dùng Ca để ký hiệu tập con các đỉnh của G, gồm đỉnh a và tất cả các đỉnh liên thông với a trong đồ thị G. Đồ thị con của G có tập đỉnh Ca được gọi là một thành phần liên thông của đồ thị G. 10
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1.4.2. Chu số Giả sử G(X, U ) là một đa đồ thị vô hướng với n đỉnh, m cạnh, p thành phần liên thông. Đặt ρ (G) = n − p. Đại lượng m − ρ (G) = m − n + p được gọi là chu số của đa đồ thị G và được ký hiệu bằng ν (G). 1.2 Đồ thị được gán nhãn 1.2.1 Định nghĩa Giả sử có bảng chữ cái Σ = {t1 , t2 , ..., ti , ti+1 , ..., tn }. Đồ thị G mà mỗi cạnh c của nó được đặt tương ứng với ký hiệu ti ∈ Σ (trên cạnh c ghi ký hiệu ti ) được gọi là đồ thị gán nhãn. Ký hiệu ti được gọi là nhãn của cạnh c. Đồ thị với nhãn của tất cả các cạnh đều là số được gọi là đồ thị có trọng số. Ví dụ 1.5. S = {a, b, g} Đồ thị được gán nhãn (trên bảng chữ cái S = {a, b, g}). 11
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Ví dụ 1.6. Đồ thị được gán nhãn trên {0, 1, 2, 3, 4} G1 là đồ thị có trọng số. 1.2.2 Nguồn 1.2.2.1. Định nghĩa nguồn Nguồn là một đa đồ thị có hướng được gán nhãn, mà trên đó tách ra một đỉnh được gọi là đỉnh vào (đỉnh vào được đặt trong một ô tròn có mũi tên đi vào) và một tập con các đỉnh được gọi là các đỉnh ra hay đỉnh kết (mỗi đỉnh kết được đặt trong một ô chữ nhật). Ví dụ 1.7. Cho nguồn I Nguồn có đỉnh vào là v , các đỉnh ra là đỉnh x5 , x6 . 12
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 1.2.2.2. Nhãn của đường Giả sử ∀a, b ∈ I và T là một đường nào đó đi từ đỉnh a đến đỉnh b và cung cis có nhãn là tis (1 ≤ s ≤ n). Khi đó dãy ký hiệu ti1 ti2 ...tis ...tin được gọi là nhãn của đường T và ký hiệu là T¯ = ti1 ti2 ...tis ...tin Ví dụ 1.8. T là đường đi từ x2 đến x5 (ở ví dụ 1.7.) Ta gọi T¯ = t7 t2 t3 - nhãn của T. Ngoài ra còn một đường khác từ x2 đến x5 : Ta có nhãn của T1 là T1 = t7 t4 . Tập gồm nhãn của tất cả các đường xuất phát từ đỉnh a và đi đến đỉnh b trong nguồn I được ký hiệu là NI (a, b) . Trong ví dụ 1.8. ta có: NI (x2 , x5 ) = T , T1 = {t7 t2 t3 , t7 t4 } 1.2.2.3. Nhãn của nguồn Giả sử nguồn G có đỉnh vào là V là tập con các đỉnh ra là F Tập gồm nhãn của tất cả các đường xuất phát từ đỉnh vào (V ) và đi tới các S đỉnh kết (F ), NI (V, a) được gọi là nhãn của nguồn I đồng thời ký hiệu bằng a∈F N (I) S N (I) = NI (V, a). a∈F 13
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Ví dụ 1.9. Hãy lập nguồn sinh tất cả các số tự nhiên N = {0, 1, 2...}, tức lập nguồn I , mà nhãn của nó là tập số tự nhiên. Lời giải. Để có nguồn I ta cần xác định đỉnh và cung: 1. Đỉnh Nguồn I gồm 3 đỉnh: 2. Cung a) Sinh số 0: Để sinh số 0 là số tự nhiên duy nhất bắt đầu và kết thúc bằng 0, nên ta kẻ một cung từ đỉnh v sang s1 với nhãn là 0. b) Tất cả các số tự nhiên còn lại đều không bắt đầu bằng 0. Bởi vậy, từ đỉnh v sang đỉnh s2 kẻ 9 cung với nhãn tương ứng là 1, 2, 3, 4, 5, 6, 7, 8, 9. c) Mỗi số tự nhiên có thể có độ dài tùy ý và kết thúc bằng một trong các chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, nên để sinh các đoạn cuối của các số thì tại đỉnh s2 ta vẽ thêm 10 khuyên với các nhãn 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Từ đó ta có nguồn sinh các số tự nhiên như sau: 14
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Có thể rút gọn thành đồ thị sau: Trong bài luận văn này xin phép sử dụng dạng rút gọn. Ví dụ: Muốn sinh số 2013: - Từ đỉnh vào đi theo cung 2 đến s2 - Tại đỉnh s2 ta lần lượt đi theo khuyên 3 nhãn 0, 1, 3. - Khi đó đường ta đã đi xuất phát từ đỉnh vào V với nhãn là 2013 và có đỉnh cuối là đỉnh kết (s2 ), nên đường này sinh được số 2013. 15
Chương 2 CÂY SINH ƯỚC Cây là một khái niệm đặc biệt trong lý thuyết đồ thị được Cayley nghiên cứu từ rất sớm bởi vì loại đồ thị này đóng vai trò quan trọng trong lý thuyết mạng. Trong toán học nhờ cây có thể thực hiện xác định thứ tự, xác định số cách sắp xếp, số các số nguyên thỏa mãn những điều kiện nào đó và ước của các số nguyên dương... Trong luận văn này xin trình bày ứng dụng của cây để xác định số ước của các số nguyên dương. 2.1 Cây 2.1.1 Định nghĩa Một đồ thị vô hướng liên thông, không có chu trình và có ít nhất hai đỉnh được gọi là một cây (Hình 2.1). 16
Chương 2. CÂY SINH ƯỚC Đồ thị hữu hạn có hướng G = (X, U ) là cây có hướng gốc x1 ∈ X , nếu nó có ít nhất hai đỉnh và thỏa mãn ba điều kiện sau: 1) Mỗi đỉnh khác x1 là điểm cuối của một cung duy nhất. 2) Đỉnh x1 không là điểm cuối của bất kỳ một cung nào. 3) Đồ thị G(X, U ) không có vòng (Hình 2.2). Một đồ thị vô hướng, mà mỗi một thành phần liên thông của nó đều là cây, được gọi là bụi (Hình 2.3). Hình 2.3 17
Chương 2. CÂY SINH ƯỚC 2.1.2 Đặc điểm của cây và cây có hướng Định lý 2.1. Giả sử H là một đồ thị vô hướng với n đỉnh (n > 1). Để đặc trưng cho một cây, thì sáu tính chất sau đây tương đương: (1) H liên thông và không có chu trình; (2) H không có chu trình và n − 1 cạnh; (3) H liên thông và có n − 1 cạnh; (4) H không có chu trình và nếu thêm một cạnh nối giữa hai đỉnh bất kì không kề nhau, thì đồ thị nhận được H 0 có một chu trình (và chỉ có một mà thôi); (5) H liên thông và khi bớt một cạnh bất kì thì đồ thị mất tính liên thông; (6) Mọi cặp đỉnh của H đều được nối với nhau bằng một xích và chỉ một mà thôi. Chứng minh. Định lý được chứng minh theo phương pháp vòng tròn. Ký hiệu số cạnh của đồ thị H bằng m, số thành phần liên thông bằng p. Khi đó chu số của đồ thị H (số chu trình của H ) là ν (H) = m − n + p (1) ⇒ (2) : Theo tính chất (1): p = 1 và chu số ν (H) = m − n + 1 = 0; Nên m = n − 1, tức đồ thị H có n − 1 cạnh. Ta có tính chất (2). (2) ⇒ (3) : theo tính chất (2): m = n − 1 và ν (H) = 0, nên ta có: ν (H) = m − n + p = n − 1 − n + p = 0 Suy ra p = 1, nên đồ thị H liên thông. Ta có tính chất (3). (3) ⇒ (4): Theo tính chất (3): Đồ thị H liên thông và có n − 1 cạnh, nên p − 1 và m = n − 1. Do đó ν (H) = m − n + p = n − 1 − n + 1 = 0, Nên đồ thị H không có chu trình. Ngoài ra, nếu thêm vào một cạnh nối giữa hai đỉnh không kề nhau, thì đồ thị H 0 nhận được sẽ có chu số: ν (H) = m + 1 − n + 1 = n − 1 + 1 − n + 1 = 1, 0 Nên đồ thị H có chu trình và chỉ có một mà thôi. Ta có tính chất (4). (4) ⇒ (5) : Lấy hai đỉnh bất kỳ x, y của đồ thị H . Theo tính chất (4): Nếu thêm vào cạnh (x, y), thì đồ thị mới nhận được H 0 có chu trình. Điều này chứng tỏ cặp đỉnh x, y đã có xích nối với nhau, tức H liên thông. Giả sử bớt đi một cạnh nào đó, chẳng hạn (u, v) mà đồ thị nhận được vẫn liên thông. Điều này chứng tỏ trong đồ thị H giữa các đỉnh u, v ngoài cạnh (u, v) còn có xích nối giữa chúng, tức là H có ít nhất một chu trình đi qua các đỉnh 18
Chương 2. CÂY SINH ƯỚC u, v . Ta đi tới mâu thuẫn với tính chất (4): Đồ thị (H) không có chu trình. Bởi vậy, nếu bớt đi một cạnh tùy ý thì đồ thị nhận được từ H sẽ không liên thông. Ta được tính chất (5). (5) ⇒ (6) : Giả sử trong đồ thị H tồn tại cặp đỉnh nào đó, chẳng hạn x, y được nối với nhau bằng từ hai xích trở lên. Khi đó, nếu ta bỏ đi một cạnh nào đó thuộc một trong hai xích này, thì xích còn lại vẫn đảm bảo cho x, y liên thông. Như vậy, ta đã đi tới mẫu thuẫn với tính chất (5). Do đó, mọi cặp đỉnh của H đều được nối với nhau bằng một xích và chỉ một mà thôi. T được tính chất (6). (6) ⇒ (1) : Giả sử H không liên thông. Khi đó có ít nhất một cặp đỉnh không có xích nối với nhau, nên mâu thuẫn với tính chất (6). Giả sử H có chu trình. Khi đó có ít nhất một cặp đỉnh nằm trên chu trình này được nối với nhau bằng ít nhất hai xích. Như vậy ta cũng đi đến mâu thuân với tính chất (6). Bởi vậy đồ thị H có tính chất (1). Định lý được chứng minh. Định lý 2.2. Một cây có ít nhất hai đỉnh treo. Chứng minh. Định lý này có hai cách chứng minh: Chứng minh thứ nhất Giả sử cây H có không quá một đỉnh treo. Ta tưởng tượng có một khách bộ hành đi theo đồ thị H , xuất phát từ đỉnh tùy ý (trong trường hợp không có đỉnh treo) hay từ đỉnh treo (trong trường hợp đồ thị có một đỉnh treo): Nếu hành khách tự cấm mình không đi qua cạnh nào hai lần, khi đó không thể gặp đỉnh nào hai lần (do đồ thị H không có chu trình). Mặt khác, khi tới mỗi đỉnh hành khách đó luôn luôn có thể đi ra bằng một cạnh mới (vì mỗi đỉnh khác đỉnh đều xuất phát đều có ít nhất hai cạnh). Như vậy, hành khách sẽ đi mãi không bao giờ dừng lại. Đó là điều không thể xảy ra vì đồ thị H có hữu hạn đỉnh. Bởi vậy đồ thị H phải có ít nhất hai đỉnh treo. Định lý được chứng minh. Chứng minh thứ hai Giả sử H = (X, E) là một cây. Vì H là đồ thị hữu hạn, nên trong H chỉ có một hữu hạn xích. Bởi vậy xác định được những xích có độ dài cực đại. Giả sử α = (x1 , x2 , ..., xk−1 , xk ) là một trong những xích có độ dài cực đại. Vì H có ít nhất hai đỉnh, nên |α| ≥ 1. Bởi vậy k > 1. 19

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2431 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.