tailieunhanh - Chu trình Hamilton trong đồ thị ơ2>= N

Given a undirected and simple graph with n vertices, we denote by σ2 the minimum of degree sum of the pair of nonadjacent vertices in G and by σ∗2 the minimum of degree sum of the pair of nonadjacent vertices with distance 2. | T¤p ch½ Tin håc v i·u khiºn håc, , (2012), 153 160 ∗ CHU TR NH HAMILTON TRONG Ç THÀ σ2 ≥ N Ô 0 xr rÁe1 D xq x rÚ x ×Íxq2 1 Khoa Cæng ngh» thæng tin, Tr÷íng ¤i håc S÷ ph¤m H nëi 2 Khoa H» thèng thæng tin kinh t¸, Håc vi»n t i ch½nh Tóm t t. gho tr÷î mët 1ç thà 1ìn væ h÷îng vîi n 1¿nhD t kþ hi»u σ2 l têng ª ² nh§t õ ¡ ∗ °p 1¿nh khæng k· nh u trong G v σ2 l têng ª ² nh§t õ ¡ °p 1¿nh ¡ h nh u kho£ng ¡ h PF f i to¡n HC x¡ 1ành hu tr¼nh r milton @ hu tr¼nh 1i qu t§t £ ¡ 1¿nh trong 1ç thàA v¨n 1÷ñ i¸t l i to¡n N P C F ghóng tæi kh£o s¡t i to¡n HC ho lîp ¡ 1ç thà thä m¢n σ2 ≥ tn ∗ v lîp ¡ 1ç thà thä m¢n σ2 ≥ tnD vîi t l h¬ng sè ho tr÷î F rong i ¡o n y hóng tæi x¥y düng thuªt to¡n vîi thíi gi n 1 thù x¡ 1ành hu tr¼nh r milton khi t ≥ 1 v hùng minh r¬ng i to¡n HC v¨n án l i to¡n N P C trong tr÷íng hñp t < 1F Abstract. qiven undire ted nd simple gr ph with n verti esD we denote y σ2 the minimum of ∗ degree sum of the p ir of non dj ent verti es in G nd y σ2 the minimum of degree sum of the p ir of non dj ent verti es with dist n e PF he pro lem HC to determine the r milton y le @ y le p ssing ll the verti es of the gr phA is wellEknown N P C Epro lemF e onsider the pro lem HC for the l ss of gr phs s tisfying σ2 ≥ tn ∗ nd for the l ss of gr phs s tisfying σ2 ≥ tnD with given onst nt tF sn this p per we give polynomi l lgorithm to estim te r milton y le for the se t ≥ 1 nd prove th t the pro lem HC rem ins N P C pro lem for the se t < 1F 1. MÐ U Trong b i b¡o n y chóng ta sû döng kh¡i ni»m v c¡c kþ hi»u v· ç thà nh÷ trong [3], ri¶ng ç thà ¦y õ vîi n ¿nh th¼ kþ hi»u l Kn . Ta ch¿ kh£o s¡t c¡c ç thà ìn væ h÷îng, li¶n thæng. Mët ç thà ÷ñc gåi l nûa Hamilton n¸u nâ câ mët ÷íng i qua t§t c£ c¡c ¿nh cõa ç thà ( ÷íng Hamilton). T÷ìng tü, ç thà ÷ñc gåi l ç thà Hamilton n¸u nâ câ chu tr¼nh Hamilton (chu tr¼nh chùa t§t c£ c¡c ¿nh cõa ç thà). Cho .

• Cơ sở dữ liệu
• Chu trình Hamilton
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton
• thuật toán
• ứng dụng cây
• hàm trên đồ thị