tailieunhanh - Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị
Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị trình bày về đồ thị vô hướng, đồ thị có hướng, biểu diễn đồ thị, đồ thị Euler, Hamilton, đồ thị Hamilton và nửa Hamilton và một số nội dung khác. | TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH 1 TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@) 2 ĐẠI CƯƠNG VỀ ĐỒ THỊ ĐỒ THỊ VÔ HƯỚNG 3 G = (X,U), trong đó: tập hợp các đỉnh U: tập hợp các cạnh u=(i, j) = (j,i) Đỉnh kề: chung cạnh (vd đỉnh 1,2) Cạnh kề: chung đỉnh (vd cạnh u1, u3) X: u5 4 1 u1 5 u6 Đỉnh cô lập u3 3 2 u10 6 Đỉnh treo ĐỒ THỊ VÔ HƯỚNG 4 Đa đồ thị: tồn tại cặp đỉnh phân biệt (i,j) có nhiều hơn một cạnh và không có khuyên Đồ thị đơn (đơn đồ thị): tất cả các cặp đỉnh (i,j) phân biệt có nhiều nhất một cạnh và không có khuyên u4 u1 2 4 u6 u3 1 u2 u8 u5 3 u7 5 6 ĐỒ THỊ VÔ HƯỚNG Đồ thị đầy đủ là đồ thị luôn tồn tại cung/cạnh nối hai đỉnh bất kỳ Đồ thị con tập hợp con của X Đồ thị con GA của đồ thị G sinh ra bởi A có đỉnh là A có cung/cạnh là cung/cạnh của G mà đỉnh của chúng thuộc A. A .
đang nạp các trang xem trước