Toán rời rạc
TS. Đỗ Đức Đông
dongdoduc@gmail.com
1
y trong đồ thị
1. Khái niệm cây trong đồ thị các thuật ngữ liên quan
2. Những tính chất của cây
3. Các ứng dụng của cây
4. Các phương pháp duyệt cây
5. y khung
6. y khung nhỏ nhất
2
Khái niệm y trong đồ thị
Một đồ thị hướng liên thông không chu trình đơn được gọi y.
y nhiều ứng dụng: tả dạng khác nhau của hợp chất hóa học, cấu
trúc dữ liệu dùng nhiều trong tin học, ứng dụng giải nhiều i toán trong
nhiều lĩnh vực khác nhau.
Trong các đồ thị trên đồ thị nào y?
3
Khái niệm rừng trong đồ th
Một đồ thị hướng không chu trình đơn được gọi rừng. Rừng một
đồ thị mỗi thành phần liên thông một cây.
4
Gốc, cây gốc
Chọn một đỉnh làm gốc (theo tiêu chí của ứng dụng), n cho mỗi
cạnh một hướng (tồn tại duy nhất một đường đi từ nút gốc tới các
đỉnh còn lại) đồ thị hướng cây gốc.
Việc chọn gốc khác nhau sẽ tạo ra cây gốc khác nhau ( thể bỏ
mũi tên chỉ hướng trên c cạnh của y gốc việc chọn gốc đã
xác định hướng của các cạnh)
5