Luận văn Lý thuyết đồ thị với các bài toán phổ thông

Lời nói đầu 3

1 Đại cương về đồ thị 4

1.1 Định nghĩa đồ thị 4

1.2 Một số dạng đồ thị đặc biệt 6

1.3 Bậc của đỉnh đồ thị 8

1.3.1 Bậc của đỉnh 8

1.3.2 Nửa bậc 8

1.3.3 Một số tính chất 9

1.4 Xích, chu trình, đường, vòng 13

1.4.1 Xích, chu trình 13

1.4.2 Dường, vòng 14

1.4.3 Một số tính chất 15

1.5 Dồ thị liên thông 16

1.5.1 Định nghĩa 16

1.5.2 Tính chất 17

1.6 Số ổn định trong, số ổn định ngoài 18

1.6.1 Số ổn định trong 18

1.6.2 Số ổn định ngoài 19

1.6.3 Các thuật toán tìm số ổn định trong, số ổn định

ngoài 20

1.7 Nhân của đồ thị và ứng dụng vào trò chơi 21

1.7.1 Định nghĩa 21

1.7.2 Tính chất 22

1.7.3 Trò chơi Nim 23

1.7.4 Trò chơi bốc các vật 24

1.8 Cây và bụi 29

1.8.1 Định nghĩa 29

1.8.2 Dặc điểm của cây và bill 30