A Note on Two Problems in Connexion with Graphs

Edsger W. Dijkstra, 1959, Numerische Mathematik

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Một ghi chú về hai bài toán liên quan đến đồ thị

Bởi

E. W. DIJKSTRA

Xét nn điểm (nút), một số hoặc tất cả các cặp trong số chúng được nối với nhau bởi một nhánh; độ dài của mỗi nhánh được cho trước. Chúng ta chỉ xét trường hợp trong đó tồn tại ít nhất một đường đi giữa bất kỳ hai nút nào. Bây giờ chúng ta xét hai bài toán.

Bài toán 1. Xây dựng cây có tổng độ dài nhỏ nhất giữa nn nút. (Một cây là một đồ thị có một và chỉ một đường đi giữa mỗi hai nút.)

Trong quá trình xây dựng mà chúng ta trình bày ở đây, các nhánh được chia thành ba tập:

I. các nhánh chắc chắn được gán cho cây đang được xây dựng (chúng sẽ tạo thành một cây con);

II. các nhánh mà từ đó nhánh tiếp theo được thêm vào tập I sẽ được chọn;

III. các nhánh còn lại (bị loại bỏ hoặc chưa được xét đến).

Các nút được chia thành hai tập:

A. các nút được nối bởi các nhánh của tập I,

B. các nút còn lại (một và chỉ một nhánh của tập II sẽ dẫn đến mỗi nút này).

Chúng ta bắt đầu việc xây dựng bằng cách chọn một nút tùy ý làm thành viên duy nhất của tập A, và đặt tất cả các nhánh kết thúc tại nút này vào tập II. Ban đầu, tập I là rỗng. Từ đó trở đi, chúng ta lặp lại hai bước sau.

Bước 1. Nhánh ngắn nhất của tập II được lấy ra khỏi tập này và thêm vào tập I.

References

  1. Kruskal jr., J. B.: On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem. Proc. Amer. Math. Soc. 7, 48—50 (1956).
  2. Loberman, H., and A. Weinberger: Formal Procedures for Connecting Terminals with a Minimum Total Wire Length. J. Ass. Comp. Mach. 4, 428—437 (1957).
  3. Ford, L. R.: Network flow theory. Rand Corp. Paper, P-923, 1956.
  4. Berge, C.: Théorie des graphes et ses applications, pp. 68—69. Paris: Dunod 1958. Mathematisch Centrum 2e Boerhaavestraat 49 Amsterdam-O (Received June 11, 1959)

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.