Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường ngắn nhất và ứng dụng

Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường ngắn nhất và ứng dụng nhằm trình bày về hệ thống lý thuyết đồ thị, trình bày hệ thống lý thuyết về đường đi ngắn nhất và các thuật toán tìm đường đi ngắn nhất, các ứng dụng của bài toán tìm đường ngắn nhất.
Nội dung trích xuất từ tài liệu:
Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường ngắn nhất và ứng dụng 1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG - - H TRUNG CANG BÀI TOÁN TÌM ĐƯ NG ĐI NG N NH T VÀ NG D NG CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ C P MÃ S : 60. 46. 40 TÓM T T LU N VĂN TH C SĨ KHOA H C Đà N ng - Năm 2011 2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS-TSKH Tr n Qu c Chi n Ph n bi n 1: TS. CAO VĂN NUÔI Ph n bi n 2: TS. HOÀNG QUANG TUY N Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p th c sĩ khoa h c h p t i Đ i h c Đà N ng vào ngày 17 tháng 08 năm 2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Thư vi n trư ng Đ i h c Sư ph m, Đ i h c Đà N ng. 3 M Đ U 1. Lý do ch n ñ tài: Lý thuy t ñ th là ngành khoa h c ñư c phát tri n t lâu nhưng l i có nhi u ng d ng hi n ñ i, nó là ki n th c cơ s cho nhi u ngành khoa h c k thu t khác nhau như Đi n t , Hóa h c, Ngôn ng h c, Kinh t h c, Máy tính, .... Nhi u khái ni m c a lý thuy t ñ th ñư c sinh ra t các v n ñ th c ti n như: ñư ng ñi, chu trình, t p n ñ nh, chu s , s c s , duy t ñ th , ñư ng ñi Hamilton, tâm ñ th , lu ng v n t i, ñ th ph ng, cây bao trùm, cây bi u th c, cây mã ti n t t i ưu,... vì v y lý thuy t ñ th ñã g n k t nhi u ngành khoa h c l i v i nhau. Các thu t toán ng n g n và lí thú c a lý thuy t ñ th ñã giúp chúng ta gi i quy t r t nhi u bài toán ph c t p trong th c t , trong ñó v n ñ tìm ñư ng ñi ng n nh t giúp chúng ta gi i quy t ñư c r t nhi u bài toán trong th c t . Vì v y, tôi ñã ch n ñ tài: “Bài toán tìm ñư ng ñi ng n nh t và ng d ng” ñ nghiên c u. 2. M c ñích và nhi m v nghiên c u: Trình bày h th ng lý thuy t ñ th . Trình bày h th ng lý thuy t v ñư ng ñi ng n nh t và các thu t toán tìm ñư ng ñi ng n nh t. Các ng d ng c a bài toán tìm ñư ng ñi ng n nh t. 3. Đ i tư ng và ph m vi nghiên c u: 3.1. Đ i tư ng nghiên c u: Đ i tư ng nghiên c u c a ñ tài là bài toán ñư ng ñi ng n nh t và m t s ng d ng c a nó. 4 3.2. Ph m vi nghiên c u: Các thu t toán tìm ñư ng ñi ng n nh t và m t s ng d ng c a bài toán tìm ñư ng ñi ng n nh t. 4. Phương pháp nghiên c u: Cơ b n s d ng phương pháp nghiên c u tài li u (sách, báo, các m c trên internet có liên quan ñ n ñ tài) ñ thu th p thông tin nh m phân tích, h th ng lý thuy t, các thu t toán v ñư ng ng n nh t, các ng d ng ph c v cho ñ tài. 5. C u trúc lu n văn: Ngoài ph n m ñ u, k t lu n, tài li u tham kh o, trong lu n văn gòm có ba chương như sau : Chương 1 : Đ I CƯƠNG V Đ TH Chương 2 : BÀI TOÁN ĐƯ NG ĐI NG N NH T Chương 3 : NG D NG 5 Chương 1 : Đ I CƯƠNG V Đ TH 1.1. Đ th , ñ nh, c nh: 1.2. B c, n a b c vào, n a b c ra: 1.2.1. B c : 1.2.2. N a b c: 1.2.3. Ví d : 1.2.4. B ñ b t tay ( Hand Shaking Lemma) : 1.2.5. M nh ñ 1: 1.2.6. M nh ñ 2 : 1.3. Đư ng ñi, chu trình, tính liên thông 1.3.1. Đ nh nghĩa : Cho ñ th G= (V,E) Dãy µ t ñ nh v ñ n ñ nh w là dãy các ñ nh và các c nh n i ti p nhau b t ñ u t ñ nh v và k t thúc t i ñ nh w. S c nh trên dãy µ g i là ñ dài c a dãy µ . Dãy µ t ñ nh v ñ n ñ nh w ñ dài n ñư c bi u di n như sau µ =(v, e1, v1, e2,v2,….,vn-1,en,w) trong ñó vi(i=1,…,n-1) là các ñ nh trên dãy và ei(i=1,…,n) là các c nh trên dãy liên thu c ñ nh k trư c và sau nó. Các ñ nh và các c nh trên dãy có th l p l i. Đư ng ñi t ñ nh v ñ n ñ nh w là dãy t ñ nh v ñ n ñ nh w, trong ñó các c nh không l p l i 6 Đư ng ñi sơ c p là ñư ng ñi không ñi qua m t ñ nh quá 1 l n. Chu trình là ñư ng ñi có ñ nh ñ u và ñ nh cu i trùng nhau Chu trình sơ c p là chu trình không ñi qua m t ñ nh quá 1 l n. Dãy có hư ng trong ñ th có hư ng là dãy các ñ nh và cung n i ti p nhau (e1, e2,….,en) th a mãn ñ nh cu i cùng c a cung ei là ñ nh ñ u c a cung ei+1, i=1,…,n-1. Đư ng ñi có hư ng trong ñó ñ th có hư ng là dãy có hư ng, trong ñó các cung không l p l i. Đư ng ñi có hư ng sơ c p là ñư ng ñi có hư ng không ñi qua m t ñ nh quá 1 l n. Chu trình có hư ng là ñư ng ñi có hư ng ñ nh ñ u và ñ nh cu i trùng nhau. Chu trình có hư ng sơ c p là chu trình có hư ng không ñi qua m t ñ nh quá 1 l n. Đ th vô hư ng g i là liên thông, n u m i c p ñ nh c a nó ñ u có ñư ng ñi n i chúng v i nhau. Đ th có hư ng g i là liên thông m nh, n u m i c p ñ nh c a nó ñ u có ñư ng ñi có hư ng n i chúng v i nhau. 1.3.2. Đ nh lý 1: 1.3.3. Đ nh lý 2 : 1.3.4. Tr ng ñ : 7 Tr ng ñ (có hư ng) là ñ th (có hư ng) mà m i c nh (cung) c a nó ñư c gán m t s . Tr ng ñ ñư c bi u di n b i G=(V,E,w), trong ñó V là t p các ñ nh, E là t p các c nh (cung) và w : E → R là hàm s trên E, w(e) là tr ng s c a c nh (cung) e v i m i e ∈ R . Trong tr ng ñ ñ dài tr ng s c a ñư ng ñi µ là t ng các tr ng s trên ñư ng ñi ñó. 1.3.5. Đ th con : 1.3.6. Ví d : 1.3.7. Đ nh lý 3: 1.4. Đ l ch tâm, bán kính, tâm ñ th : Cho ñ th G =(V,E,w). Ta ñ nh nghĩa kho ng cách t u ñ n v, ∀u , v ∈ V , là ñ dài ñư ng ñi ng n nh t t u ñ n v và ký hi u là d(u,v). { Đ i lư ng e(v) = max d (v, w) v ∈ V } g i là ñ l ch tâm c a ñ nh v, ∀v ∈ V . Bán kính c a ñ th G, kí hi u r(G), là ñ l ch tâm nh nh t, t c là : r (G ) = min {e(v) v ∈ V } Đ nh v ∈ V ñư c g i là ñ nh tâm n u e(v) = r (G ) . T p h p t t c các ñ nh tâm ñư c g i là tâm c a ñ th và ký hi u là C(G). 8 1.5 ...