Bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ

- BÀI TOÁN LIÊN THÔNG P-MEDIAN TRÊN ĐỒ THỊ ĐẦY ĐỦ VÀ ĐỒ THỊ LƯỠNG PHÂN ĐẦY ĐỦ.
- Bài toán p-median, đồ thị đầy đủ, đồ thị lưỡng phân đầy đủ, thuật toán thời gian tuyến tính.
- Trong bài báo này, một bài toán vị trí liên quan đến các thành phần liên thông trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ được đề cập..
- Để giải quyết bài toán này, một số định lí và bổ đề được đưa ra trong quá trình nghiên cứu.
- Bên cạnh đó, các thuật toán thời gian tuyến tính được đưa ra để giải bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ..
- Bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ.
- Bài toán vị trí khởi nguồn từ bài toán nổi tiếng được đưa ra bởi nhà toán học Fermat vào khoảng thế kỷ XVII, đó là tìm vị trí của một điểm mới trên mặt phẳng sao cho khoảng cách từ nó đến ba điểm cho trước là nhỏ nhất.
- Bài toán đó sau này đã được giải bởi Torricelli (Krarup and Vajda, 1997).
- Từ bài toán này, trường hợp đối với một tập gồm điểm đã được đưa ra và điểm làm tối thiểu hàm khoảng cách đến tất cả các điểm còn lại được gọi là điểm median trên mặt phẳng, và hàm cần làm tối thiểu gọi là hàm median (Kariv and Hakimi, 1979)..
- Bài toán vị trí nói trên đã được áp dụng vào các loại đồ thị đặc biệt như đồ thị cây, đồ thị có dạng mạng lưới,… tuy nhiên vì một lí do đặc biệt nào đó mà người ta cần tìm nhiều hơn một cơ sở mới trên mạng lưới đồ thị sao cho hàm khoảng cách từ các điểm có sẵn trên mặt phẳng đến tập hợp các điểm đó là nhỏ nhất, mặt khác các điểm này được đòi hỏi phải là các điểm liên thông, từ đây một lớp các bài toán đã được đưa ra nghiên cứu..
- (2015) về bài toán liên thông p-median trên đồ thị khối, các tác giả chứng minh rằng bài toán liên thông p-median trên đồ thị khối với độ dài tổng quát là NP-khó.
- trường hợp đặc biệt, khi đồ thị khối có độ dài các cạnh bằng nhau thì tác giả cũng chỉ ra rằng bài toán liên thông p-median có thể giải trong thời gian tuyến tính..
- trong đó n là số đỉnh của đồ thị khối..
- Trong bài báo này, tiếp nối những kết quả của các tác giả trên, bài báo này đặt ra một vấn đề về bài toán vị trí liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ..
- Theo Bondy and Murty (1976), đồ thị G được định nghĩa là một bộ phận hợp thành bởi ba thành phần V G E G.
- Nếu ta gọi e là một cạnh của đồ thị G và u v , là hai đỉnh sao cho.
- Một đồ thị được gọi là đồ thị đơn nếu nó không có cạnh nào có điểm đầu và điểm cuối trùng nhau và không có hai cạnh nào nối cùng một cặp đỉnh..
- Hai đỉnh của một đồ thị được gọi là kề nhau nếu tồn tại một cạnh nối hai điểm đó.
- Một đồ thị được gọi là đồ thị đầy đủ (Hình 1) nếu nó là đồ thị đơn và hai đỉnh bất kỳ của đồ thị luôn kề nhau..
- Hình 1: Đồ thị đầy đủ.
- Đồ thị lưỡng phân là một đồ thị mà trong đó tập hợp các đỉnh của nó có thể được chia thành hai tập con rời nhau sao cho hai đỉnh thuộc cùng một tập con thì không kề nhau.
- Đồ thị lưỡng phân đầy đủ (Hình 2) là một đồ thị lưỡng phân mà trong đó bất kì một đỉnh nào từ tập con này, đều kề với tất cả các đỉnh thuộc tập con kia..
- Hình 2: Đồ thị lưỡng phân đầy đủ Đường đi độ dài n từ đỉnh u đến đỉnh v là dãy.
- Trong bài báo này, ta chỉ đề cập đến các đồ thị đơn mà các cạnh của nó có độ dài đơn vị, nghĩa là.
- Một tập hợp con S của V G.
- là liên thông nếu luôn có một đường đi nối hai đỉnh bất kỳ trong S.
- Bài báo này đề cập đến một bài toán là tìm một tập hợp liên thông S p gồm p đỉnh ( p  n với n là số đỉnh của đồ thị đầy đủ G.
- 3 BÀI TOÁN LIÊN THÔNG P-MEDIAN TRÊN ĐỒ THỊ ĐẦY ĐỦ.
- Bây giờ ta xét bài toán liên thông p-median trên đồ thị đầy đủ với trường hợp p = 1 .
- bài toán 1-median cổ điển trên đồ thị đầy đủ với hàm mục tiêu là:.
- Do ta đang xét đồ thị đầy đủ với độ dài đơn vị nên khoảng cách giữa hai đỉnh phân biệt bất kỳ thuộc đồ thị đều bằng 1.
- u với u là đỉnh có trọng số lớn nhất trên đồ thị G sẽ làm cho hàm mục tiêu đạt giá trị nhỏ nhất, nghĩa là tập hợp liên thông p  arg max {w.
- trả về đỉnh có trọng số lớn nhất..
- Đối với trường hợp p  2 , bài toán tương ứng là bài toán tìm tập hợp gồm p đỉnh liên thông S p.
- Giả sử ta có S p là tập hợp gồm p điểm lấy từ.
- v n thì khi đó p-median liên thông của G là S p.
- Với mọi tập hợp S  V G.
- Theo kết quả có được ở Bổ đề 3.1, ta chứng minh được tập liên thông p-median của G là tập hợp p đỉnh có trọng số lớn nhất thuộc V G.
- Từ đây, ta xây dựng thuật toán tổ hợp để tìm tập hợp liên thông p-median S p trên đồ thị đầy đủ G cho trước.
- Hơn nữa, thuật toán tìm trung vị của một dãy có độ phức tạp bằng độ dài của dãy đó (Hoare, 1961).
- Giả sử độ phức tạp của bài toán là T(n) với n là số đỉnh của G, khi đó,.
- với k là số bước lặp của thuật toán thỏa 2 k  n và kí hiệu.
- Nói một cách khác, thuật toán chạy trong thời gian tuyến tính..
- Sau đây, chúng ta xem xét một thuật toán thời gian tuyến tính để tìm tập hợp.
- gồm p số lớn nhất trong một tập hợp B gồm n số.
- Thuật toán 3.2: Tìm p số lớn nhất trong một tập hợp B gồm n phần tử là số thực ( p  n.
- Input: Một tập hợp B gồm n phần tử là số..
- Output: Tập hợp  p gồm p số lớn nhất lấy từ B.
- Ví dụ 3.3: Tìm tập hợp  p gồm 5 số lớn nhất lấy từ tập hợp B.
- Áp dụng Thuật toán 3.2, ta có kết quả như sau:.
- p | 5 p nên Thuật toán 3.2 dừng..
- Vậy ta thu được tập hợp  p cần tìm là.
- Sau đây, bằng cách áp dụng Thuật toán 3.2, chúng tôi đề xuất một thuật toán để giải bài toán liên thông p-median trên đồ thị đầy đủ..
- Thuật toán 3.4: Giải bài toán liên thông p- median trên đồ thị đầy đủ..
- Input: Đồ thị đầy đủ G với n đỉnh.
- Áp dụng Thuật toán 3.2 để tìm tập hợp  p gồm p số lớn nhất lấy từ tập hợp B.
- Output: Tập S p gồm p đỉnh liên thông tương ứng với tập  p.
- Ví dụ 3.5: Cho đồ thị đầy đủ như Hình 3, với trọng số cho bởi Bảng 3.
- Ta giải bài toán với p = 4..
- Bảng 3: Trọng số các đỉnh.
- Hình 3: Đồ thị đầy đủ K 5.
- Áp dụng Thuật toán 3.2, ta được:.
- Định lý 3.6: Bài toán liên thông p-median trên đồ thị đầy đủ có thể giải trong thời gian tuyến tính..
- 4 BÀI TOÁN LIÊN THÔNG P-MEDIAN TRÊN ĐỒ THỊ LƯỠNG PHÂN ĐẦY ĐỦ.
- Bây giờ, ta xét bài toán liên thông p-median trên đồ thị lưỡng phân đầy đủ..
- Bài toán của chúng ta trong trường hợp này có thể được phát biểu như sau: Tìm tập hợp liên thông p-median trên đồ thị lưỡng phân đầy đủ K sao cho hàm median sau đây đạt giá trị nhỏ nhất:.
- Đối với trường hợp p = 1 , bài toán trên cũng là bài toán 1-median cổ điển trên đồ thị lưỡng phân đầy đủ, đó là tìm một đỉnh trên đồ thị này sao cho tổng khoảng cách từ các đỉnh còn lại thuộc đồ thị đến nó là nhỏ nhất..
- Theo định nghĩa của đồ thị lưỡng phân đầy đủ, ta có thể chia tập hợp đỉnh của K thành hai tập rời nhau V 1 và V 2 sao cho hai đỉnh thuộc cùng một tập thì không kề nhau..
- Bây giờ ta xét trường hợp p = 2 , khi đó bài toán của chúng ta là tìm tập hợp liên thông 2-median trên đồ thị lưỡng phân đầy đủ K sao cho hàm median.
- Vì S 2 liên thông nên S 2 gồm hai đỉnh, trong đó có một đỉnh thuộc V 1 và một đỉnh thuộc V 2.
- 1 do S p là tập hợp liên thông, do đó hàm median của chúng ta là hàm:.
- Mệnh đề 4.7: Tập liên thông 2-median S 2 của K thỏa F S ( 2.
- và S 2 ' là tập liên thông thì khi đó.
- Như vậy với p = 2 thì tập liên thông p-median S p là tập gồm 2 điểm là trọng số lớn nhất lần lượt nằm trong hai thành phần phân chia V 1 và V 2.
- Bằng phép chứng minh tương tự như Mệnh đề 4.7, ta chứng minh được với p  2 , tập liên thông S p là tập liên thông 2-median hợp với tập hợp gồm.
- p − đỉnh nữa là các đỉnh có trọng số lớn nhất trên đồ thị lưỡng phân đầy đủ K sau khi đã bỏ đi các đỉnh thuộc tập 2-median.
- Theo như Mệnh đề 4.7, ta có tập liên thông S p.
- với p = 2 chứa hai đỉnh có trọng số lớn nhất lần lượt nằm trên hai thành phần phân chia của đồ thị K .
- Với p  2 , ta xét tập liên thông S p gồm hai.
- và p − 2 đỉnh có trọng số lớn nhất trên đồ thị K , khi đó.
- S liên thông và | S.
- với mọi tập liên thông.
- Từ đây ta sẽ đi xây dựng thuật toán thời gian tuyến tính để giải bài toán liên thông p-median trên đồ thị lưỡng phân đầy đủ K .
- Ý tưởng của thuật toán này là sử dụng Thuật toán 3.2 để tìm ra đỉnh có trọng số lớn nhất lần lượt nằm trên hai thành phần phân chia, và sau đó, ta thêm các đỉnh có trọng số lớn hơn median của các đỉnh còn lại để thêm vào tập.
- Thuật toán 4.8: Giải bài toán liên thông p- median trên đồ thị lưỡng phân đầy đủ K.
- Input: Đồ thị lưỡng phân đầy đủ K với.
- V 1 ,1 là tập hợp chứa 1 đỉnh có trọng số lớn nhất trong V 1.
- Áp dụng Thuật toán 3.2 để tìm  1.
- 1 ' max ( V 2 ,1 ) là tập hợp chứa 1 đỉnh có trọng số lớn nhất trong V 2.
- Áp dụng Thuật toán 3.2 để tìm tập hợp.
- Output: Tập S p gồm p đỉnh liên thông tương ứng với tập.
- Ví dụ 4.9: Cho đồ thị lưỡng phân đầy đủ như trong Hình 4 và trọng số cho bởi Bảng 4.
- Ta giải bài toán với p = 5..
- Bảng 4: Trọng số các đỉnh.
- Hình 4: Đồ thị lưỡng phân đầy đủ Đồ thị lưỡng phân đầy đủ đã cho có.
- V 1 ,1 , áp dụng Thuật toán 3.2 với B.
- áp dụng Thuật toán 3.2 với B.
- Tiếp tục áp dụng Thuật toán 3.2 với tập hợp B để tìm tập hợp  p− 2 gồm p − 2 đỉnh có trọng số lớn nhất trong B , ta có được  p− 2.
- Định lí 4.10: Bài toán liên thông p-median trên đồ thị lưỡng phân đầy đủ có thể giải trong thời gian tuyến tính..
- Trong bài báo này, các thuật toán thời gian tuyến tính đã được đưa ra để giải bài toán liên thông p- median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy.
- Trong các bài báo kế tiếp chúng ta có thể nghiên cứu tìm một thuật toán thời gian tuyến tính để giải bài toán liên thông trên các dạng đồ thị khác, tiêu biểu là đồ thị có nhiều hơn hai thành phần phân chia, đồ thị đa lớp, các loại đồ thị có trọng số dương/âm