Báo cáo Thực tập : Lý thuyết đồ thị trong toán học

Lời Mở Đầu Lý thuyết đồ thị là một lĩnh vực đó cú từ lõu và cú nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toỏn học lỗi lạc người Thụy Sỹ Lenhard Euler. Đồ thị được sử dụng để giải cỏc bài toỏn trong nhiều lĩnh lực khỏc nhau . Chẳng hạn , đồ thị cú thể sử để xỏc định mạch vũng trong vấn đề giải tớch mạch điện. Đồ thị cú trọng số trờn cỏc cạnh cú thể sử dụng để giải cỏc bài toỏn như: Tỡm đường đi ngắn nhất giữa hai thành phố trong mạnh giao thụng. Chỳng ta cũng cũn sử dụng đồ thị để giải cỏc bài toỏn về lập lịch , thời khoa biểu… Đặc biệt trong khoảng vài mươi năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của tin học, lí thuyến đồ thị càng được quan tâm đến nhiều hơn. Các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lí thuyết mã, Tối ưu hoá…. Trong phạm vi đề tài này do thời gian cú hạn chỳng em chỉ nghiên cứu về một số bài toán về đường đi trong lí thuyết đồ thị như: Bài toán tìm chu trình Euler, Bài toán tìm đường đi ngắn nhất , Thuật toán Dijkstral. Chỳng em rất mong được sự đúng gúp ý kiến của thầy cụ và cỏc bạn. Chúng em đặc biệt bày tỏ lòng biết ơn chân thành tới thầy giáo, Tiến sĩ: Nguyễn Trung Hũa, người thầy đã tạo mọi điều kiện và luôn giúp đỡ, hướng dẫn chúng em tận tình để chúng em hoàn thành tốt đề tài này. Nhúm sinh viờn thực hiện: Lờ Thị Thu Hiền Nguyễn Thị Thảo Trịnh Thị Thủy Nguyễn Trọng Tài Phần I: Cỏc khỏi niệm cơ bản về lý thuyết đồ thị Định nghĩa: Là một cấu trỳc rời rạc gồm cỏc đỉnh và cỏc cạnh nối cỏc đỉnh đú. Được mụ tả hỡnh thức: G = (V, E) V gọi là tập cỏc đỉnh (Vertices) và E gọi là tập cỏc cạnh (Edges). Cú thể coi E là tập cỏc cặp (u, v), với u và v là hai đỉnh của V. Cú thể phõn loại đồ thị theo đặc tớnh và số lượng của tập cỏc cạnh E: Cho đồ thị G = (V, E). Định nghĩa một cỏch hỡnh thức 1. G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V cú nhiều nhất là 1 cạnh trong E nối từ u tới v. 2. G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V cú thể cú nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiờn đơn đồ thị cũng là đa đồ thị). 3. G được gọi là đồ thị vụ hướng nếu cỏc cạnh trong E là khụng định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay núi cỏch khỏc, tập E gồm cỏc cặp (u, v) khụng tớnh thứ tự. (u, v)≡(v, u) 4. G được gọi là đồ thị cú hướng nếu cỏc cạnh trong E là cú định hướng, cú thể cú cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đó cú cạnh nối từ đỉnh v tới đỉnh u. Hay núi cỏch khỏc, tập E gồm cỏc cặp (u, v) cú tớnh thứ tự: (u, v) ≠ (v, u). Trong đồ thị cú hướng, cỏc cạnh được gọi là cỏc cung. Đồ thị vụ hướng cũng cú thể coi là đồ thị cú hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u). B A E D C Hỡnh 1.2: Đồ thị cú hướng Hỡnh 1.1: Đồ thị vụ hướng a — e — c — d — g — f — b — Vớ dụ : Rất nhiều bài toỏn cú thể mụ hỡnh hoỏ bằng đồ thị và giải quyết bằng cỏc thuật toỏn trờn đồ thị. Vớ dụ: Xếp lịch thi đấu là một đồ thị vụ hướng với mỗi đội là đỉnh, hai đội thi đấu với nhau là cạnh. Mạng giao thụng là một đa đồ thị cú hướng với nỳt giao thụng là đỉnh, đường đi giữa hai nỳt là cung. Tương tự việc thiết kế mạng mỏy tớnh, mạng viễn thụng cú thể đưa về bài toỏn đồ thị Cỏc khỏi niệm 1 . Cỏc khỏi niệm cơ bản Khuyờn: cạnh (cung) e gọi là khuyờn nếu e cú dạng (v,v). Cạnh (cung) lặp: là hai cạnh (cung) cựng tương ứng với một cặp đỉnh. Đỉnh kề: nếu (u,v) là cạnh (hoặc cung) của đồ thị thỡ v gọi là kề của u. Trong đồ thị vụ hướng nếu v kề u thỡ u cũng kề v, nhưng trong đồ thị cú hướng thỡ khụng chắc. Cạnh liờn thuộc: Trong đồ thị vụ hướng, cạnh e=(u,v) gọi là cạnh liờn thuộc với đỉnh u và liờn thuộc với đỉnh v. Bậc của đỉnh: Trong đồ thị vụ hướng, số cạnh liờn thuộc với v gọi là bậc của đỉnh v, kớ hiệu là deg(v). Vớ dụ: Xột đồ thị hỡnh 1,deg(a)=1, deg(b)=deg(c)=4, deg(d)=1, deg(e)=deg(f)=3, deg(g)=0 Đỉnh cụ lập, đỉnh treo: Trong đồ thị vụ hướng, đỉnh bậc 0 gọi là đỉnh cụ lập , đỉnh bậc 1 gọi là đỉnh treo. Vớ dụ: Xột đồ thị hỡnh 1.1. Ta cú a là đỉnh treo, g là đỉnh cụ lập Cung vào, ra: Trong đồ thị cú hướng, cung e=(u,v) gọi là cung ra khỏi u và là cung vào v. Bỏn bậc của đỉnh: Trong đồ thị cú hướng, số cung vào v gọi là bỏn bậc vào của đỉnh v, kớ hiệu là: deg-(v), số cung ra khỏi v gọi là bỏn bậc ra của đỉnh v, kớ hiệu là: deg+(v) Vớ dụ: Xột đồ thị hỡnh 1.1, deg-(A)=2, deg-(B)=3, deg-(C)=1, deg-(D)=2, deg-(E)=2 deg+(A)=3, deg+(B)=2, deg+(C)=2, deg+(D)=2, deg+(E)=1 Định lý 1: Trong đồ thị vụ hướng thỡ tổng bậc của tất cả cỏc đỉnh bằng 2 lần số cạnh. = 2m (m là số cạnh) Chứng minh: Mỗi cạnh e=(u,v) được tớnh một lần trong deg(u) và một lần trong deg(v) nờn trong tổng bậc của cỏc đỉnh, mỗi cạnh được tớnh hai lần, mà cú m cạnh nờn suy ra tổng bậc bằng 2m. Hệ quả: Trong đồ thị vụ hướng, số đỉnh cú bậc là số lẻ là một số chẵn Chứng minh: Gọi O là tập cỏc đỉnh cú bậc là số lẻ, và U là tập cỏc đỉnh cú bậc là số chẵn. Ta cú: = + = 2m Do vU, deg(v) chẵn nờn chẵn Do vO, deg(v) lẻ mà tổng chẵn, nờn tổng này phải gồm một số chẵn cỏc số hạng số đỉnh cú bậc là số lẻ là một số chẵn (đpcm). Định lý 2: Trong đồ thị cú hướng, tổng bỏn bậc ra của tất cả cỏc đỉnh bằng tổng bỏn bậc vào của tất cả cỏc đỉnh và bằng số cạnh của đồ thị = = m (m là số cạnh) Chứng minh: Hiển nhiờn vỡ mỗi cung đều ra ở một đỉnh và vào ở một đỉnh khỏc. 2. Cỏch biểu diễn đồ thị trong mỏy tớnh Ma trận kề, ma trận trọng số Xột đơn đồ thị G=(V,E) với V là tập cỏc đỉnh , E là tập cỏc cạnh. Ma trận kề: Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai, j = 0, nếu (i,j) E và ai,j = 1 , nếu (i,j) E, i, j=1, 2,. . .,n. gọi là ma trận kề của đồ thị G. Vớ dụ: Hỡnh 2.1. Đồ thị vụ hướng G và Đồ thị cú hướng G1 1 2 3 4 5 6 1 0 1 1 0 1 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 4 0 0 1 0 1 1 5 1 1 0 1 0 1 6 0 0 0 1 1 0 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 0 0 0 0 3 0 1 0 1 0 0 4 0 0 0 0 0 0 5 0 0 0 1 0 1 6 0 0 0 0 1 0 Ma trận kề G Ma trận kề G1 * Tớnh chất của ma trận kề của đồ thị vụ hướng: Tớnh đối xứng: a[i,j]=a[j,i], i,j=1,2,. . .,n. Tổng cỏc phần từ trờn dũng i (cột j) bằng bậc của đỉnh i (đỉnh j). Gọi aịjp , i,j=1, 2,. . . ,n là phần tử của ma trận Ap =A.A. . .A (p thừa số) Khi đú: aịjp , i,j=1, 2,. . . ,n là số đường đi khỏc nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. * Tớnh chất của ma trận kề của đồ thị cú hướng: Khụng cú tớnh đối xứng Tổng cỏc phần từ trờn dũng i bằng bỏn bậc ra của đỉnh i và tổng cỏc phần từ trờn cột j bằng bỏn bậc vào của đỉnh j. Giống tớnh chất 3 của vụ hướng * Ma trận kề của đa đồ thị: a[i,j]=số cạnh (cung) nối hai đỉnh i, j. Ma trận trọng số: Đồ thị cú trọng số là đồ thị mà mỗi cạnh (i,j) cú một giỏ trị c(i,j) gọi là trọng số của cạnh. Để biểu diễn đồ thị ta sử dụng ma trận trọng số C= {c[i,j], i,j=1, 2,. . .,n} với      c[i,j]=c(i,j) nếu (i,j) E và  c[i,j]= nếu (i,j) E trong đú số cú thể được đặt bằng một trong cỏc giỏ trị sau: 0, + , - . Ưu điểm lớn nhất của phương phỏp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời cõu hỏi: Hai đỉnh u,v cú kề nhau trờn đồ thị hay khụng, chỳng ta chỉ phải thực hiện một phộp so sỏnh. nhược điểm lớn nhất của phương phỏp này là: khụng phụ thuộc vào số cạnh của đồ thị, ta luụn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nú. Ma trận liờn thuộc đỉnh-cạnh Xột G=(V, E) là đơn đồ thị cú hướng. Ma trận liờn thuộc đỉnh-cạnh cú dạng: 1, nếu i là đỉnh đầu của cung ej -1, nếu i là đỉnh cuối của cung ej 0, nếu i khụng là đầu mỳt của cung ej aij = 1 2 4 6 5 3 Vớ dụ: Hinh 2.2 (1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (4,6) (5,2) (5,6) 1 1 1 0 0 0 0 0 0 0 2 -1 0 1 1 0 0 0 -1 0 3 0 -1 -1 0 1 0 0 0 0 A= 4 0 0 0 -1 0 1 1 0 0 5 0 0 0 0 -1 0 0 1 1 6 0 0 0 0 0 0 -1 0 -1 Danh sỏch cạnh (cung) Trong trường hợp đồ thị thưa (đồ thị cú số cạnh m thoả món bất dẳng thức: m<6n) người ta thường dựng cỏch biểu diễn đồ thị dưới dạng danh sỏch cạnh. Chỳng ta sẽ lưu trữ danh sỏch tất cả cỏc cạnh (cung) của đồ thị. Một cạnh (cung) e=(x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cỏch biểu diễn này tỡm cỏc đỉnh kề với một đỉnh cho trước chỳng ta phải làm cỡ m phộp so sỏnh (khi duyệt qua danh sỏch tất cả cỏc cạnh của đồ thị). Trong trường hợp đồ thị cú trọng số ta cần thờm m đơn vị bộ nhớ để lưu trữ trọng số của cỏc cạnh. Vớ dụ: D/s cạnh (cung) của G (G1) ( hỡnh 1) Đầu Cuối Đầu Cuối 1 2 1 2 1 3 1 3 1 5 3 2 2 3 3 4 2 5 5 4 3 4 5 6 4 5 6 5 4 6 5 6 D/s cạnh của G          D/s cung của G1 Danh sỏch kề Với mỗi đỉnh v, ta lưu trữ danh sỏch cỏc đỉnh kề với v: Ke(v)={u V: (v,u)E} Vớ dụ: - Danh sỏch kề của G Đỉnh đầu - Danh sỏch kề của hỡnh G1 Đỉnh đầu Trong cỏch biểu diễn này chỳng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ. III. Đường đi trong đồ thị 1 Đường đi Xét đồ thị G = với - Tập đỉnh V = {v1,v2,...,vn} - Tập cạnh E = {e1,e2,...,em} Tập hợp các đỉnh kề nhau từ vi đến vj được gọi là 1 đường đi, kí hiệu vivi1vi2 ... vj º vieivi1ei1vi2ei2 ... ejvj Trong đó các cạnh, các đỉnh trong đường đi có thể lặp lại 2 Chu trình Xét một đường đi từ vi - vj. Nếu vi º vj thì đường đi này được gọi là một chu trình. Như vậy chu trình là một đường đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau. Chú ý rằng đường đi trong đồ thị có hướng không được đi ngược chiều mũi tên - Đường đi (chu trình) được gọi là đơn nếu nó đi qua mỗi cạnh không quá một lần. - Đường đi (chu trình) được gọi là sơ cấp nếu nó đi qua mỗi đỉnh đúng một lần 3 Đường đi và chu trình của đồ thị vô hướng: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G=(V,E) là dãy: x, x, …, xn-1, xn. Trong đó: u=x0, v=xn, (xi,xi+1) thuộc E. i=0,1,2,…, n-1. Đường đi trên còn được biểu diễn dưới dạng cạnh: (x0,x1), (x1,x2), …,(xn-1,xn). Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u trùng với v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu không có cạnh nào bị lặp lại. A B C D E Hỡnh2.3 Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung. 4. Đường đi và chu trình của đồ thị có hướng: Đường đi có độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị có hướng là dãy: x, x, …, xn-1, xn. Trong đó: u=x0, v=xn, (xi,xi+1) thuộc E. i=0,1,2,…, n-1. Đường đi trên còn được biểu diễn dưới dạng các cung: (x0,x1), (x1,x2), …,(xn-1,xn). Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u trùng với v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu không có cạnh nào bị lặp lại. 5. Đồ thị liên thông Cho đồ thị G = . Hai đỉnh phân biệt u,v ẻ V được gọi là liên thông nếu tồn tại một đường đi nối các đỉnh u,v với nhau. Đồ thị G được gọi là liên thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông. Ví dụ như hình 2.3 là một đồ thị liên thông vì luôn có đường đi nối hai đỉnh bất kỳ của đồ thị, còn đồ thị như hình 2 là không liên thông vì không có đường đi từ A tới D hoặc từ D tới F v.v.. Xét 2 đồ thị liên thông G1 = và G2 = Trong đó: V1 ầ V2 = ặ và E1 ầ E2 = ặ Khi đó: V = V1 ẩ V2 E = E1 ẩ E2 Thì G = là đồ thị có 2 thành phần liên thông G1, G2. A B F C E D Hình 2.4 Ví dụ như đồ thị trong hình 2.4 có ba thành phần liên thông sau: G1 = với V1= {A,B,C} và E1 = {AB, AC, CB} G2 = với V2= {D, E} và E2 = {DE} G3 = với V3= {F} và U3 = ặ Cho đồ thị có hướng G = - G được gọi là đồ thị liên thông yếu nếu đồ thị vô hướng tương ứng với nó là liên thông - G là liên thông một chiều nếu với hai đỉnh u,v khác nhau bất kỳ của G luôn có đường đi u - v hoặc đường đi v - u. A B C D A B C D A B C D - G là liên thông mạnh (liên thông 2 chiều) nếu hai đỉnh u,v khác nhau bất kỳ của G đều có đường đi u - v và đường đi v - u. H1 H2 H3 Hình 2.5 Trờn hình 2.5 đồ thị H1 là liên thông mạnh, giả sử cặp đỉnh (A,C) ta có chiều đi từ C tới A, và đồng thời cũng có chiều đi từ A tới C, và bất kỳ các cặp đỉnh khác cũng tương tự như vậy. H2 là liên thông một chiều vì xét cặp đỉnh (A,D) có chiều đi từ D tới A nhưng không có chiều đi từ A tới D. H3 là liên thông yếu vì tồn tại cặp đỉnh (B,C) không có chiều đi B - C cũng không có chiều đi C - B, nhưng đồ thị vô hướng tương ứng là liên thông 6. Đường đi Euler và chu trinh Euler Đường đi Euler: Một đường đi trong đồ thị được gọi là đường đi euler nếu nú đi qua tất cả cỏc cạnh hoặc cung của đồ thị với mỗi cạnh hoặc cung đi qua đỳng một lần. Chu trỡnh Euler: Một chu trỡnh được gọi là chu trỡnh Euler nếu nú là một đường đi Euler Đường đi Euler là một đường đi đơn chứa tất cả cỏc cạnh hoặc cung của đồ thị. Cũn chu trỡnh Euler là một chu trinh đơn chứa tất cả cỏc cạnh hoặc cung của đồ thị. Một đồ thị cú đường đi Euler thỡ được gọi là đồ thị nửa Euler.Cũn đồ thị cú chu trỡnh Euler thỡ gọi là đồ thị Euler. B C B A C D E A E D F Hỡnh 2.6 Hinh 2.7 Chọn đỉnh khởi đầu là A ,trờn hỡnh 2.6 cú chu trỡnh Euler là: A->B ->C->A->F->C->D->E->A - Chọn đỉnh đầu là A , hỡnh 2.7 cú chu trỡnh nửa Euler là: A->E->D->A->B->D->C->B Định lý 1: a, Điều kiện cần và đủ để một đồ thị vụ hướng liờn thụng cú chu trỡnh Euler là mọi đỉnh của nú đều cú bậc chẵn. b, Điều kiện cần và đủ để đồ thị cú hướng liờn thụng mạnh cú chu trỡnh Euler là tại mọi đỉnh của nú thỡ bậc vào bằng bậc ra cú nghĩa là: Deg -(v)=Deg +(v) vV; Định lý 2 Cần và đủ để 1 đồ thị cú đường đi Euler nhưng khụng cú chu trỡnh Euler là đồ thị đú cú đỳng 2 đỉnh bậc lẻ. 7. Bài toỏn đường đi ngắn nhất Trong lý thuyết đồ thị, bài toỏn đường đi ngắn nhất nguồn đơn là bài toỏn tỡm một đường đi giữa hai đỉnh sao cho tổng cỏc trọng số của cỏc cạnh tạo nờn đường đi đú là nhỏ nhất. Định nghĩa một cỏch hỡnh thức, cho trước một đồ thị cú trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trong số cú giỏ trị thực f : E → R), cho trước một đỉnh v thuộc V, tỡm một đường đi P từ v tới mỗi đỉnh v' thuộc V sao cho: là nhỏ nhất trong tất cả cỏc đường nối từ v tới v' . Bài toỏn đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toỏn tương tự, trong đú ta phải tỡm cỏc đường đi ngắn nhất cho mọi cặp đỉnh v và v' . Thuật toỏn Dijkstra, mang tờn của nhà khoa học mỏy tớnh người Hà Lan Edsger Dijkstra, là một thuật toỏn giải quyết bài toỏn đường đi ngắn nhất nguồn đơn trong một đồ thị cú hướng khụng cú cạnh mang trọng số õm. Bài toỏn: Cho một đồ thị cú hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tớnh toỏn được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị. Vớ dụ: Chỳng ta dựng cỏc đỉnh của đồ thị để mụ hỡnh cỏc thành phố và cỏc cạnh để mụ hỡnh cỏc đường nối giữa chỳng. Khi đú trọng số cỏc cạnh cú thể xem như độ dài của cỏc con đường (và do đú là khụng õm). Chỳng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toỏn Dijkstra sẽ giỳp chỉ ra đường đi ngắn nhất chỳng ta cú thể đi. Trọng số khụng õm của cỏc cạnh của đồ thị mang tớnh tổng quỏt hơn khoảng cỏch hỡnh học giữa hai đỉnh đầu mỳt của chỳng. Vớ dụ: Với 3 đỉnh A, B, C đường đi A-B-C cú thể ngắn hơn so với đường đi trực tiếp A-C. Thuật toỏn Dijkstra cú thể mụ tả như sau: - Ta quản lý một tập hợp động S. Ban đầu S={s}. - Với mỗi đỉnh v, chỳng ta quản lý một nhón d[v] là độ dài bộ nhất trong cỏc đường đi từ nguồn s đến một đỉnh u nào đú thuộc S, rồi đi theo cạnh nối u-v. - Trong cỏc đỉnh ngoài S, chỳng ta chọn đỉnh u cú nhón d[u] bộ nhất, bổ sung vào tập S. Tập S được mở rộng thờm một đỉnh, khi đú chỳng ta cần cập nhật lại cỏc nhón d cho phự hợp với định nghĩa. - Thuật toỏn kết thỳc khi toàn bộ cỏc đỉnh đó nằm trong tập S, hoặc nếu chỉ cần tỡm đường đi ngắn nhất đến một đỉnh đớch t, thỡ chỳng ta dừng lại khi đỉnh t được bổ sung vào tập S. Tớnh chất khụng õm của trọng số cỏc cạnh liờn quan chặt chẽ đến tớnh đỳng đắn của thuật toỏn. Khi chứng minh tớnh đỳng đắn của thuật toỏn, chỳng ta phải dựng đến tớnh chất này. Phần 2: Cài Đặt Thuật Toỏn I. Kiểm tra tính liên thông: Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh của nó đều được nối với nhau bởi một đường. Một đồ thị con liên thông của đồ thị mà nó không được chứa trong một đồ thị con liên thông khác, gọi là thành phần liên thông. Bài toán: Bài toán đặt ra là cho một đồ thị vô hướng G=(V,E), hãy cho biết G có bao nhiêu thành phần liên thông, và mỗi thành phần liên thông của nó gồm những đỉnh nào. Thuật toán kiểm tra tính liên thông: Xét đồ thị G(V,E): Bước 1: Lấy đỉnh bất kỳ I của G, đặt T={ I } và gọi I là đỉnh gốc. Bước 2: Đưa vào T tất cả những đỉnh j sao cho cạnh ij thuộc E ( tức cạnh ij là một cạnh của G). Bước 3: Nếu T chứa mọi đỉnh của G( nghĩa là điều kiện dừng lại ở bước 2 thoả mãn), thì đồ thị G liên thông. Bước 4: Nếu T không chứa mọi đỉnh của G thì đồ thị G không liên thông. Khi đó, T là một thành phần của liên thông. Bước 5: Lấy đỉnh v thuộc G nhưng không thuộc T, trở về bước 2. II. Tìm chu trình Euler: Định nghĩa chu trình Euler : Giả sử G là đồ thị vô hướng. Một chu trình w trong đồ thị G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh của G và đi qua mỗi cạnh đúng một lần. 1. Nêu bài toán : Cho đồ thị G=. Hãy tìm chu trình Euler của đồ thị G nếu có. 2. Nêu thuật toán : Cho đơn đồ thị G với ma trận kề a[i,j]. Bước 1: Kiểm tra xem bậc của mỗi đỉnh có là số chẵn hay không, tức là kiểm tra xem tổng các phần tử trên mỗi dòng ( hoặc mỗi cột) có là số chẵn hay không? Bước 2: Nếu tồn tại một đỉnh có bậc lẻ (hoặc một dòng hay một cột của ma trân có tổng các phần tử của nó là lẻ), ta kết luận rằng đồ thị không có chu trình Euler. Bước 3: Nếu mọi đỉnh của đồ thị đều có bậc chẵn thì đồ thị có chu trình Euler. Bước 4: Khi đó, xuất phát từ một đỉnh bất kỳ, ta đi một cách ngẫu nhiên theo các cạnh của đồ thị theo quy tắc mỗi cạnh của đồ thị chỉ đi có một lần. Khi dừng lại ta được một chu trình. Bước 5: Kiểm tra xem có còn đỉnh nào có cạnh liên thuộc với nó mà chưa được đi qua hay không? Nếu có, ta lấy đỉnh đó làm xuất phát (đỉnh dớnh), đi theo chu trình cũ, hoàn tất chu trình tại đỉnh này rồi đi theo cạnh chưa được đi qua. Trở về bước4. Bước 6: Nếu không có đỉnh nào còn có cạnh liên thuộc với nó mà chưa được đi qua, thỡ ta ghộp chu trỡnh với chu trỡnh con tại đỉnh dớnh và coi chu trỡnh mới thu được bằng chu trỡnh. Ta kết luận chu trỡnh tim được là chu trỡnh Euler. 3.Vớ dụ minh họa Hinh 3:Chu trình Euler 6 1 2 4 3 5 Ma trận kề tương ứng: 4. Cài đặt thuật toỏn uses crt; Type imatr=array[1..20,1..20] of byte; bvtor=array[-1..20] of byte; var a,c, w1,w:imatr; l:byte; ct,ctc:bvtor; queue,chuaxet,truoc:array[1..20] of byte; i,j,n,solt,k,s,t:integer; ch:char; {********************************************************} procedure nhapsolieu; begin write('Cho so dinh cua do thi:');readln(n); writeln('Nhap so lieu ma tran ke:'); for i:=1 to n do begin for j:=i+1 to n do begin write('a[',i,',',j,']='); readln(a[i,j]); a[j,i]:=a[i,j]; end; a[i,i]:=0; writeln; end; end; {*********************************************************} procedure doctep; var f:text; fn:string; begin write('Cho ten file du lieu:');readln(fn); assign(F,fn); reset(F); readln(f,n); writeln('Nhap so lieu ma tran ke:'); for i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end; {*******************************************************} procedure Insolieu; begin writeln('Ma tran ke:'); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3); writeln; end; end; {******************** chu trinh euler ********************} Function kiemtra(a:imatr;n:byte):boolean; Var i,j,k:byte; b:boolean; Begin b:=true; for i:=1 to n do begin k:=0; for j:=1 to n do k:=k+a[i,j]; b:=b and (k mod 2=0); end; kiemtra:=b; End; {***********************Lap chu trinh-**********************} Procedure lapchtr(var w:imatr;var ct:bvtor;l:byte); Var i,j,k,a:byte; Begin k:=0; i:=l; ct[k]:=i; repeat j:=1; while (w[i,j]=0) and (j<=n) do j:=j+1; if j<=n then begin w[i,j]:=w[i,j]-1; w[j,i]:=w[i,j]; k:=k+1; ct[k]:=j; i:=j; end; until i=l; ct[-1]:=k; End; {*************Kiem tra het canh*****************} Function Hetcanh(a:imatr;n:byte):boolean; Var i,j,k:byte; b:boolean; Begin b:=true; for i:=1 to n do for j:=1 to i-1 do b:=b and (a[i,j]=0); Hetcanh:=b; End; {**********************Tim Diem Dinh**************} Function diemdinh(w1,w:imatr;n:byte):byte; Var i,j,t1,t2:byte; Begin i:=0; t1:=0; t2:=0; repeat i:=i+1; for j:=1 to n do begin t1:=t1+w1[i,j]; t2:=t2+w[i,j]; end until (t20) and (t2<t1); diemdinh:=i; End; {*******************Ghep chu trinh*****************} Procedure ghep(var ct:bvtor; ctc:bvtor;i:byte); Var j,k:byte; Begin k:=1; while ct[k]i do inc(k); for j:=ct[-1] downto k+1 do ct[ctc[-1]+j]:=ct[j]; for j:=1 to ctc[-1] do ct[j+k]:=ctc[j]; ct[-1]:=ct[-1]+ctc[-1]; End; {*****************Euler**********************} procedure eulerr ; begin insolieu; w1:=a; c:=a; Write('Chon dinh dau: '); readln(l);writeln; if (kiemtra(a,n)=false) then begin writeln('Khong co chu trinh'); write('An enter de tiep tuc..');readln; end else begin lapchtr(a,ct,l); while not Hetcanh(a,n) do begin i:=diemdinh(w1,a,n); lapchtr(a,ctc,i); ghep(ct,ctc,i); end; a:=c; writeln('Duong di cua chu trinh la:'); for i:=0 to ct[-1] do write(ct[i],'<-'); readln; end; end; {***************************************************} procedure ketqualienthong; begin insolieu; if solt=1 then begin writeln('Do thi la lien thong'); eulerr; end else begin writeln('So thanh phan cua do thi lien thong la:',solt); for i:=1 to solt do begin writeln('Thanh phan lien thong thu ',i,' gom cac dinh:'); for j:= 1 to n do if chuaxet[j]=i then write(j:3); writeln; end; end; write('Nhan enter de tiep tuc...');readln; end; {***************************************************} procedure DFS(v:integer); {Tim kiem theo chieu sau bat dau tu dinh v} var u:integer; begin chuaxet[v]:=solt; for u:=1 to n do if (a[v,u]0) and (chuaxet[u]=0) then begin truoc[u]:=v; DFS(u); end; end; {***************************************************} procedure lienthong; begin {Khoi tao so lieu} for j:=1 to n do chuaxet[j]:=0;solt:=0; for i:=1 to n do if chuaxet[i]=0 then begin solt:=solt+1; DFS(i);{ tim kiem theo chieu sau} end; ketqualienthong; end; {***************************************************} procedure ketquaduongdi; begin if truoc[t]=0 then writeln('Khong co duong di tu ',s,' den ',t) else begin writeln('Duong di tu ',s,' den ',t,' la:'); j:=t; write(t,'<=='); while truoc[j]s do begin write(truoc[j],'<=='); j:=truoc[j]; end; writeln(s); end; write('An enter de tiep tuc..');readln; end; {***************************************************} procedure duongdi; begin insolieu; write('Tim duong di tu dinh:');readln(s); write(' den dinh:');readln(T); for j:= 1 to n do begin truoc[j]:=0; chuaxet[j]:=0; end; solt:=1; DFS(s); ketquaduongdi; end; {***************************************************} procedure menu; begin clrscr; writeln('TIM DUONG DI VA KIEM TRA TINH LIEN THONG'); WRITELN('CUA DO THI THEO THUAT TOAN TIM KIEM TREN DO THI'); writeln('Moi ban chon chuc nang:'); writeln; writeln('1.Nhap so lieu tu ban phim'); writeln('2.Nhap so lieu tu tep'); writeln('3.Kiem tra tinh lien thong'); writeln('4.Tim duog di giua hai dinh'); writeln('5.Thoat'); ch:=readkey; writeln(ch); end; {--------------Chuong trinh chinh----------------------------------} begin repeat menu; case ch of '1':Nhapsolieu; '2':doctep; '3':Lienthong; '4':duongdi; end; until (ch='5') or (upcase(ch)='Q'); end. II. Tìm đường đi ngắn nhất giữa hai đỉnh trong đơn đồ thị 1. Bài toán: Tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số trong trường hợp vô hướng và có hướng. 2.Thuật toán Dijkstra: Procedure Dijkstra (G:đơn đồ thị liên thông có trọng số dương) {G có các đỉnh a=v0, v1,…, vn=z và trọng số w(vi,vj). Với w(vi,vj)= ∞ nếu {vi,vj} không là một cạnh trong G} For i:=1 to n do L(vi):=∞; L(a):=0; S:=rỗng; { Ban đầu các nhân được khởi tạo sao cho nhân của a=0, các đỉnh khác=∞, tập S là rỗng} while z không thuộc rỗng begin U:=đỉnh không thuộc S có nhân L(u) nhỏ nhất. S:=S U {u} For tất cả các đỉnh v không thuộc S IF L(u) + w(u,v) < L(v) then L(v):=L(u)+w(u,v) {Thêm vào S đỉnh có nhãn nhỏ nhất và sửa đổi nhãn của các đỉnh không thuộc SU End; { L(z) = độ dài đường đi ngắn nhất từ a đến z} 6 D B 3. Ví dụ minh hoạ: 0 1 2 0 0 0 1 0 3 6 5 0 A= 2 3 0 0 4 0 0 6 0 0 7 8 0 5 4 7 0 9 0 0 0 8 9 0 Hinh 4:Đồ thị vô hướng G 8 1 3 7 A F 9 2 4 C E a 4. Cài đặt thuật toán: program Duong_di; uses crt,graph; Const max=26; vocung=2*maxint*maxint; type str26=string[26]; tendinh=record l:longint; dd:str26; end; points=record x,y:integer; End; var G:array[1..max,1..max] of integer; V:array[1..max] of tendinh; n:byte; S:array[1..max] of boolean; Xp:byte; Kt:byte; { l:longint;} ch:char; p:array[1..max] of points; {**************************************************} procedure ktdh; var gd,gm:integer; begin gd:=0; Initgraph(gd,gm,''); If graphresult0 then halt(1); end; {*****************************************************} function Doc_tep(ten:string):boolean; var F:text; i,j:integer; begin assign(F,ten); reset(F); If (Ioresult0) then doc_tep:=false else begin readln(F,n); for i:=1 to n do begin for j:=1 to n do read(F,G[i,j]); readln(F); end; close(F); doc_tep:=true; end; end; {**********************************************************} function nhanmin:byte; var min:longint; tg,i:byte; begin min:=vocung; tg:=0; for i:=1 to n do if not S[i] then if (min>v[i].l) then begin min:=V[i].l; tg:=i; end; nhanmin:=tg; end; {******************************************************} procedure DIJKSTRA; var i:integer; dinhmin:byte; begin fillchar(S,sizeof(s),false); for i:=1 to n do begin V[i].l:=vocung; V[i].dd:=''; end; V[xp].l:=0; V[xp].dd:=chr(Xp+96); dinhmin:=Xp; while dinhmin0 do begin S[dinhmin]:=true; for i:=1 to n do if not S[i] then if (G[Dinhmin,i]0) then if (V[dinhmin].l+G[dinhmin,i]<V[i].l) then begin V[i].l:=V[dinhmin].l+G[dinhmin,i]; V[i].dd:=V[dinhmin].dd+chr(i+96); end; dinhmin:=nhanmin; end; end; {************************************************************} procedure Drawnline(a,b:points); var tgx,tgy,dx,dy:real; Kcmax,i:integer; begin tgx:=A.x; tgy:=A.y; if abs(B.x-A.x)>abs(B.y-A.y) then begin if b.x-a.x>=0 then dx:=1 else dx:=-1; KCmax:=abs(B.x-A.x); dy:=(B.y-A.y)/KcMax; end else begin if b.y-a.y>0 then dy:=1 else dy:=-1; Kcmax:=abs(B.y-A.y); dx:=(B.x-A.x)/Kcmax; end; for i:=0 to Kcmax-1 do begin tgx:=tgx+dx; tgy:=tgy+dy; delay(80); putpixel(round(tgx),round(tgy),6); end; end; {***********************************************************} procedure drawpoints(number:byte); var i:real; j:integer; begin i:=0; j:=1; setcolor(5); repeat p[j].x:=320-round(210*sin(i)); { lay toa do cua x,y} p[j].y:=240-round(210*cos(i)); putpixel(p[j].x,p[j].y,4); circle(p[j].x,p[j].y,1); { ve diem} circle(p[j].x,p[j].y,2); i:=i+2*pi/number; j:=j+1; until j>number; setcolor(10); end; {*********************************************************} procedure drawpointname(number:byte); var i:real; j,x,y:integer; begin x:=0; y:=0; i:=0; j:=1; settextstyle(2,0,4); setcolor(12); repeat x:=320-round(220*sin(i)); { xac dinh toa do} y:=240-round(220*cos(i)); outtextxy(x-3,y-6,chr(j+64)); { viet chu tuong ung voi dinh} i:=i+2*pi/number; j:=j+1; until j>number; setcolor(10); end; {***********************************************************} procedure drawngraph; { ve canh cua do thi} var i,j:integer; begin for i:=1 to n do for j:=1 to n do if G[i,j]>0 then line(P[i].x,p[i].y,p[j].x,p[j].y); end; {********************************************************} procedure introngso; var i,j:integer; st,st1:string; begin settextstyle(2,0,4); setcolor(3); for i:=1 to n do for j:=1 to n do if G[i,j]>0 then begin str(G[i,j],st); { doi ten dinh 1,2 thanh "1","2"} outtextxy((P[i].x+P[j].x) div 2+5,(P[i].y+p[j].y) div 2+5,st);{ viet vao khoag giua hai dinh} end else if ( G[i,j]<0) then begin st1:='-'; str(G[i,j],st); { doi ten dinh 1,2 thanh "1","2"} outtextxy((P[i].x+P[j].x) div 2,(P[i].y+p[j].y) div 2,st1);{ viet vao khoag giua hai dinh} { outtextxy((P[i].x+P[j].x) div 2+5,(P[i].y+p[j].y) div 2+5,st);{ viet vao khoag giua hai dinh} end; end; {**********************************************************} procedure drawduongdi(k:integer); var i,lk:integer; begin lk:=length(V[k].dd); for i:=1 to lk-1 do begin drawnline(P[ord(V[k].dd[i])-96],P[ord(V[k].DD[i+1])-96]); {goi ham ve duong thang} { chuyen duong di tu xau sang so vi du A-> 97} end; end; {*********************************************************} var i:integer; st:string[10]; begin ktdh; cleardevice; setcolor(6); write('Doc tu tep'); doc_tep('dothi.bat'); if n>0 then begin repeat cleardevice; settextstyle(2,0,6); setcolor(12); outtextxy(10,20,'BAI TOAN TIM DUONG DI NGAN NHAT '); setcolor(13); settextstyle(2,0,4); outtextxy(10,50,'Nhap dinh xuat phat:'); ch:=upcase(readkey); outtextxy(10,50,'Nhap dinh xuat phat:'+ch); xp:=ord(ch)-64; { ord chuyen ky tu A thanh so 65} outtextxy(10,60,'Nhap dinh ket thuc:'); ch:=upcase(readkey); outtextxy(10,60,'Nhap dinh ket thuc:'+ch); kt:=ord(ch)-64; drawpoints(N); drawngraph;{ ve do thi ban dau} introngso; drawpointname(N);{ ve ten dinh A,B,C,,,F} DIJKSTRA; setcolor(4); if S[kt] then begin drawduongdi(KT);{ ve duog di ngan nhat} str(V[kt].l,st);{ chuyen so thanh xau} setcolor(13); settextstyle(2,0,4); outtextxy(10,80,'Do dai duong di ngan nhat la:');{ hien thi van ban} outtextxy(190,80,st); end else outtextxy(10,80, 'Khong co duong di'); outtextxy(10,90,'Ban co muon tiep tuc nua khong(C/K)'); ch:=readkey; until upcase(ch)'C'; end; setcolor(8); readln; end. Tài liệu tham khảo Toỏn rời rạc _ Nguyễn Đức Nghĩa , Nguyễn Tụ Thành Nhà xuất bản Đại học Quốc gia Hà Nội-2001 Bài giảng toỏn rời rạc – TS. Nguyễn Trung Hũa Mục lục Lời Mở Đầu 1 Phần I- Cỏc khỏi niệm cơ bản về lý thuyết đồ thị 2 I- Định nghĩa 2 II – Cỏc khỏi niệm 3 1. Cỏc khỏi niệm cơ bản 3 2. Cỏch biểu diễn đồ thị trong mỏy tớnh 5 III- Đường đi trong đồ thị 9 1. Đường đi 9 2. Chu trỡnh 9 3. Đường đi và chu trỡnh của đồ thị vụ hướng 9 4. Đường đi và chu trỡnh của đồ thị cú hướng 10 5. Đồ thị liờn thụng 11 6. Đường đi Euler và chu trỡnh Euler 12 7. Bài toỏn đường đi ngắn nhất 13 Phần 2 Cài đặt thuật toỏn 15 I- Kiểm tra tớnh liờn thụng 15 1. Bài toỏn 15 2.Thuật toỏn kiểm tra tớnh liờn thụn 15 II- Tỡm chu trỡnh Euler 15 1. Nờu bài toỏn 15 2. Nờu thuật toỏn 15 3. Vớ dụ minh họa 16 4. Cài đặt thuật toỏn 16 III- Tỡm đường đi ngắn nhất giữa hai đỉnh trong đơn đồ thị 25 1. Bài toỏn 25 2. Thuật toỏn Dijkstra 26 3. Vớ dụ minh họa 27 4. Cài đặt thuật toỏn 27