Lý thuyết đồ thị - Phần 3

Đồ thị vô hướng (có hướng) G=(V,E) được gọi là đồ thị có trong số nếu mỗi cạnh (cung) ...
Nội dung trích xuất từ tài liệu:
Lý thuyết đồ thị - Phần 3 3.3.Đườngđitrongđồthị 3.3.1.Địnhnghiãđườngđi. 3.3.2.Tínhliênthông. 3.3.3.ChutrìnhEulervàđườngđiEuler. 3.3.4.Tìmđườngđingắnnhất.Oct1,2010 3.3.Đườngđitrongđồthị 1 3.3.4.Tìmđườngđingắnnhất  Đồthịcótrọngsố  Địnhnghĩa1. Đồthịvôhướng(cóhướng)G =(V,E)đượcgọilàđồthịcótrọngsố nếumỗicạnh(cung)e∈Eđượcđặttươngứngvớimộtsốthực w(e).Sốthựcw(e)đượcgọilàtrọngsốcủacạnh(cung)e.  Địnhnghĩa2. Ma trận trọng số của đơn đồ thị G =(V,E) là ma trận W=[wi,k] trongđó wi,klàtrọngsốcủacạnh(cung)nốiđỉnhthứivớiđỉnhthứk (nếucó); wi,k=∞ nếukhôngcócạnh(cung)nốiđỉnhthứivớiđỉnhthứ k.Oct1,2010 3.3.Đườngđitrongđồthị 2 3.3.4.Tìmđườngđingắnnhất  Theođịnhnghiãtrên:  cácphầntửcủamatrậntrọngsócóthểlàcácsốâm.  Mộtđơnđồthịbấtkỳcũngcóthểxemlàđồthịcótrọngsốnếu mỗicạnh(cung)đềugắntrọngsốlà1(nhưđịnhnghĩađườngđi độ dài 1 trong mục trước) và khi đó ma trận trọng số chính là matrận01.  Vídụ:  xét một mạng hàng không, khi đó mạng này có thể coi là các đồthịcótrọngsốvớicáckiểutrọngsốsauđây:  Độdàicungđườngbay  Giácướcvậnchuyểnchomộtđơnvịvậnchuyển  thờigianthựchiệnchuyếnbaygiữahaisânbayOct1,2010 3.3.Đườngđitrongđồthị 3 3.3.4.Tìmđườngđingắnnhất Vídụ: Matrậntrọngsốcủađồthịtrênlà 0 15 20 0 20 14  15 0 11 18 0 24    20 11 0 13 22 0 W=  0 18 13 0 16 21  20 0 22 16 0 12    14  24 0 21 12 0Oct1,2010 3.3.Đườngđitrongđồthị 4 3.3.4.Tìmđườngđingắnnhất  Bàitoánđượcđặtralà:  tìmđườngđingắnnhấttrongđồthịcótrọngsốG =(V,E)từ đỉnhxđếnđỉnhychotrước.  Ýtưởnggiảithuậtlà:  ta sẽ lần lượt duyệt và xác định độ dài của đường đi ngắn nhấttừđỉnhxđếncácđỉnhlâncận,chođếnkhiđỉnhđíchy đượcduyệt.  Ở mỗi bước duyệt, mỗi đỉnh v sẽ được gắn nhãn, là cặp (l(v);t(v))trongđó:  l(v) là độ dài của đường đi tìm được từ đỉnh đầu x đến đỉnh v chođếnthờiđiểmđangxét;  t(v)làđỉnhtrướcđỉnhvtrongđườngđiđó.Oct1,2010 3.3.Đườngđitrongđồthị 5 3.3.4.Tìmđườngđingắnnhất  TừđótacóthuậttoánsauđâyDijkstra(Hàlan19302002):  Bướckhởiđầu: Vớimọiđỉnhv∈V, l(v):=∞;t(v):=‘’; L(x):=0;{độdàiđườngđitừxđếnxbằng0} S:=∅;{Slàtậpđỉnhđãđượcduyệt}  Bướclặp: Khiy∉Sthựchiện: Tìmutrongtậpcácđỉnhchưađượcduyệt(u∈VS)saochol(u)bénhất; S:=S∪{u}; Vớimọiđỉnhvthuộctậpcácđỉnhchưađượcduyệtvàcócạnh(cung)từuđến v,thựchiện Nếul(u)+wuv 3.3.4.Tìmđườngđingắnnhất Vídụ: Bước A1 A2 A3 A4 A5 A6 khởiđầuTìmđườngđingắn 0 ∞ ∞ ∞ ∞ ∞ nhấttừA1đếnA4 Bước1 0 15,A1 20,A1 ∞ 20,A1 14,A1 A1 Bước2 0 15,A1 20,A1 35,A6 20,A1 14,A1 A6 Bước3 0 15,A1 20,A1 33,A2 20,A1 14,A1 A2 ...