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).
Nội dung trích xuất từ tài liệu:
Số đồ thị Hamilton tối đại. . . a ` e e’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.22, S.3 (2006), 221—228 ı . ´ ` ˆ ˆ ´ ˆ SO DO THI HAMILTON TOI DAI . . ˜ INH HOA1 , DO NHU. AN2 VU D` ` ˜ ˆ 1 Khoa Cˆng nghˆ thˆng tin, Tru.`.ng Dai hoc Su. pham H` Nˆi o e o . o . . . a o. 2 Khoa Cˆng nghˆ thˆng tin, Tru.`.ng Dai hoc Nha Trang o e o . o . .Abstract. A graph is called a maximal uniquely Hamiltonian graph if it has the maximum numberof edges among the graphs with the same number of vertices and exact one Hamiltonian cycle. In this n−7paper, we prove the conjecture posed in [5] that for every n ≥ 7 there are exactly 2[ 2 ] maximaluniquely Hamiltonian graphs.T´m t˘t. Mˆt dˆ thi du.o.c goi l` dˆ thi Hamilton tˆi dai nˆu nhu. n´ c´ sˆ canh nhiˆu nhˆ t c´ thˆ o ´ a o o . . ` . ` . a o . ´ o . e ´ ´ o o o . ` e ´ a o e ’ a o ` thi c´ c` ng sˆ dınh v` c´ d´ng mˆt chu tr` Hamilton. Trong b`i n`y, ch´ ng tˆi ch´.ngtrong c´c dˆ . o u ´ ’ o a o u o . ınh a a u o u n−7minh gia thuyˆt du.o.c nˆu trong [5] r˘ ng c´ d´ ng 2[ 2 ] dˆ thi Hamilton tˆi dai n ≥ 7 dınh. ’ ´ e . e ` a o u ` o . ´ o . ’ ’. A 1. MO D` U ˆ Trong b`i b´o n`y, ch´ng ta chı n´i dˆn c´c dˆ thi h˜.u han vˆ hu.´.ng. Mˆt dˆ thi G du.o.c a a a u ´ ’ o e a o . u ` . o o . ` o o . .k´ hiˆu G = (V, E) v´ y e o.i V l` tˆp ho.p dınh v` E l` tˆp ho.p canh cua G. Dˆ thi G = (V , E ) a a ’ a a a ’ ` o . 1 . . . . . . 1 1 .o.c n´i l` dˆ thi con cua dˆ thi G2 = (V2 , E2 ) nˆu nhu. V1 ⊆ V2 v` E1 ⊆ E2 . Dˆ thi condu . o a o ` . ’ o .` e´ a ` . oG1 = (V1 , E1 ) cua dˆ thi G2 = (V2 , E2 ) du.o.c goi l` dˆ thi th`nh phˆn cua G2 nˆu nhu. mˆi ’ o .` . . ` a o . a ` a ’ ´ e ˜ ocanh e = (x, y) cua G2 v´.i x, y ∈ V1 c˜ng l` canh cua dˆ thi G1 . Cho tru.´.c dˆ thi G = (V, E) . ’ o u a . ’ o .` o o . `v` S l` tˆp ho.p con cua V , th` dˆ thi th`nh phˆn cua G v´.i tˆp dınh S du.o.c goi l` dˆ thi a a a. . ’ ` ı o . a `a ’ o a ’ . . . a o .`sinh bo.i S v` du.o.c k´ hiˆu l` G[S]. Ngo`i ra, moi k´ hiˆu v` kh´i niˆm kh´c o. dˆy dˆu du.o.c ’ a . y e a . a . y e a a e . . a ’ a ` e .lˆ y t`. [3]. Cho tru.´.c mˆt dˆ thi do.n vˆ hu.´.ng G, ta goi mˆt chu tr`nh C cua G l` chu tr`nh ´ a u o . ` o o . o o . o . ı ’ a ı ´ e o ´ a ’ a ’ ` ’ o . . `Hamilton nˆu n´ di qua tˆ t ca c´c dınh cua dˆ thi G. Trong h` 1 ta c´ mˆt dˆ thi 5 dınh ınh ...