Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi

Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi. Nội dung chính trong chương này gồm có: Đường đi giữa hai đỉnh, đường đi ngắn nhất giữa hai đỉnh, đường đi ngắn nhất giữa tất cả các cặp đỉnh, phát hiện mạch có độ dài âm. 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 3: Các bài toán về đường điChu.o.ng 3C´ ac b` ai to´ an vˆ ¯u.` `e d o.ng d ¯iTrong c´ac u ´.ng du.ng thu..c tˆe´, ta cˆ`an t`ım d¯u.`o.ng d¯i (nˆe´u c´o) gi˜ u.a hai d¯ı˙’nh cu˙’a d¯`oˆ thi.. D - ˇa.c . .biˆe.t, b`ai to´an t`ım d¯u `o ng d¯i ngˇa´n nhˆa´t gi˜ . u a hai d¯ı˙’nh cu˙’a mˆo.t d¯`oˆ thi. c´o y . ´ ngh˜ıa to l´o n. C´o ˙ ’ ˜thˆe dˆan vˆ . `e b`ai to´an nhu vˆa.y t` . u nhiˆ . `eu b`ai to´an thu. c tˆe´. V´ı du., b`ai to´an t`ım h`anh tr`ınhtiˆe´t kiˆe.m nhˆa´t (theo tiˆeu chuˆa˙’n khoa˙’ng c´ach, th`o.i gian hoˇa.c chi ph´ı) trˆen mˆo.t ba˙’n d¯`oˆ giaothˆong; b`ai to´an cho.n phu.o.ng ph´ap tiˆe´t kiˆe.m nhˆa´t d¯ˆe˙’ d¯u.a mˆo.t hˆe. d¯oˆ. ng lu..c t` u. tra.ng th´ain`ay sang tra.ng th´ai kh´ac v.v... Hiˆe.n nay c´o rˆa´t nhiˆ `eu phu.o.ng ph´ap du..a trˆen l´ y thuyˆe´t d¯`ˆo . .thi. to˙’ ra l`a c´ac phu o ng ph´ap c´o hiˆe.u qua˙’ nhˆa´t. Chu.o.ng n`ay tr`ınh b`ay c´ac thuˆa.t to´an t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t trˆen d¯`ˆo thi. c´o tro.ng sˆo´.3.1 - u.` D o.ng d u.a hai d ¯i gi˜ ¯ı˙’nh3.1.1 - u.` D o.ng d u.a hai d ¯i gi˜ ¯ı˙’nhTrong nhiˆ `eu tru.`o.ng ho..p, ch´ ung ta cˆ`an tra˙’ l`o.i cˆau ho˙’i: Tˆ `on ta.i d¯u.`o.ng d¯i µ t`u. d¯ı˙’nh s d¯ˆe´n . . . .d¯ı˙’nh t cu˙’a d¯`oˆ thi. c´o hu ´o ng G := (V, E)? Nˆe´u c´o, h˜ay chı˙’ ra c´ach d¯i cu˙’a d¯u `o ng d¯i µ. L`o.i gia˙’i cu˙’a b`ai to´an n`ay kh´a d¯o.n gia˙’n: ch´ `an ´ap du.ng thuˆa.t to´an t`ım kiˆe´m ung ta chı˙’ cˆtheo chiˆ `eu rˆo.ng (hoˇa.c chiˆ `eu sˆau) trˆen d¯`ˆo thi. c´o hu.´o.ng G nhu. sau. G´an mˆo˜i d¯ı˙’nh cu˙’a G mˆo.tchı˙’ sˆo´. Bˇa` ng phu.o.ng ph´ap lˇa.p, dˆ `an dˆ`an ta s˜e cho mˆo˜i d¯ı˙’nh v mˆo.t chı˙’ sˆo´ n`ao d¯o´ bˇ`a ng d¯oˆ. . . ´d`ai d¯u `o ng d¯i ngˇan nhˆa t (sˆo cung ´ıt nhˆa´t) t` ´ ´ u. s t´o.i v. D - ´anh dˆa´u d¯ı˙’nh s bˇ`a ng chı˙’ sˆo´ 0. Nˆe´uc´ac d¯ı˙’nh d¯u o. c d¯´anh dˆa´u bˇ`a ng chı˙’ sˆo´ m lˆa.p th`anh mˆo.t tˆa.p ho..p P (m) d¯a˜ biˆe´t, th`ı ta d¯a´nh . .dˆa´u chı˙’ sˆo´ (m + 1) cho mo.i d¯ı˙’nh cu˙’a tˆa.p ho..p: P (m + 1) := {vj chu.a d¯u.o..c d¯a´nh dˆa´u | tˆ `on ta.i vi ∈ P (m) v´o.i (vi , vj ) ∈ E}. 75 http://www.ebook.edu.vn u.ng khi khˆong thˆe˙’ d¯´anh dˆa´u d¯u.o..c n˜Thuˆa.t to´an d` u.a. C´o hai tru.`o.ng ho..p xa˙’y ra: - ı˙’nh t d¯u.o..c d¯a´nh dˆa´u, chˇa˙’ng ha.n t ∈ P (m) v´o.i m n`ao d¯´o, th`ı ta x´et c´ac d¯ı˙’nh v1 , v2 , ..., 1. D sao cho v1 ∈ P (m − 1), v2 ∈ P (m − 2), . . . , vm ∈ P (0). Khi d¯o´ µ := {s = v , v m m−1 , ..., v , t} l`a d¯u.`o.ng d¯i pha˙’i t`ım. 1 2. D- ı˙’nh t khˆong d¯u.o..c d¯a´nh dˆa´u. Trong tru.`o.ng ho..p n`ay, ta kˆe´t luˆa.n khˆong tˆ `on ta.i d¯u.`o.ng d¯i t` . u s d¯ˆe´n t. Theo c´ach xˆay du..ng cu˙’a thuˆa.t to´an, dˆ˜e d`ang ch´ u.ng minh rˇ`a ngMˆ e.nh d `e 3.1.1 Nˆe´u d¯`ˆo thi. d¯u.o..c x´ac d¯.inh bo˙’.i d˜ay liˆen tiˆe´p c´ac d¯ı˙’nh, th`ı thuˆa.t to´an c´o ¯ˆth`o.i gian O(m).3.1.2 - `ˆ D o thi. liˆ en thˆ ong ma.nhNhˇa´c la.i l`a d¯`oˆ thi. c´o hu.´o.ng G go.i l`a liˆen thˆong ma.nh nˆe´u hai d¯ı˙’nh s v`a t t` ´ cu˙’a G luˆon uy y . . `on ta.i mˆo.t ...