tailieunhanh - Số đồ thị Hamilton tối đại.

Số đồ thị Hamilton tối đại. Quan hệ chức năng ấy bao gồm sự trao đổi thông tin và vòng quan hệ phản hồi (feedback) mà kết quả rõ nét của nó là hiện tượng Tự tổ chức ( Humberto Maturana, Varela và Ricardo Uribe phát hiện), Tự sản sinh - autopoiesis ( Francisco phát hiện). | Tap chi Tin hoc và Điều khiển hoc 2006 221 228 SO DO THI HAMILTON TOI DẠI VU DÌNH HOA1 DO NHƯ AN2 1Khoa Công nghệ thông tin Trường -Dai học Sư phạm Hà Nội 2Khoa Công nghệ thông tin Trường Dại học Nha Trang Abstract. A graph is called a maximal uniquely Hamiltonian graph if it has the maximum number of edges among the graphs with the same number of vertices and exact one Hamiltonian cycle. In this paper we prove the conjecture posed in 5 that for every n 7 there are exactly 2 2 maximal uniquely Hamiltonian graphs. Tóm tắt. Một do thi dược goi là do thi Hamilton tếi dai nếu như nó có so canh nhieu nhat co the trong cac dế thi co cung sộ dinh và có dung một chu trình Hamilton. Trong bai nay chung toi chứng minh giả thuyết dược nếu trong 5 rằng co dung 2 2 1 dế thi Hamilton tội dai n 7 dinh. 1. MỞ DAU Trong bài báo này chúng ta chi nói dến các dồ thi hữu hạn vô hướng. Một dồ thị G dược ky hiệu G V E với V là tộp hợp dinh và E là tạp hợp cạnh cúà G. Đồ thi G1 V1 E1 dược nôi là do thi con cúà dô thi G2 V2 E2 nồú nhú. V1 c V và E1 c E2. Đồ thi con G1 V1 E1 cúà dô thị G2 V2 E2 dúơc gợi là dồ thi thanh phôn cúà G2 nồú nhú môi cành e x y cúà G2 với x y G V1 cúng là cành cúà dô thi G1. Chô trúớc dô thị G V E và S là tàp họp côn cúà V thì dô thi thành phàn cúà G vôi tàp dinh S dược gọi là do thi sinh bởi S và dúô c ky hiộú là G S . Ngôài rà môi ký hiộú và khài niệm khác ô dồy dồú dước lấy tú 3 . Chô t óc một dô thi dôn vồ hượng G tà gôi môt chú trình C cúà G là chu trình Hamilton nệú nó di qúà tẩt cà càc dinh cúà dô thi G. Trông hình 1 tà có môt dô thi 5 dinh vói hài chú trình Hàmiltôn khác nhàú. Hình 1. Đồ thị 5 dinh có hài chú trình Hàmiltôn Đồ thi không có chú trình Hàmiltôn vói nhiềú cành nhàt dà dước nghiồn cứú bởi Erdôs 4 và mồt sô nhà tôàn hôc khàc. Nồú dồ thi G cô chú trình Hàmiltôn thì nó dước gôi là dồ thị Hamilton. Môt dô thi chi có dúng môt chú trình Hàmiltôn dược gôi là dồ thị Hamilton tối dai nồú nhú nô cô nhiềú cành nhồt trông sô càc dô thi cúng sồ dinh