Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị. Nội dung chính trong chương này gồm có: Chu số, sắc số, số ổn định trong, số ổn định ngoài, nhân của đồ thị, trò chơi Nim,. để biết thêm nội dung chi tiết. | Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị 2 C´ o´ co. ba˙’n cu˙’a d ac sˆ `o thi. ¯ˆ o´ Chu sˆ Kh´ai m`a ch´ung ta s˜e d¯`ˆe o˙’. d¯ˆay khˆong phu. v`ao su d¯.inh hu.´: ta s˜e n´oi vˆ `e ch´ . ˙’ - ˙ ’ ˙ ’ ` . . u khˆong phai cung. Dˆe tˆo ng qu´at x´et d¯a d¯ˆo thi. vˆo hu ´o ng G := (V, E) c´o n d¯ınh, m ˙ ’ v`a p th`anh phˆ`an liˆen thˆong. D - ρ(G) := n − p, ν(G) := m − ρ(G) = m − n + p. Ta ν(G) l`a chu sˆo´ cu˙’a d¯`oˆ thi. G. - l´ D y Cho d¯a d¯`ˆo thi. vˆo hu.´ G = (V, E). Gia˙’ su˙’. G0 l`a d¯`ˆo thi. d¯ t` u. G bˇ`a ng c´ach nˆo´i hai d¯ı˙’nh a v`a b cu˙’ a G bo˙’.i m´; nˆe´u a v`a b tr` ung nhau c´o thˆe˙’ . . nˆo´i v´o i nhau bo˙’ i dˆay chuyˆ`en cu˙’ a G th`ı ρ(G0 ) = ρ(G), ν(G0 ) = ν(G) + 1; trong tru.` hop ρ(G0 ) = ρ(G) + 1, ν(G0 ) = ν(G). Ch´ minh. Theo c´ach xˆay dung, d¯a d¯`ˆo thi. G0 c´o n0 = n d¯ı˙’nh, m0 = m + 1 v`a gia˙’ su˙’. `an liˆen thˆong. G0 c´o p0 th`anh phˆ Nˆe´u a ≡ b c´o dˆay chuyˆ `en nˆo´i a v´ b. Khi d¯´o ph´ep biˆe´n d¯oˆ˙’i G th`anh G0 khˆong thay d¯ˆo˙’i sˆo´ th`anh phˆ l`a p = p0 . Do d¯´o `an liˆen thˆong, t´ ρ(G0 ) = n0 − p0 = n − p = ρ(G), ν(G0 ) = m0 − ρ(G0 ) = ν(G) + 1. 49 , nˆe´u a 6= b v`a khˆong tˆ `on dˆay chuyˆ `en nˆo´i a v`a b, th`ı do c´ach x´ac d¯ G0 0 ta c´o p = p − 1. Suy ra ρ(G0 ) = n0 − p0 = n − (p − 1) = n − p + 1 = ρ(G) + 1, ν(G0 ) = m0 − ρ(G0 ) = (m + 1) − (ρ(G) + 1) = m − ρ(G) = ν(G). / e. qua˙’ ρ(G) ≥ 0 v`a ν(G) ≥ 0. Hˆ Ch´ minh. , xuˆa´t ph´at t` u. d¯`ˆo thi. th`anh bˇ`a ng c´ac d¯ı˙’nh cu˙’a d¯a d¯`oˆ thi. vˆo hu.´ G, d¯ı˙’nh no. cˆo v´ d¯ı˙’nh kia, ta xˆay dung G0 dˆ `an dˆ`an t` ; kho˙’.i d¯`ˆau ta c´o ρ = 0, ν = 0; mˆo˜i khi thˆem
