Luận văn Phân tích tai của đồ thị và đồ thị series parallel

1 là một tai của P0 ∪ P1 ∪ . . . ∪ Pi và hai đầu mút của Pi (có thể trùng nhau) thuộc P0∪P1∪ . . .∪Pi−1. Tai mở là tai có hai đầu mút rời nhau, tai đóng là tai có hai đầu mút trùng nhau. Phân tích tai mở loại 1 (Open ear decomposition - OED) là phân tích tai mà mọi tai của nó (trừ tai đầu tiên) đều là tai mở. Hình 1.14: Ví dụ về phân tích tai và phân tích tai mở loại 1. 25 Chú ý 2. Một đồ thị có thể có nhiều phân tích tai. Như đồ thịG trong hình 1.14, nếu ta coi P3 là tai đầu tiên (P3 = P0) thì G sẽ có phân tích tai mới như trong hình 1.15. Hình 1.15: Phân tích tai mới thu được khi thay P3 = P0. Tiếp theo, chúng tôi trình bày hai định lý thể hiện mối liên hệ giữa phân tích tai với tính liên thông của đồ thị. Định lý 1.4.1. [5]Một đồ thị là 2 - liên thông khi và chỉ khi nó có một phân tích tai mở. Hơn nữa, mọi xích trong một đồ thị 2 - liên thông là xích khởi tạo đầu tiên trong một phân tích tai nào đó. Chứng minh. Điều kiện đủ: Vì một xích là 2 - liên thông nên để chứng minh điều kiện đủ ta chỉ cần chỉ ra rằng khi thêm một tai mở vào một đồ thị 2 - liên thông thì đồ thị mới thu được cũng 2 - liên thông. Giả sử u, v là hai đầu mút của tai P được thêm vào đồ thị 2 - liên thông G. Do thêm một cạnh vào đồ thị không làm mất đi tính liên thông nên G + uv là 2 - liên thông. Một chuỗi các phép phân chia cạnh sẽ chuyển G+ uv thành đồ thị G ∪ P , trong đó P là một tai (hình 1.16). Theo hệ quả 1.3.2, mỗi phép phân chia cạnh bảo toàn tính 2 - liên thông nên G ∪ P là 2 - liên thông. Điều kiện cần: Cho G là đồ thị 2 - liên thông, ta sẽ xây dựng một phân tích tai từ một xích C trong G. Đặt Go = C, gọi Gi là đồ thị con thu được bằng 26 Hình 1.16: Chuỗi các phép phân chia cạnh uv chuyển đồ thị G+ uv thành G ∪ P . cách thêm i tai. Nếu Gi 6= G, ta có thể chọn một cạnh uv thuộc G− E(Gi) và một cạnh xy ∈ E(Gi). Do G là 2 - liên thông nên tồn tại một xích C ′ đi qua uv, xy. Đặt P là đường trong C ′ mà chứa uv và có duy nhất hai đỉnh chung với Gi, hai đỉnh đó cũng là hai đầu mút của của P . Khi đó ta thêm P vàoGi và thu được đồ thị Gi+1 với P là một tai mở của Gi+1. Tiếp tục quá trình trên cho đến khi hấp thụ hết các cạnh của G ta thu được một phân tích tai mở của G. Qua cách xây dựng trên ta thấy rằng mỗi một xích C sẽ cho ta một phân tích tai khác nhau, do đó mỗi xích trong đồ thị G đều là tai đầu tiên của một phân tích tai nào đó. Định lý 1.4.2. [5] Một đồ thị là 2 - cạnh liên thông khi và chỉ khi nó có một phân tích tai và mọi xích trong đồ thị đó đều là tai đầu tiên trong một phân tích tai nào đó. Chứng minh. Điều kiện đủ: Để chứng minh điều kiện đủ, ta chỉ cần chứng minh rằng khi thêm một tai đóng hay mở vào một đồ thị 2 - cạnh liên thông ta cũng thu được một đồ thị 2 - cạnh liên thông. Theo định lý 1.2.1, cạnh cắt là cạnh không nằm trên một xích nào. Do đó một đồ thị là 2 - cạnh liên thông nếu mỗi cạnh của nó đều nằm trên một xích nào đó. Giả sử G là đồ thị 2 - cạnh liên thông. Khi ta thêm một tai đóng vào G tức là ta thêm một xích vào G thì đồ thị mới thu được cũng là 2 - cạnh liên thông. Nếu ta thêm một tai mở P vào G thì đường nối hai đầu mút của P trong G kết hợp với P tạo thành một xích. Do đó 27 ta cũng thu được một đồ thị 2 - cạnh liên thông. Điều kiện cần: Giả sử G là đồ thị 2 - cạnh liên thông, ta sẽ xây dựng một phân tích tai của G. Gọi Po là một xích trong G. Xét phân tích tai Po ∪ . . .∪Pi của đồ thị con Gi của G. Nếu Gi 6= G, ta sẽ tìm một tai để thêm vào Gi. Do G là 2 - cạnh liên thông nên tồn tại một cạnh uv ∈ E(G) − E(Gi) với u ∈ V (Gi). DoG là 2 - cạnh liên thông nên uv nằm trên một xích C. Gọi P = C ∩ (E(G)− E(Gi)), thêm P vào Gi ta được một đồ thị con Gi+1 = Gi ∪ P với P là một tai đóng hoặc mở. Tiếp tục quá trình trên cho đến khi hấp thụ hết các cạnh của G ta thu được một phân tích tai của G. Qua cách xây dựng trên ta thấy rằng mỗi một xích C sẽ cho ta một phân tích tai khác nhau, do đó mỗi xích trong đồ thị G đều là tai đầu tiên của một phân tích tai nào đó. 1.4.2 Phân tích tai loại 2 Định nghĩa 1.4.2. [5] Một phân tích tai loại 2 của đồ thị G là sự phân chia các cạnh của G thành một dãy các tai E1, E2, . . . , En. Trong đó mỗi tai là một đường thỏa mãn các tính chất sau: 1. Nếu hai đỉnh của đường trùng nhau thì chúng phải là đầu mút của đường. 2. Hai đầu mút của của mỗi taiEi, i > 1 nằm trên các taiEj, Ej′ với j, j′ < i 3. Không có điểm trong nào của Ei nằm trên Ej . Định nghĩa 1.4.3. [5] Phân tích tai mở loại 2 là một phân tích tai mà hai đầu mút của mỗi tai phải phân biệt. Ví dụ 1.4.1. Hình 1.17 cho ta ví dụ về phân tích tai và phân tích tai mở loại 2. Nhận xét 1.4.1. Ta thấy rằng mọi phân tích tai loại 1 đều có thể coi là phân tích tai loại 2 bằng cách chia tai đầu tiên Po thành hai tai: P ′o = ef, P ′ 1 = Po − ef 28 Hình 1.17: Phân tích tai và phân tích tai mở loại 2. với ef là một cạnh bất kì của Po. Ngược lại, có phân tích tai là loại 2 nhưng không phải loại 1. Ví dụ phân tích tai mở trong hình 1.17 là một phân tích loại 2 nhưng không phải loại 1 do đồ thị đó không phải 2 - liên thông. Quan sát phân tích tai loại 2 ta thấy rằng một phân tích tai (tương ứng phân tích tai mở) loại 2 thu được khi ta gắn các đồ thị con 2 - liên thông cực đại (tương ứng 2 - cạnh liên thông cực đại) của đồ thị ban đầu lên tai đầu tiên. Do đó ta có thể tìm ra mối liên hệ giữa phân tích tai loại 2 và tính liên thông bằng cách định nghĩa các đồ thị con 2 - liên thông cực đại (2 - cạnh liên thông cực đại) như sau: Định nghĩa 1.4.4. Một khối (block) của đồ thịG là một đồ thị con 2 - liên thông cực đại của G. Tập các khối của một đồ thị liên thông có dạng một cây với các nút là các khối và các đỉnh cắt của đồ thị. Hai nút được nối với nhau bằng một cạnh trong các trường hợp sau: 1. Một nút là một đỉnh cắt và nút còn lại là khối chứa đỉnh đó. 2. Cả hai nút đều là các đỉnh cắt và chúng được nối với nhau bằng một cạnh của đồ thị. Khối lá là khối chỉ chứa duy nhất một đỉnh cắt (tương ứng với lá của cây các khối). 29 Tương tự ta có định nghĩa về đồ thị con 2 - cạnh liên thông cực đại. Định nghĩa 1.4.5. Đồ thị con 2 - cạnh liên thông cực đại của đồ thị G là đồ thị con liên thông cực đại của G mà sau khi xóa đi một cạnh bất kì thì phần còn lại vẫn liên thông. Tập các đồ thị con 2 - cạnh liên thông cực đại của một đồ thị có dạng một cây với các nút là các đồ thị con 2 - cạnh liên thông cực đại được nối với nhau bằng cạnh cắt của đồ thị. Ví dụ 1.4.2. Cho đồ thị G như trong hình 1.18, hình 1.18i là cây các khối của G còn hình 1.18ii là cây các đồ thị con 2 - cạnh liên thông cực đại của G. Hình 1.18: Đồ thị G, cây các khối và cây các đồ thị con 2 - cạnh liên thông cực đại của G. Nhận xét 1.4.2. Qua việc nghiên cứu về phân tích tai của đồ thị, chúng tôi có hai nhận xét như sau: 1. Đồ thị G có phân tích tai mở loại 2 khi và chỉ khi cây các khối của G là một đường. 2. Đồ thị G có phân tích tai loại 2 khi và chỉ khi cây các đồ thị con 2 - cạnh liên thông của G là một đường. 30 Chúng tôi có ý tưởng chứng minh điều 1 (điều 2 có thể chứng minh tương tự) như dưới đây. Tuy nhiên chúng tôi chưa thể chứng minh chi tiết và chặt chẽ nên xin được viết ở đây như hai câu hỏi mở. • Điều kiện cần: Chứng minh quy nạp theo số tai của G. Nếu G chỉ có một tai E1 thì điều kiện cần hiển nhiên đúng do cây các khối của G chính là E1. Giả sử điều kiện cần đúng nếu số tai nhỏ hơn k, ta chứng minh điều kiện cần vẫn đúng khi thêm tai thứ k vào đồ thị. Nếu tai thứ k có hai đầu mút nằm trên các tai khác tai đầu tiên thì hoặc số khối không đổi hoặc số khối giảm đi một. Nếu cả hai đầu mút của tai thứ k đều nằm trên tai đầu thì số khối hoặc giữ nguyên hoặc tăng một hoặc giảm một. Khi đó cây các khối vẫn là đường ban đầu (có thể thêm hoặc bớt đỉnh) (hình 1.19). Hình 1.19: Hình minh họa các trường hợp khi thêm tai thứ k. • Điều kiện đủ: Giả sử G có cây các khối là một đường P , khi đó các đỉnh cắt của G đều thuộc P , đánh số thứ tự cho các đỉnh cắt này từ một đầu mút của P cho đến hết là x1, x2, . . . , xk. Gọi đường xixi+1 là đường ngắn nhất nối từ xi đến xi+1 trong G. Đặt Po là hợp của các đường xixi+1. Ta sẽ xây dựng một phân tích tai của G bắt đầu từ Po. Giả sử B là một khối của G. Nếu B khác khối lá và xi, xi+1 thuộc B thì do B là 2 - liên thông nên B có một phân tích tai mở bắt đầu từ đường xixi+1. Nếu B là một đỉnh x của G thì x là hàng xóm của x1 hoặc xk. Khi đó ta thêm cạnh x1x hoặc xkx vào Po. NếuB là khối lá vàB có nhiều hơn một đỉnh thì x1 hoặc xk là đỉnh cắt chứa trong B. Không mất tính tổng quát ta giả sử là x1, gọi 31 x1u là một cạnh thuộc B. Do B là 2 - liên thông nên có một phân tích tai mở bắt đầu từ x1u và ta thêm cạnh x1u vào Po. Đánh số lại các tai trong từng phân tích tai ta được một phân tích tai của G với tai đầu tiên là Po. Ta rút ra kết luận sau về điều kiện để có phân tích tai 1. Ta thấy rằng, nếu một đồ thị có 3 đỉnh bậc 1 thì đồ thị đó không thể có phân tích tai. 2. Khi đồ thị không có đỉnh bậc 1, G có phân tích tai mở khi G là 2 - liên thông. G có phân tích tai nếu G là 2 - cạnh liên thông. 3. Nếu đồ thị có 1 hoặc 2 đỉnh bậc 1 thì đồ thị chỉ có thể có phân tích tai loại 2 (do nó không là 2 - liên thông). Đồ thị G có phân tích tai (phân tích tai mở) nếu G liên thông và cây các đồ thị con 2 - cạnh liên thông cực đại (các khối) của G là một đường với đầu mút là đỉnh bậc 1. Như vậy, trong chương này ta đã tìm hiểu về tính liên thông của đồ thị và mối quan hệ của nó với phân tích tai. Phân tích tai của đồ thị là một vấn đề kinh điển, đã được phát triển sâu rộng và được sử dụng như một công cụ mạnh để phân loại và nghiên cứu các tính chất của đồ thị. Đã có thuật toán tìm phân tích tai của đồ thị trong thời gian logarit như thuật toán của Maon et al. (1986) [7] . CHƯƠNG 2 NHẬN DẠNG ĐỒ THỊ SERIES PARALLEL DỰA TRÊN PHÂN TÍCH TAI Trong chương này chúng tôi sẽ trình bày thuật toán nhận dạng đồ thị Series Parallel. Thuật toán dựa trên định nghĩa phân tích tai mở của đồ thị. Cụ thể chúng tôi sẽ chỉ ra rằng đồ thị Series Parallel có thể được đặc trưng bởi tính gắn kết của phân tích tai. Để kiểm tra một đồ thị có là Series Parallel không chúng tôi lần lượt làm các công việc sau: đầu tiên, kiểm tra đồ thị có phân tích tai không; tiếp theo, kiểm tra tính gắn kết của một phân tích tai đó, nếu đồ thị là Series Parallel thì phân tích tai phải gắn kết; và cuối cùng là đưa ra cây phân tích các phép toán Series và Parallel của đồ thị đó nếu nó là Series Parallel. Nội dung trong chương 2 bao gồm các phần sau: 2.1. Phân tích tai gắn kết: mục này trình bày về phân tích tai gắn kết, một trường hợp của đặc biệt của phân tích tai loại 2 có mối quan hệ chặt chẽ với đồ thị Series Parallel. 2.2. Đồ thị là Series Parallel và phân tích tai: phần này trình bày định nghĩa đồ thị Series Parallel, điều kiện cần và đủ để một đồ thị là Series Parallel và cách chọn đỉnh đầu cuối nếu đồ thị đầu vào chưa nói rõ đỉnh đầu cuối. 32 33 2.3 Thuật toán nhận dạng đồ thị Series Parallel: phần này chúng tôi sẽ kết hợp các kết quả đã có để hình thành thuật toán, trình bày chi tiết cách kiểm tra tính gắn kết của phân tích tai (bước quan trọng của thuật toán), tính toán độ phức tạp và đưa ra những ví dụ minh họa. Các phân tích tai được nói đến trong chương này nếu không nói gì thêm đều là phân tích tai loại 2 . Các kiến thức trong chương này được tham khảo chủ yếu từ [4]. 2.1 Phân tích tai gắn kết Đầu tiên chúng tôi sẽ lần lượt giới thiệu các trường hợp phân tích tai. Định nghĩa 2.1.1. [4]Cho đồ thịG và một phân tích tai mở ED= {E1,E2, ...,Ek} của G. Ta định nghĩa hàm eED tác động lên đỉnh v như sau: • eED(v) = Ei nếu v là đỉnh trong của Ei. • eED(v) = E1 nếu v là đầu mút của E1. Định nghĩa 2.1.2. [4] Tai Ei được gọi là gắn (nested) trên tai Ej nếu j < i và hai đầu mút của Ei nằm trên Ej . Khoảng gắn (nest interval) của tai Ei trên tai Ej là đường trên Ej nối hai đầu mút của Ei. Định nghĩa 2.1.3. [4] Phân tích tai ED = {E1,E2, . . . ,Ek} là phân tích tai dạng cây (tree ear decompotition) nếu nó thỏa mãn với mỗi i > 1,∃j < i sao cho Ei gắn trên Ej . Định nghĩa 2.1.4. [4] Phân tích tai gắn kết (nested ear decomposition) là phân tích tai dạng cây thỏa mãn nếu hai tai Ei, Ei′ cùng gắn trên cùng một tai Ej thì khoảng gắn của Ei chứa khoảng gắn của Ei′ hoặc ngược lại, hoặc hai khoảng 34 gắn phải rời nhau (không có 2 khoảng gắn nào trên cùng một tai Ej mà cắt nhau). Hình 2.1: Phân tích tai gắn kết và phân tích tai dạng cây Bổ đề 2.1.1. [4] Nếu đồ thịG có một phân tích tai ED là gắn kết thì các khoảng gắn trên một tai Ei bất kì sẽ tạo thành một cây. Trong đó khoảng gắn I là con của khoảng gắn J nếu I là một đường con cực đại của J , I là anh em kế của J nếu chúng có cùng bố và không có điểm trong chung giữa chúng. Chứng minh. Đặt Ei là đỉnh gốc, mỗi khoảng gắn trên Ei là một đỉnh của cây, hai đỉnh được nối với nhau nếu chúng có quan hệ bố con. Ta có ED là phân tích tai gắn kết nên nếu có hai khoảng gắn I, J trên tai Ei thì chúng chỉ có quan hệ hoặc là bố con hoặc là anh em kế. Nếu J và I rời nhau thì chúng được nối với gốc Ei còn nếu chúng chứa nhau mà khoảng gắn này là đường con cực đại của khoảng gắn kia thì chúng được nối với nhau theo quan hệ bố con. Do đó mỗi khoảng gắn trong Ei đều có một bố duy nhất vậy nên các khoảng gắn trên Ei sẽ hình thành một cây (hình 2.2). Ví dụ 2.1.1. Trong hình 2.1, ta có đồ thị G có một phân tích tai gắn kết là E = E1∪E2∪E3∪E4∪E5∪E6. Trong đó E2, E3, E5, E6 gắn trên E1 và E4 gắn trên E2. Ta có ab, ac, ch, cg lần lượt là các khoảng gắn của tai E3, E2, E5 và E6 trên tai E1 còn de là khoảng gắn của tai E4 trên tai E2. 35 Đồ thị H có phân tích tai dạng cây nhưng không phải là phân tích tai gắn kết vì E3 và E2 cùng gắn trên E1 nhưng hai khoảng gắn của chúng cắt nhau. Theo bổ đề 2.1.1, ta có thể hình thành cây của các khoảng gắn trên tai E1 như trong hình 2.2. Hình 2.2: Cây của các khoảng gắn trên tai E1 Từ bổ đề 2.1.1 chúng tôi đưa ra định nghĩa cây của một phân tích tai dạng cây. Định nghĩa 2.1.5. Cho đồ thị G có phân tích tai dạng cây. Cây của G được định nghĩa như sau: 1 . E1 là đỉnh gốc. 2 . Mỗi tai được coi là một đỉnh của cây. 3 . Ei là con của Ej nếu Ei gắn trên Ej . Ví dụ 2.1.2. Phân tích tai trong hình hình 2.3i có thể có hai cây còn phân tích tai trong hình 2.3ii có một cây duy nhất. Từ ví dụ trên ta thấy rằng một phân tích tai dạng cây có thể có nhiều hơn một cây. Vậy câu hỏi đặt ra là khi nào thì một phân tích tai dạng cây có một cây duy nhất? Để trả lời câu hỏi đó ta đi đến mệnh đề sau. Mệnh đề 2.1.1. Cho đồ thịG có một phân tích tai dạng cây ED= {E1,E2, . . . ,Ek}, cây của G là duy nhất khi và chỉ khi nếu Ei và Ei′ cùng gắn trên Ej thì khoảng gắn của chúng phải phân biệt. 36 Hình 2.3: Phân tích tai dạng cây và cây. Chứng minh. Điều kiện cần. Giả sử cây của G là duy nhất, Ei và Ei′ cùng gắn trên Ej và khoảng gắn của chúng trùng nhau. Khi đó ta sẽ có 2 cách biểu diễn cây như trong hình 2.3i (mâu thuẫn với tính duy nhất) nên khoảng gắn của Ei và Ei′ phải phân biệt. Điều kiện đủ Giả sử Ei và Ei′ cùng gắn trên Ej và khoảng gắn của chúng phân biệt. Vì phân tích tai là dạng cây nên Ei và Ei′ chỉ gắn trên Ej . Do đó mỗi tai trong G chỉ có duy nhất một bố nên cây của G là duy nhất. Bổ đề 2.1.2. [4] Nếu đồ thị G có một phân tích tai ED = {E1,E2, . . . ,Ek} là gắn kết thì với mỗi tai Ei, i > 1 có hai đầu mút là x, y, Ei sẽ gắn trên tai có chỉ số lớn hơn trong hai tai eED(x), eED(y). Chứng minh. Ta chứng minh bằng quy nạp theo i. Với i = 2, ED chỉ có 2 tai là E1 và E2 với E2 gắn trên E1, do đó bổ đề hiển nhiên đúng. Giả sử bổ đề đúng với mọi i′ < i. Theo định nghĩa của phân tích tai gắn kết ∃j < i sao cho Ei gắn trên Ej nên x, y đều phải thuộc Ej . Nếu eED(x) = eED(y) = Ej thì suy ra bổ đề đúng. Nếu một trong hai đỉnh x hoặc y là đầu mút của Ej , giả sử eED(x) = Ej và y là đầu mút của Ej thì ta có 37 eED(y) = Ej′ với j′ ≤ j. Suy ra Ei gắn trên tai Ej là tai có chỉ số lớn hơn trong hai tai eED(x), eED(y). Nếu x, y đều là đầu mút của của Ej thì theo giả thiết quy nạp Ej gắn trên tai có chỉ số lớn hơn trong hai tai eED(x), eED(y) nên Ei cũng gắn trên tai có chỉ số lớn hơn trong hai tai eED(x), eED(y). Vậy bổ đề đúng với i. Tiếp theo ta sẽ mở rộng hàm eED từ đỉnh đến tai. Định nghĩa 2.1.6. [4] Cho đồ thị G có phân tích tai dạng cây ED = {E1,E2, . . . ,Ek}: 1. NếuEi có hai đầu mút x, y, ta định nghĩa eED(Ei) là tai có chỉ số lớn hơn trong hai tai eED(x) và eED(y). 2. Ei là gắn thực sự trên Ej nếu eED(Ei) = Ej . 3. Ei được chứa trongEj nếu có một dãy các taiEi, Ek, . . . , Ej sao cho mỗi tai đều gắn thực sự trên tai tiếp sau nó. Định nghĩa gắn thực sự cũng được áp dụng cho một phân tích tai bất kì. Ví dụ 2.1.3. Trong đồ thị G (hình 2.1) ta có eED(E1) = E1, eED(E2) = E1, eED(E3) = E1, eED(E4) = E2 nên E2, E3 gắn thực sự trên tai E1 và E4 gắn thực sự trên tai E2. E4 chứa trong E1 do ta có dãy các tai E4, E2, E1 thỏa mãn điều kiện mỗi tai đều gắn thực sự trên tai tiếp sau nó. Hình 2.4 cho ta một ví dụ về tính gắn nhưng không gắn thực sự. Ta cóEi gắn trên Ej nhưng không gắn thực sự trên Ej mà Ej và Ei cùng gắn thực sự trên Ei′. Ta cũng thấy rằng nếu một phân tích tai không phải dạng cây thì một tai gắn thực sự trên tai này chưa chắc đã gắn trên tai đó. Như phân tích tai mở của đồ thị H trong hình 1.14, tai P4 gắn thực sự trên tai P3 nhưng không gắn trên tai đó. 38 Hình 2.4: Tai Ej gắn trên Ei nhưng không gắn thực sự. Bổ đề sau sẽ chứng minh rằng chỉ cần kiểm tra các tai gắn thực sự trong việc kiểm tra một phân tích tai có là gắn kết hay không. Bổ đề 2.1.3. [4] Cho đồ thị G có một phân tích tai mở ED = {E1,E2, ...,Ek} sao cho: 1. ED bắt đầu từ một cạnh đơn. 2. Với mỗi i > 1,∃j < i sao cho Ei là gắn trên Ej . 3. Nếu hai tai Ei và Ei′ cùng gắn thực sự trên cùng một tai Ej thì khoảng gắn của Ei chứa Ei′ hoặc ngược lại, hoặc hai khoảng gắn rời nhau. Khi đó ED là gắn kết. Chứng minh. Ta có ED thỏa mãn điều kiện 1 và 2 nên nó là một phân tích tai dạng cây. Nếu Ei là gắn trên tai Ej nhưng không là gắn thực sự thì khoảng gắn của Ei là toàn bộ Ej , do đó không thể cắt bất cứ khoảng gắn nào khác của Ej . Do đó ED là phân tích tai gắn kết. Ta thấy rằng bất cứ phân tích tai gắn kết nào cũng thỏa mãn điều kiện 2 và 3. Do đó, để kiểm tra tính gắn kết của một phân tích tai bắt đầu từ một cạnh đơn ta có thể làm hai bước như sau: • Kiểm tra điều kiện 2: mỗi tai đều gắn trên một tai khác nào đó. 39 • Kiểm tra điều kiện 3: trên mỗi tai ta xét tập các tai gắn thực sự trên tai đó rồi kiểm xem có hai tai nào cắt nhau không (tức là khoảng gắn của chúng không chứa nhau mà lại có điểm trong chung), nếu không có thì phân tích tai đó là gắn kết. Bổ đề 2.1.4. Cho ED là một phân tích tai gắn kết của đồ thịG và cho Ei là một tai với đầu mút là x, y. Khi đó x, y phân tách đồ thị con sinh bởi các tai chứa trong Ei với phần còn lại của đồ thị. Chứng minh. Gọi S là đồ thị con sinh bởi các tai chứa trongEi. Để chứng minh bổ đề đúng, ta sẽ chứng minh rằng với mỗi tai nằm trong S thì bất cứ tai nào gắn trên nó đều thuộc S hoặc chỉ có duy nhất hai đỉnh chung với G− S là x, y. Lấy Ej ∈ S, Ek là tai gắn trên trên Ej . Nếu Ek gắn thực sự trên Ej thì nó chứa trong Ei, do đó Ek ∈ S. Ngược lại Ek không gắn thực sự trên Ej thì hai đầu mút của Ek trùng với hai đầu mút của Ej . Nếu j 6= i thì Ek sẽ chứa trong Ei do nó gắn thực sự trên cùng một tai với Ej . Nếu j = i thì Ek thuộc phần còn lại của đồ thị và chỉ có hai điểm chung duy nhất là x và y với Ei. Như vậy, phân tích tai gắn kết là một phân tích tai mà mỗi tai của nó chỉ được gắn thực sự trên một tai duy nhất và các tai gắn thực sự trên cùng một tai thì không được cắt nhau. Ta thấy rằng nếu cho một đồ thị G có một phân tích tai ED gắn kết với k tai và tai đầu tiên là một cạnh đơn, nếu ta cố định một xích là Eo thì G có một phân tích tai gắn kết duy nhất và G có đúng k kiểu phân tích tai gắn kết. Việc kiểm tra khi nào một phân tích tai là gắn kết sẽ được trình bày trong mục 2.3.2. 40 2.2 Đồ thị Series - Parallel và phân tích tai 2.2.1 Định nghĩa đồ thị Series - Parallel Trong mục này chúng tôi trình bày về khái niệm đồ thị TTSP (Two Terminal Series Parallel) và cách biểu diễn đồ thị TTSP bằng cây nhị phân mà chúng tôi gọi là cây sp . Định nghĩa 2.2.1. (Đồ thị Series - Parallel hai đầu) i. Một đồ thị hai đầu (Two-Terminal Graph) là đồ thị có hai điểm phân biệt s và t được gọi là điểm nguồn và điểm hút (ta gọi s và t là hai đỉnh đầu cuối). ii. Đồ thị chỉ gồm hai đỉnh và một cạnh đơn nối hai đỉnh đó (đồ thị K2) là TTSP với hai đỉnh đầu cuối là hai đỉnh đã cho. iii. Cho 2 TTSP X và Y với các đỉnh đầu cuối lần lượt là sX , tX , sY , tY , ta xây dựng đồ thị G bằng cách: (a) Tổng hợp song song (parallel composition): ta đồng nhất s = sX = sY , t = tX = tY và giữ nguyên tập cạnh của X , Y . Khi đó ta viết G = P (X, Y ). (b) Tổng hợp chuỗi (series composition): ta đồng nhất s = sX , t = tY , tX = sY và giữ nguyên tập cạnh của X , Y . Khi đó ta viết G = S(X, Y ). iv. Một đồ thị là TTSP nếu nó được xây dựng bởi một dãy các phép toán tổng hợp chuỗi và song song bắt đầu từ một tập các đồ thịK2 với đỉnh đầu cuối được gán. v. Một đồ thị là Series Parallel nếu tồn tại một cặp đỉnh s, t để đồ thị đó là TTSP với (s, t) là hai đỉnh đầu cuối. 41 Một đồ thị Series Parallel có thể được biểu diễn một cách tự nhiên bằng cây nhị phân với các nút S (tương ứng với phép tổng hợp chuỗi), P (tương ứng với phép tổng hợp song song) và các lá tương ứng với các cạnh trong đồ thị. Ví dụ 2.2.1. Hình 2.5 chỉ ra cấu trúc của một đồ thị Series Parallel được xây dựng từ một chuỗi các phép tổng hợp chuỗi và tổng hợp song song. Hình 2.6 là cây sp thể hiện cấu trúc của đồ thị TTSP trong hình 2.5. Hình 2.5: Cấu trúc của một đồ thị TTSP bằng các phép tổng hợp chuỗi và song song 2.2.2 Điều kiện để một đồ thị là Series - Parallel Đầu tiên, chúng tôi sẽ trình bày điều kiện cần và đủ để một đồ thị là TTSP. 42 Hình 2.6: Cây nhị phân thể hiện cấu trúc của đồ thị TTSP trong hình 2.5. Bổ đề 2.2.1. [5] Nếu đồ thị vô hướng G có một phân tích tai gắn kết bắt đầu từ một đường nối từ s đến t thì G là TTSP với đỉnh đầu cuối là s, t. Chứng minh. Nếu G chỉ có một cạnh đơn thì G là TTSP. Nếu |E(G)| ≥ 2 ta chứng minh bổ đề trên bằng quy nạp theo E(G). Trường hợp 1: Tồn tại một số Ej, j > 1 có chung hai đầu mút s, t với E1. Đặt Y là đồ thị con sinh bởi Ej và những tai chứa trong nó. X là đồ thị con sinh bởi các cạnh còn lại (hình 2.7i). Theo bổ đề 2.1.4, ta có X, Y được kết nối với nhau qua s và t. Khi đó các tai trong Y có dạng một phân tích tai gắn kết bắt đầu từ Ej , các tai trong X có dạng một phân tích tai gắn kết bắt đầu từ E1. Theo quy nạp X, Y là các đồ thị TTSP với đỉnh đầu cuối là s và t. Do đó G = P (X, Y ) là TTSP với đỉnh đầu cuối là s và t. Trường hợp 2: Không có tai nào có chung hai đầu mút s và t với E1. Gọi Ej là một tai gắn thực sự trên E1 sao cho khoảng gắn của Ej không nằm trong bất cứ khoảng gắn nào khác. Khi đó Ej có một đầu mút là x khác s và t. Gọi X là đồ thị con của G bao gồm đường con từ s đến x trong E1 và tất cả các tai chứa trong đường con đó và Y là đồ thị con của G bao gồm đường con từ x đến t trong E1 và tất cả các tai chứa trong đường con đó (hình 2.7ii). Do tính gắn kết 43 của phân tích tai và khoảng gắn của Ej không chứa trong một khoảng gắn nào khác nên không có tai nào gắn trên E1 mà cắt tai Ej và mọi tai gắn trên E1 phải nằm trong X hoặc Y . Mỗi tai Ei, i 6= 1 của G thì Ei ⊂ X hoặc Y , không có tai nào nốiX với Y . Suy raX có một phân tích tai gắn kết bắt đầu từ đường nối s tới x, Y có một phân tích tai gắn kết bắt đầu từ đường nối x đến t. Theo quy nạpX và Y là các đồ thị TTSP với các điểm đầu cuối lần lượt là s, x và x, t do đó G = S(X, Y ) là TTSP với đỉnh đầu cuối là s, t. Hình 2.7: Hình minh họa trường hợp 1 và 2. Bổ đề 2.2.2. [5] Nếu ED = {E1, E2, ..., Ek} là một phân tích tai mở của đồ thị TTSP G với đỉnh đầu cuối là s, t và E1 là một đường từ s đến t thì ED là gắn kết. Chứng minh. Ta sẽ chứng minh bổ đề trên bằng quy nạp theo số cạnh của G. Nếu G chỉ có một cạnh đơn st thì hiển nhiên ED là gắn kết. Trường hợp 1: Nếu G = P (X, Y ), X và Y chỉ liên kết với nhau qua s và t thìE1 phải nằm trọn vẹn trongX hoặc Y , hơn nữa mỗi tai kế tiếp cũng chỉ được thuộc X hoặc Y (nếu không s hoặc t sẽ là đỉnh trong của tai đó, mâu thuẫn). Không mất tính tổng quát ta giả sử E1 ⊂ X . Khi đó những tai trongX có dạng một phân tích tai mở, theo qui nạp phân tích đó là gắn kết. Gọi Ej là tai đầu tiên 44 trong Y với j là chỉ số nhỏ nhất. Khi đó s và t phải là hai đầu mút của Ej do s và t là những hai đỉnh duy nhất của Y xuất hiện trên những tai trước đó. Khi đó những tai trong Y có dạng một phân tích tai mở bắt đầu từ Ej , nên theo qui nạp phân tích tai đó là gắn kết. Kiểm tra tính gắn kết: 1. Lấy Ei ∈ G, i 6= 1 suy ra Ei ∈ X hoặc Ei ∈ Y . Do cảX, Y đều có phân tích tai là gắn kết nên Ei phải g