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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.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. 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2.
CÂY SINH ƯỚC 2.2 Đặc điểm của cây và cây có hướng Định lý 2. 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. Đị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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. Một cây có ít nhất hai đỉnh treo. Đị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., 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. 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. CÂY SINH ƯỚC Ta sẽ khẳng định rằng x1 và xk là các đỉnh treo, tức mỗi đỉnh này cho có một cạnh đi ra.
Giả sử ngược lại, x1 không phải là đỉnh treo, nên ngoài x2 nó còn phải nối với đỉnh xi nào đó, mà xi 6= x2. Vì H liên thông, nên x2 và xi có xích nối với nhau. Khi đó trong cây H có chu trình β = (x1 , x2 ,. Ta đã đi tới mâu thuẫn với tính chất của cây, nên x1 là đỉnh treo.
Tương tự ta cũng khẳng định được xk là đỉnh treo. Định lý được chứng minh. Mọi cây có hướng khi bỏ định hướng các cung đều trở thành cây. Giả sử cây có hướng H = (X, U ) có gốc tại x1 và đồ thị vô hướng G = (X, E) nhận được từ cây có hướng H sau khi bỏ định hướng các cung.
1) Đồ thị G liên thông Do điều kiện 1) mỗi đỉnh x 6= x2 đều có đường từ x1 đi tới. Thật vậy, giả sử x 6= x1 và từ x1 không có đường đi tới x. Nếu x là đỉnh biệt lập, thì nó không thể là đỉnh biệt lập, thì phải có đỉnh y là điểm xuất phát của một đường đi tới x. Nhưng do từ x1 không có đường đi tới x, nên y 6= x1 , mà nó cũng không là đỉnh cuối của bất kỳ cung nào.
Như vậy ta đã đi tới mâu thuẫn với điều kiện 1). Do đó, mọi đỉnh x 6= x1 từ x1 có đường đi tới nó, nên trong G mọi đỉnh x đều có xích nối với x1. Bởi vậy đồ thị G liên thông. 2) Đồ thị G không có chu trình Thật vậy, giả sử G có chu trình, thì trong H dãy cung tương ứng với các cạnh thuộc chu trình này sẽ hoặc lập thành một vòng hoặc có ít nhất hai cung có chung điểm cuối.
Như vậy, ta đi tới mâu thuẫn với điều kiện 1) hoặc điều kiện 3). Nên đồ thị G không có chu trình và liên thông. Do đó G là một cây. Định lý được chứng minh.
Một cây với n đỉnh có đúng n − 1 cạnh. Chứng minh bằng quy nạp theo số đỉnh n của cây. 1) Cơ sở quy nạp Với n = 2. Khi đó cây có một cạnh nên khẳng định thỏa mãn.
2) Quy nạp Giả sử khẳng định đã đúng với n = k , tức một cây gồm n = k + 1 đỉnh. 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. CÂY SINH ƯỚC Giả sử H là một cây tùy ý gồm k + 1 đỉnh. Khi đó H có ít nhất hai đỉnh treo.
Giả sử x là một trong những đỉnh treo của H. Ta loại đỉnh x và cạnh thuộc nó khỏi cây H và được đồ thị H 0 = H − {x}. Khi đó H 0 cũng là đồ thị liên thông. Giả sử ngược lại: H 0 là đồ thị không liên thông.
Khi đó nó phải có ít nhất hai thành phần liên thông. Giả sử G1 , G2 là hai trong các thành phần liên thông của H 0. Vì đồ thị H liên thông, nên từ đỉnh x phải xuất phát hai xích α1 , α2 : xích α1 nối x với G1 , còn xích α2 nối x với G2. Như vậy từ x xuất phát ít nhất hai cạnh.
Ta đi tới mâu thuẫn với tính chất đỉnh treo của x, nên đồ thị H 0 liên thông.