ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN



ĐỀ CƯƠNG MÔN HỌC
LÝ THUYẾT ĐỒ THỊ
1.Thông tin về giảng viên
- Họ và tên: Đặng Huy Ruận
- Chức danh, học hàm, học vị: Giảng viên cao cấp, Giáo sư, Tiến sĩ.
- Thời gian và địa điểm làm việc : Bộ môn tin học, Tầng 5, Nhà T5, Trường ĐHKH
Tự nhiên, 334 Đường Nguyễn Trãi, Thanh Xuân, Hà Nội.
- Địa chỉ liên hệ : P15, Nhà C5, Ngõ 182 Đường Nguyễn Trãi, P.Thanh Xuân Bắc,
Q.Thanh Xuân, Hà Nội.
- Các hướng nghiên cứu chính : Độ phức tạp đoán nhận ngôn ngữ và siêu ngôn ngữ.
- Thông tin về cán bộ có thể giảng dạy môn học:
- Họ và tên: Nguyễn Hữu Điển
- Chức danh, học hàm, học vị: Giảng viên, Tiến sĩ.
- Thời gian và địa điểm làm việc : Giờ hành chính, Trung tâm tính toán hiệu nâng
cao, Tầng 1, Nhà T5, Trường ĐHKH Tự nhiên, 334 Đường Nguyễn Trãi, Thanh
Xuân, Hà Nội.
- Địa chỉ liên hệ : P404, NE 7A, Bán đảo Linh Đàm, quận Hoàng Mai, Hà Nội.
- Các hướng nghiên cứu chính : Lý thuyết tối ưu, lý thuyết điểm bất động, toán rời rạc, lập
trình ứng dụng.
2.Thông tin chung về môn học
- Tên môn học: Lý thuyết đồ thị
- Mã môn học:
- Số tín chỉ: 3
- Môn học : Bắt buộc
- Các môn học tiên quyết: Lý thuyết tập hợp, Giải tích tổ hợp, Tin học cơ sở
- Các môn học kế tiếp: Lý thuyết quy hoạch

1.3.Một số dạng đồ thị đặc biệt.
2. Bậc của đồ thị.
3. Xích, chu trình, đường, vòng.
4. Đồ thị liên thông.
5. Chu số
6. Sắc số và đồ thị tô màu.
6.1.Một số tính chất.
6.2.Thuật toán tìm sắc số.
6.3.Đồ thị tô màu.
7.Các tập đặc biệt trên đồ thị.
7.1.Các tập ổn định trong.
7.2.Các tập ổn định ngoài.

3
7.3.Nhân của đồ thị.
8.Trò chơi trên đồ thị.
8.1.Trò chơi Nim
8.2.Trò chơi tổng. Trò chơi tích.
8.3.Hàm grandy. Phương pháp hàm grandy.
9. Đồ thị Euler.
9.1.Định nghĩa.
9.2.Điều kiện cần và đủ.
9.3.Thuật toán tìm chu trình Euler.
9.4.Điều kiện cần và đủ để đồ thị có hướng là đồ thị Euler.
10. Đồ thị Hamilton
10.1.Định nghĩa.
10.2.Điều kiện tồn tại chu trình Hamilton.
11. Đường đi ngắn nhất.
11.1.Thuật toán tìm đường đi ngắn nhất.
11.2.Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số.

Nội dung
Hình thức tổ chức dạy học môn
Tổng
Lên lớp
Thực hành, thí
nghiệm, điền dã
Tự học, tự
nghiên cứu
Lý thuyết
Bài tập

Nội dung 1
2
(4)
2
Nội dung 2
1
(2)
1
Nội dung 3
2

Nội dung 8
3
3 (12)
6
Nội dung 9
2
(4)
2
Nội dung 10
2
1 (6)
3
Nội dung11
1 2
(2)
3
Nội dung 12
3

Hình thức tổ
chức dạy học
Thời gian
địa điểm
Nội dung chính
Yêu cầu
sinh viên
chuẩn bị
Ghi
chú
1 1 Lý thuyết Thứ 3, 7h-9h50
Các khái niệm cơ bản về
đồ thị 5
Tuần
Nội
dung
Hình thức tổ
chức dạy học
Thời gian
địa điểm
Nội dung chính
Yêu cầu
sinh viên
chuẩn bị
Ghi
chú
2

4 6
Lý thuyết
Bài tập
Thứ 3, 7h-9h50
P309 T5
Một số dạng đồ thị tô màu

Ứng dụng đồ thị tô màu
để giải toán.
Ôn về đồ
thị tô màu

5
6 Bài tập
Thứ 3, 7h-9h50
P309 T5
Ứng dụng đồ thị tô màu
để giải toán.
Ôn đồ thị
tô màu

7 Lý thuyết
Các tập đặc biệt trên đồ
thị
6 7 Bài tập
Thứ 3, 7h-9h50
P309 T5
Tìm các tập ổn định trong,
ổn định ngoài, nhân của
đồ thị.

đường,
vòng.

10 Lý thuyết Đồ thị Hamilton
10
10
Lý thuyết
Thứ 3, 7h-9h50
P309 T5
Đồ thị Hamilton
Ôn về đồ
thị
Hamilton

Bài tập
Bài tập ứng dụng đồ thị
Hamilton
11
Lý thuyết
Đường đi ngắn nhất
11
11 Thực hành
Thứ 3, 7h-
10h50
Phòng máy
Tìm đường đi ngắn nhất
Ôn về
đường đi
ngắn nhất


Thứ 3, 10h-
12h0
Phòng máy
Tìm cây bao trùm bé nhất
13
12 Thực hành
Thứ 3, 7h-
10h50
Phòng máy
Tìm cây bao trùm bé nhất
Ôn về cây

13 Lý thuyết
Thứ 3, 11h-
12h00
P309 T5
Mạng vận tải
14 13
Lý thuyết
Thứ 3, 7h-7h50
P309 T5
Thuật toán tìm luồng cực
đại
Ôn về
mạng vận
tải

Thực hành
Thứ 3, 8h-
11h50