
TOÁN RỜI RẠC
CHƯƠNG 7
ĐỒ THỊ VÀ CÂY
Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@mta.edu.vn
@Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
1

NỘI DUNG
2
@Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University

7.1. GIỚI THIỆU CHUNG
Nội dung chính của chương này đề cập đến những khái niệm
cơ bản nhất của đồ thị, phương pháp biểu diễn đồ thị trên
máy tính và một số khái niệm liên quan.
Các loại đồ thị vô hướng, đồ thị có hướng, đa đồ thị…
Khái niệm về bậc của đỉnh, đường đi, chu trình và tính liên thông
của đồ thị.
Biểu diễn đồ thị bằng ma trận kề.
Biểu diễn đồ thị bằng danh sách kề.
Biểu diễn đồ thị bằng danh sách cạnh
3
@Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University

7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (1/17)
7.2.1. Mở đầu (1/2)
Lý thuyết đồ thị được đề xuất từ thế kỷ 18, bắt đầu từ bài báo
của Euler công bố năm 1736 liên quan đến lời giải bài toán nổi
tiếng về các cây cầu ở Konigsberg.
Cho tới nay, mối quan tâm đến lý thuyết đồ thị vẫn không hề suy
giảm.
Lý do: phạm vi ứng dụng hết sức rộng rãi của đồ thị trong rất
nhiều lĩnh vực khác nhau, bao gồm:
Trong tin học,
Hoá học,
Vận trù học,
Kỹ thuật điện,
Ngôn ngữ
Kinh tế…
4
@Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University

7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (2/17)
7.2.1. Mở đầu (2/2)
Vậy đồ thị là gì?
Có thể định nghĩa:
Đồ thị (Graph) là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh
và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị
thông qua kiểu và số lượng cạnh nối giữa các cặp đỉnh của đồ
thị.
5
@Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University

