SÁCH - Giáo trình Lý thuyết đồ thị (Đặng Trường Sơn & Lê Văn Vinh) Full
14 thg 7, 2025 | 16:18

SÁCH - Giáo trình Lý thuyết đồ thị (Đặng Trường Sơn & Lê Văn Vinh) Full



Nội dung giáo trình gồm có 8 chƣơng,  bao quát hầu hết các vấn đề cốt lõi của môn học. Giáo trình không đi sâu vào các vấn đề lý thuyết mà tập trung vào các giải thuật cũng nhƣ tính ứng dụng của môn học. Cuối mỗi chƣơng đều có phần bài tập để sinh viên có thể tự kiểm tra kiến thức của  mình.  Các  thuật  toán  trong  giáo  trình  hầu  hết  đƣợc  trình  bà y  dƣới dạng mã giả. Phần phụ lục có mã nguồn của một số thuật toán.



NỘI DUNG:


Chƣơng I: CÁC KHÁI NIỆM CƠ BẢN  ................................................  9

1.1. MỞ ĐẦU  ............................................................................................  9

1.2. ĐỊNH NGHĨA VÀ PHÂN LOẠI ĐỒ THỊ  .......................................  10

1.2.1. Định nghĩa đồ thị  ....................................................................  10

1.2.2. Phân loại đồ thị  .......................................................................  10

1.3. CÁC THUẬT NGỮ CƠ BẢN  ..........................................................  14

1.4. ĐƢỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG  ......................  16

1.4.1. Đƣờng đi  .................................................................................  16

1.4.2. Chu trình  .................................................................................  17

1.4.3. Đƣờng đi và chu trình trong đồ thị có hƣớng  .........................  17

1.4.4. Đồ thị liên thông  .....................................................................  18

1.5. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT  .............................................  20

1.5.1. Đồ thị đầy đủ  ..........................................................................  20

1.5.2. Đồ thị vòng, đồ thị bánh xe  ....................................................  20

1.5.3. Đồ thị siêu khối  ......................................................................  21

1.5.4. Đồ thị hai phía  ........................................................................  22

1.5.5. Đồ thị phẳng  ...........................................................................  25

1.6. BÀI TẬP CHƢƠNG I  ..................................................................  27

Chƣơng II: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH  .......................  29

2.1. MA TRẬN KỀ, MA TRẬN TRỌNG SỐ .......................................  29

2.1.1. Ma trận kề  ...............................................................................  29

2.1.2. Ma trận trọng số .....................................................................  31

2.1.3. Cài đặt  .....................................................................................  31

2.2. DANH SÁCH CẠNH (CUNG)  ........................................................  33 

6

2.3. DANH SÁCH KỀ  .............................................................................  34

2.4. MA TRẬN LIÊN THUỘC  ...............................................................  38

2.5. SỰ ĐẲNG CẤU CỦA ĐỒ THỊ  .......................................................  38

2.5.1. Định nghĩa  .............................................................................  38

2.5.2. Tính bất biến  ...........................................................................  39

2.6. BÀI TẬP CHƢƠNG II  .....................................................................  39

Chƣơng III: DUYỆT ĐỒ THỊ  ..............................................................  43

3.1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU ............................................  43

3.1.1. Phƣơng pháp duyệt  .................................................................  43

3.1.2. Cài đặt thuật toán  ....................................................................  44

3.2. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG  .........................................  46

3.2.1. Phƣơng pháp duyệt  .................................................................  46

3.2.2. Cài đặt thuật toán  ....................................................................  46

3.3. TÌM ĐƢỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG ...............  50

3.3.1. Bài toán tìm đƣờng đi  ............................................................  50

3.3.2. Bài toán kiểm tra tính liên thông  ............................................  52

3.4. BÀI TẬP CHƢƠNG III  ....................................................................  54

Chƣơng IV: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON  .................  57

4.1. ĐỒ THỊ EULER  ...............................................................................  57

4.1.1. Định nghĩa  ..............................................................................  57

4.1.2. Định lý Euler  ..........................................................................  57

4.1.3. Giải thuật xây dựng chu trình Euler  .......................................  59

4.2. ĐỒ THỊ HAMILTON  .......................................................................  62

4.2.1. Định nghĩa  ..............................................................................  62

4.2.2. Định lý Dirac  ..........................................................................  63

4.2.3. Giải thuật xây dựng chu trình Hamilton  .................................  63

4.3. BÀI TẬP CHƢƠNG IV  ...................................................................  65 

7

Chƣơng V: CÂY.....................................................................................  67

5.1. ĐỊNH NGHĨA VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY  .........  67

5.2. CÂY KHUNG CỦA ĐỒ THỊ  ...........................................................  69

5.2.1. Định nghĩa  ..............................................................................  69

5.2.2. Thuật toán xây dựng cây khung  .............................................  70

5.3. BÀI TOÁN CÂY KHUNG NHỎ NHẤT  .........................................  73

5.3.1. Thuật toán Kruskal  .................................................................  74

5.3.2. Thuật toán Prim  ......................................................................  77

5.4. CÂY CÓ GỐC  ..................................................................................  79

5.4.1. Các định nghĩa  ........................................................................  79

5.4.2. Cây nhị phân tìm kiếm  ...........................................................  81

5.4.3. Cây quyết định  ........................................................................  83

5.4.4. Các phƣơng pháp duyệt cây  ...................................................  83

5.5. BÀI TẬP CHƢƠNG V  .....................................................................  86

Chƣơng VI: TÔ MÀU ĐỒ THỊ  ............................................................  89

6.1. MỞ ĐẦU  ..........................................................................................  89

6.1.1. Định nghĩa 1  ...........................................................................  89

6.1.2. Định nghĩa 2  ...........................................................................  90

6.2. ĐỊNH LÝ BỐN MÀU  ......................................................................  90

6.3. ĐỒ THỊ 2 MÀU  ................................................................................  90

6.4. THUẬT TOÁN SEQUENTIALCOLOR  .........................................  91

6.5. NHỮNG ỨNG DỤNG CỦA BÀI TOÁN TÔ MÀU ĐỒ THỊ  .........  93

6.5.1. Bài toán lập lịch thi ................................................................  94

6.5.2. Bài toán phân chia tần số  ........................................................  95

6.6. BÀI TẬP CHƢƠNG VI  ...................................................................  95

Chƣơng VII: ĐƢỜNG ĐI NGẮN NHẤT  ............................................  97

7.1. ĐỊNH NGHĨA ..................................................................................  97

7.2. THUẬT TOÁN DIJKSTRA  .............................................................  97 

8

7.2.1. Ý tƣởng thuật toán  ..................................................................  97

7.2.2. Cài đặt thuật toán  ....................................................................  98

7.3. THUẬT TOÁN FORD-BELLMAN  ..............................................  100

7.3.1. Ý tƣởng thuật toán  ................................................................  101

7.3.2. Cài đặt thuật toán  ..................................................................  101

7.4. THUẬT TOÁN FLOYD  ................................................................  103

7.4.1. Ý tƣởng thuật toán  ................................................................  103

7.4.2. Cài đặt thuật toán  ..................................................................  103

7.5. BÀI TẬP CHƢƠNG VII  ................................................................  106

Chƣơng VIII: LUỒNG TRONG MẠNG...........................................  110

8.1. MỘT SỐ KHÁI NIỆM CƠ BẢN  ..................................................  110

8.1.1. Mạng  .....................................................................................  110

8.1.2. Luồng trong mạng  ................................................................  111

8.2. ĐỊNH LÝ FORD-FULKERSON ...................................................  113

8.3. THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI TRONG MẠNG  ..........  117

8.4. BÀI TẬP CHƢƠNG VIII  ...............................................................  122

PHỤ LỤC  ..............................................................................................  123

HƢỚNG DẪN VÀ ĐÁP ÁN MỘT SỐ BÀI TẬP  ................................  139

TÀI LIỆU THAM KHẢO  



ĐẶT MUA SÁCH LÝ THUYẾT ĐỒ THỊ NGAY TẠI ĐÂY > > >










LINK DOWNLOAD - BẢN 2012 (TÀI LIỆU VIP MEMBER)



Nội dung giáo trình gồm có 8 chƣơng,  bao quát hầu hết các vấn đề cốt lõi của môn học. Giáo trình không đi sâu vào các vấn đề lý thuyết mà tập trung vào các giải thuật cũng nhƣ tính ứng dụng của môn học. Cuối mỗi chƣơng đều có phần bài tập để sinh viên có thể tự kiểm tra kiến thức của  mình.  Các  thuật  toán  trong  giáo  trình  hầu  hết  đƣợc  trình  bà y  dƣới dạng mã giả. Phần phụ lục có mã nguồn của một số thuật toán.



NỘI DUNG:


Chƣơng I: CÁC KHÁI NIỆM CƠ BẢN  ................................................  9

1.1. MỞ ĐẦU  ............................................................................................  9

1.2. ĐỊNH NGHĨA VÀ PHÂN LOẠI ĐỒ THỊ  .......................................  10

1.2.1. Định nghĩa đồ thị  ....................................................................  10

1.2.2. Phân loại đồ thị  .......................................................................  10

1.3. CÁC THUẬT NGỮ CƠ BẢN  ..........................................................  14

1.4. ĐƢỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG  ......................  16

1.4.1. Đƣờng đi  .................................................................................  16

1.4.2. Chu trình  .................................................................................  17

1.4.3. Đƣờng đi và chu trình trong đồ thị có hƣớng  .........................  17

1.4.4. Đồ thị liên thông  .....................................................................  18

1.5. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT  .............................................  20

1.5.1. Đồ thị đầy đủ  ..........................................................................  20

1.5.2. Đồ thị vòng, đồ thị bánh xe  ....................................................  20

1.5.3. Đồ thị siêu khối  ......................................................................  21

1.5.4. Đồ thị hai phía  ........................................................................  22

1.5.5. Đồ thị phẳng  ...........................................................................  25

1.6. BÀI TẬP CHƢƠNG I  ..................................................................  27

Chƣơng II: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH  .......................  29

2.1. MA TRẬN KỀ, MA TRẬN TRỌNG SỐ .......................................  29

2.1.1. Ma trận kề  ...............................................................................  29

2.1.2. Ma trận trọng số .....................................................................  31

2.1.3. Cài đặt  .....................................................................................  31

2.2. DANH SÁCH CẠNH (CUNG)  ........................................................  33 

6

2.3. DANH SÁCH KỀ  .............................................................................  34

2.4. MA TRẬN LIÊN THUỘC  ...............................................................  38

2.5. SỰ ĐẲNG CẤU CỦA ĐỒ THỊ  .......................................................  38

2.5.1. Định nghĩa  .............................................................................  38

2.5.2. Tính bất biến  ...........................................................................  39

2.6. BÀI TẬP CHƢƠNG II  .....................................................................  39

Chƣơng III: DUYỆT ĐỒ THỊ  ..............................................................  43

3.1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU ............................................  43

3.1.1. Phƣơng pháp duyệt  .................................................................  43

3.1.2. Cài đặt thuật toán  ....................................................................  44

3.2. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG  .........................................  46

3.2.1. Phƣơng pháp duyệt  .................................................................  46

3.2.2. Cài đặt thuật toán  ....................................................................  46

3.3. TÌM ĐƢỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG ...............  50

3.3.1. Bài toán tìm đƣờng đi  ............................................................  50

3.3.2. Bài toán kiểm tra tính liên thông  ............................................  52

3.4. BÀI TẬP CHƢƠNG III  ....................................................................  54

Chƣơng IV: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON  .................  57

4.1. ĐỒ THỊ EULER  ...............................................................................  57

4.1.1. Định nghĩa  ..............................................................................  57

4.1.2. Định lý Euler  ..........................................................................  57

4.1.3. Giải thuật xây dựng chu trình Euler  .......................................  59

4.2. ĐỒ THỊ HAMILTON  .......................................................................  62

4.2.1. Định nghĩa  ..............................................................................  62

4.2.2. Định lý Dirac  ..........................................................................  63

4.2.3. Giải thuật xây dựng chu trình Hamilton  .................................  63

4.3. BÀI TẬP CHƢƠNG IV  ...................................................................  65 

7

Chƣơng V: CÂY.....................................................................................  67

5.1. ĐỊNH NGHĨA VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY  .........  67

5.2. CÂY KHUNG CỦA ĐỒ THỊ  ...........................................................  69

5.2.1. Định nghĩa  ..............................................................................  69

5.2.2. Thuật toán xây dựng cây khung  .............................................  70

5.3. BÀI TOÁN CÂY KHUNG NHỎ NHẤT  .........................................  73

5.3.1. Thuật toán Kruskal  .................................................................  74

5.3.2. Thuật toán Prim  ......................................................................  77

5.4. CÂY CÓ GỐC  ..................................................................................  79

5.4.1. Các định nghĩa  ........................................................................  79

5.4.2. Cây nhị phân tìm kiếm  ...........................................................  81

5.4.3. Cây quyết định  ........................................................................  83

5.4.4. Các phƣơng pháp duyệt cây  ...................................................  83

5.5. BÀI TẬP CHƢƠNG V  .....................................................................  86

Chƣơng VI: TÔ MÀU ĐỒ THỊ  ............................................................  89

6.1. MỞ ĐẦU  ..........................................................................................  89

6.1.1. Định nghĩa 1  ...........................................................................  89

6.1.2. Định nghĩa 2  ...........................................................................  90

6.2. ĐỊNH LÝ BỐN MÀU  ......................................................................  90

6.3. ĐỒ THỊ 2 MÀU  ................................................................................  90

6.4. THUẬT TOÁN SEQUENTIALCOLOR  .........................................  91

6.5. NHỮNG ỨNG DỤNG CỦA BÀI TOÁN TÔ MÀU ĐỒ THỊ  .........  93

6.5.1. Bài toán lập lịch thi ................................................................  94

6.5.2. Bài toán phân chia tần số  ........................................................  95

6.6. BÀI TẬP CHƢƠNG VI  ...................................................................  95

Chƣơng VII: ĐƢỜNG ĐI NGẮN NHẤT  ............................................  97

7.1. ĐỊNH NGHĨA ..................................................................................  97

7.2. THUẬT TOÁN DIJKSTRA  .............................................................  97 

8

7.2.1. Ý tƣởng thuật toán  ..................................................................  97

7.2.2. Cài đặt thuật toán  ....................................................................  98

7.3. THUẬT TOÁN FORD-BELLMAN  ..............................................  100

7.3.1. Ý tƣởng thuật toán  ................................................................  101

7.3.2. Cài đặt thuật toán  ..................................................................  101

7.4. THUẬT TOÁN FLOYD  ................................................................  103

7.4.1. Ý tƣởng thuật toán  ................................................................  103

7.4.2. Cài đặt thuật toán  ..................................................................  103

7.5. BÀI TẬP CHƢƠNG VII  ................................................................  106

Chƣơng VIII: LUỒNG TRONG MẠNG...........................................  110

8.1. MỘT SỐ KHÁI NIỆM CƠ BẢN  ..................................................  110

8.1.1. Mạng  .....................................................................................  110

8.1.2. Luồng trong mạng  ................................................................  111

8.2. ĐỊNH LÝ FORD-FULKERSON ...................................................  113

8.3. THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI TRONG MẠNG  ..........  117

8.4. BÀI TẬP CHƢƠNG VIII  ...............................................................  122

PHỤ LỤC  ..............................................................................................  123

HƢỚNG DẪN VÀ ĐÁP ÁN MỘT SỐ BÀI TẬP  ................................  139

TÀI LIỆU THAM KHẢO  



ĐẶT MUA SÁCH LÝ THUYẾT ĐỒ THỊ NGAY TẠI ĐÂY > > >










LINK DOWNLOAD - BẢN 2012 (TÀI LIỆU VIP MEMBER)

M_tả
M_tả

Chuyên mục:

Không có nhận xét nào: