Nghiên cứu tập trung vào một lớp bài toán vị trí tối ưu thuộc lĩnh vực tối ưu tổ hợp và lý thuyết đồ thị, cụ thể là 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 là một trong những mô hình nền tảng trong quy hoạch vị trí cơ sở, với mục tiêu lựa chọn p đỉnh (hay p cơ sở) sao cho tổng khoảng cách từ các đỉnh còn lại đến các đỉnh được chọn là nhỏ nhất. Mô hình này có ý nghĩa ứng dụng rộng rãi trong nhiều lĩnh vực thực tiễn như quy hoạch trung tâm phân phối, bố trí bệnh viện, trạm cứu hộ, mạng lưới giao thông, viễn thông và logistics. Tuy nhiên, trong nhiều bối cảnh thực tế, ngoài yêu cầu tối ưu chi phí khoảng cách, các đỉnh được lựa chọn còn cần thỏa mãn tính liên thông nhằm đảm bảo khả năng phối hợp, vận hành hoặc kết nối nội bộ hiệu quả. Chính vì vậy, bài toán liên thông p-median trở nên phức tạp hơn so với p-median cổ điển.

Trong bài báo này, tác giả xem xét bài toán trên hai cấu trúc đồ thị đặc biệt là đồ thị đầy đủ (complete graph) và đồ thị lưỡng phân đầy đủ (complete bipartite graph). Đây là hai lớp đồ thị có cấu trúc mạnh, cho phép khai thác các tính chất toán học đặc thù để đơn giản hóa quá trình phân tích và thiết kế thuật toán. Đồ thị đầy đủ là dạng đồ thị mà mọi cặp đỉnh đều có cạnh nối trực tiếp, trong khi đồ thị lưỡng phân đầy đủ chia tập đỉnh thành hai nhóm sao cho mọi đỉnh thuộc nhóm này đều nối với mọi đỉnh thuộc nhóm kia. Việc nghiên cứu bài toán p-median trên các cấu trúc này không chỉ có giá trị lý thuyết mà còn đóng vai trò nền tảng cho các mở rộng sang các lớp đồ thị phức tạp hơn.

Để giải quyết bài toán, nghiên cứu đã xây dựng và chứng minh một số định lý và bổ đề quan trọng, đóng vai trò làm cơ sở lý thuyết cho việc đặc trưng hóa nghiệm tối ưu. Các kết quả này giúp xác định các tính chất cấu trúc của tập đỉnh p-median liên thông tối ưu, từ đó loại bỏ nhiều khả năng tìm kiếm không cần thiết và giảm đáng kể độ phức tạp tính toán. Việc sử dụng các công cụ toán học như định lý và bổ đề không chỉ củng cố tính đúng đắn của thuật toán mà còn giúp làm rõ bản chất của bài toán dưới góc độ lý thuyết đồ thị và tối ưu hóa.

Một đóng góp nổi bật của nghiên cứu là việc đề xuất các thuật toán thời gian tuyến tính (linear-time algorithms) cho bài toán liên thông p-median trên cả đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ. Thuật toán thời gian tuyến tính có độ phức tạp O(n), nghĩa là thời gian xử lý tăng tỷ lệ thuận với số lượng đỉnh, đây là mức hiệu quả rất cao trong khoa học máy tính và tối ưu tổ hợp. So với nhiều bài toán vị trí vốn thường thuộc nhóm NP-hard trên đồ thị tổng quát, việc đạt được lời giải tối ưu trong thời gian tuyến tính trên các lớp đồ thị đặc biệt là kết quả có giá trị đáng kể cả về mặt học thuật lẫn ứng dụng.

Ý nghĩa của kết quả này nằm ở chỗ nó không chỉ cung cấp lời giải hiệu quả cho một bài toán cụ thể mà còn mở rộng hiểu biết về khả năng khai thác cấu trúc đồ thị để thiết kế thuật toán tối ưu. Trong các hệ thống lớn yêu cầu xử lý nhanh như mạng lưới logistics, phân phối hoặc hạ tầng kỹ thuật số, các thuật toán tuyến tính có thể mang lại lợi ích lớn về tốc độ và khả năng mở rộng.

Tóm lại, nghiên cứu đã đóng góp quan trọng vào lĩnh vực bài toán vị trí trên đồ thị bằng cách xây dựng cơ sở lý thuyết và thuật toán hiệu quả cho bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ. Kết quả không chỉ có giá trị trong phát triển lý thuyết tối ưu tổ hợp mà còn tạo nền tảng cho các nghiên cứu tiếp theo trên các mô hình đồ thị khác, góp phần thúc đẩy ứng dụng của lý thuyết đồ thị trong giải quyết các vấn đề tối ưu hóa thực tiễn phức tạp.