TAILIEUCHUNG - Bài giảng Toán rời rạc: Chương 5 - Nguyễn Lê Minh
Bài giảng "Toán rời rạc - Chương 5: Lý thuyết đồ thị" cung cấp cho người học các kiến thức: Khái niệm đồ thị, các loại đồ thị, bậc của đồ thị, biểu diễn đồ thị, tính liên thông trong đồ thị, chu trình Euler – Hamilton, tìm đường đi ngắn nhất. . | Bài giảng Toán rời rạc: Chương 5 - Nguyễn Lê Minh TOÁN RỜI RẠC Chương 5: LÝ THUYẾT ĐỒ THỊ GV: NGUYỄN LÊ MINH Bộ môn Công nghệ thông tin Nội dung Khái niệm đồ thị Các loại đồ thị Bậc của đồ thị Biểu diễn đồ thị Tính liên thông trong đồ thị Chu trình Euler – Hamilton Tìm đường đi ngắn nhất 2 Khái niệm Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Có 2 loại đồ thị: Đồ thị có hướng – Đồ thị vô hướng 3 Đồ thị có hướng Đồ thị có hướng G = (V, E) trong đó: • Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị • E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. • Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 2 , quy định hướng đi từ i -> j 3 Đồ thị vô hướng Đồ thị vô hướng G = (V, E) trong đó: • Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị • E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. • Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 2 , không quy định thứ tự. 3 Cạnh song song và khuyên • Nếu đồ thị có cạnh nối từ một đỉnh với chính nó, cạnh này được gọi là khuyên • Nếu hai cạnh V và V’ cùng liên kết với cặp (i,j) thì V và V’ được gọi là cặp cạnh song song với nhau 3 Các loại đồ thị Đồ thị rỗng Đồ thị đơn Đồ thị đủ Có tập cạnh là tập Không có khuyên Là đồ thị vô hướng, rỗng và cạnh song song đơn, 2 đỉnh bất kỳ luôn kề nhau 3 Các loại đồ thị Đồ thị hai phía (Đồ thị lưỡng phân) Là một đồ thị trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai điểm bất kỳ thuộc cùng một tập 3 Đỉnh kề Trong đồ thị vô hướng G=(V,E), nếu e=(u,v) là 1 cạnh thì: • Đỉnh u, v là hai đỉnh kề nhau • Cạnh e là cạnh liên thuộc với đỉnh u,v • Đỉnh u, v là đỉnh đầu u cạnh e e v 3 Đỉnh kề Trong đồ thị có hướng G=(V,E), nếu e=(u,v) là 1 cung thì: • Đỉnh v là đỉnh kề của đỉnh u • Cung e là cung đi ra .
đang nạp các trang xem trước
