Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị

Đồ 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,... Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thịChu.o.ng 2C´ o´ co. ba˙’n cu˙’a d ac sˆ `o thi. ¯ˆ2.1 o´ Chu sˆKh´ai niˆe.m m`a ch´ung ta s˜e d¯`ˆe cˆa.p o˙’. d¯ˆay khˆong phu. thuˆo.c v`ao su.. d¯.inh hu.´o.ng: ta s˜e n´oi vˆ `eca.nh 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 ˙ ’ca.nh v`a p th`anh phˆ`an liˆen thˆong. D - ˇa.t ρ(G) := n − p, ν(G) := m − ρ(G) = m − n + p.Ta go.i ν(G) l`a chu sˆo´ cu˙’a d¯`oˆ thi. G.- i.nh l´D y 2.1.1 Cho d¯a d¯`ˆo thi. vˆo hu.´o.ng G = (V, E). Gia˙’ su˙’. G0 l`a d¯`ˆo thi. nhˆa.n d¯u.o..c t` u. Gbˇ`a ng c´ach nˆo´i hai d¯ı˙’nh a v`a b cu˙’ a G bo˙’.i mˆo.t ca.nh m´o.i; nˆe´u a v`a b tr` ung nhau hoˇa.c c´o thˆe˙’ . .nˆo´i v´o i nhau bo˙’ i mˆo.t dˆay chuyˆ`en cu˙’ a G th`ı ρ(G0 ) = ρ(G), ν(G0 ) = ν(G) + 1;trong tru.`o.ng ho..p ngu.o..c la.i ρ(G0 ) = ρ(G) + 1, ν(G0 ) = ν(G).Ch´u.ng minh. Theo c´ach xˆay du..ng, d¯a d¯`ˆo thi. G0 c´o n0 = n d¯ı˙’nh, m0 = m + 1 ca.nh v`a gia˙’ su˙’. `an liˆen thˆong.G0 c´o p0 th`anh phˆ Nˆe´u a ≡ b hoˇa.c c´o mˆo.t dˆay chuyˆ `en nˆo´i a v´o.i b. Khi d¯´o ph´ep biˆe´n d¯oˆ˙’i G th`anh G0khˆong thay d¯ˆo˙’i sˆo´ th`anh phˆ u.c 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 http://www.ebook.edu.vn Ngu.o..c la.i, nˆe´u a 6= b v`a khˆong tˆ `on ta.i dˆay chuyˆ `en nˆo´i a v`a b, th`ı do c´ach x´ac d¯i.nh G0 0ta 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˙’ 2.1.2 ρ(G) ≥ 0 v`a ν(G) ≥ 0.HˆCh´ u.ng minh. Thˆa.t vˆa.y, xuˆa´t ph´at t` u. d¯`ˆo thi. th`anh lˆa.p bˇ`a ng c´ac d¯ı˙’nh cu˙’a d¯a d¯`oˆ thi. vˆohu.´o.ng G, d¯ı˙’nh no. cˆo lˆa.p v´o.i d¯ı˙’nh kia, ta xˆay du..ng G0 dˆ `an dˆ`an t`u.ng ca.nh mˆo.t; kho˙’.i d¯`ˆau tac´o ρ = 0, ν = 0; mˆo˜i khi thˆem mˆo.t ca.nh, th`ı hoˇa.c ρ tˇang v`a l´ uc d¯o´ ν khˆong d¯oˆ˙’i, hoˇa.c ν tˇangv`a l´ . . uc d¯o´ ρ khˆong d¯oˆ˙’i. Nhu vˆa.y, trong qu´a tr`ınh xˆay du. ng d¯`oˆ thi. G0 , c´ac sˆo´ ρ v`a ν chı˙’ c´othˆe˙’ tˇang. / u.ng kˆe´t qua˙’ phong ph´ - ˆe˙’ c´o thˆe˙’ vˆa.n du.ng nh˜ D u.u, u cu˙’a d¯a.i sˆo´ vector trong viˆe.c nghiˆen c´ngu.`o.i ta thu.`o.ng d¯aˇ. t tu.o.ng u ´.ng mˆo˜i chu tr`ınh trong G v´o.i mˆo.t vector theo c´ach sau d¯ˆay. Mˆo˜i ca.nh cu˙’a d¯a d¯`oˆ thi. G d¯`ˆeu d¯u.o..c d¯.inh hu.´o.ng mˆo.t c´ach t` ´; nˆe´u chu tr`ınh µ d¯i uy y . . `an thuˆa.n hu ´o ng v`a sk lˆqua ca.nh ek , rk lˆ . . . . `an ngu o. c hu ´o ng th`ı ta d¯ˇa.t ck := rk − sk (nˆe´u ek l`a . .mˆo.t khuyˆen th`ı ta luˆon qui u ´o c sk = 0). Vector m chiˆ `eu (c1 , c2 , . . . , cm )go.i l`a vector chu tr`ınh tu.o.ng u ´.ng v´o.i µ v`a k´ y hiˆe.u ...