TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Lý thuyết đồ thị - TS. Trần Ngọc Việt

Bài giảng Cấu trúc dữ liệu và giải thuật: Lý thuyết đồ thị, được biên soạn gồm các nội dung chính sau: định nghĩa về đồ thị, cây; biểu diễn đồ thị trên máy tính; thuật toán đường đi ngắn nhất – dijkstra’s. Mời các bạn cùng tham khảo! | 1. ĐỒ THỊ diễn đồ thị trên máy tính Định nghĩa 1 Đơn đồ thị vô hướng bao gồm V là tập các đỉnh E là tậ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 cạnh không kể thứ tự Định nghĩa 2 Đơn đồ thị có hướng bao gồm V là tập các đỉnh E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung có thứ tự Xét đồ thị đơn vô hướng với tập đỉnh 1 2 . . tập cạnh 1 2 . . . Ta gọi ma trận kề của đồ thị G là ma trận có các phần tử bằng 0 hoặc 1 1 ế 0 ế 1 2 . . . 2 KHOA CÔNG NGHỆ THÔNG TIN 1. ĐỒ THỊ Ví dụ 1 Hình 1 Hình trên là đồ thị G V E trong đó tập đỉnh là 1 2 3 4 5 6 Và tập các cạnh là 1 2 3 4 5 6 7 Đường đi là dãy các đỉnh và các cạnh nối tiếp nhau. Độ dài đường đi là số các cạnh của nó. 3 KHOA CÔNG NGHỆ THÔNG TIN 1. ĐỒ THỊ Ví dụ 2 cho đồ thị Hình 1 trên dãy 1 1 2 4 4 7 6 là đường đi từ 1 đến 6 có độ dài bằng 3. Ví dụ 3 cho đồ thị Hình 1 trên dãy 1 1 2 4 4 3 3 2 1 là chu trình từ 1 quay về 1 . Đồ thị G gọi là liên thông nếu giữa hai đỉnh bất kì bao giờ cũng tồn tại đường đi nối chúng với nhau. Đồ thị trên không liên thông vì từ 5 không có đường đi đến các đỉnh khác. Đỉnh 5 gọi là đỉnh cô lập. 4 KHOA CÔNG NGHỆ THÔNG TIN 2. CÂY Cây là đồ thị liên thông không chứa chu trình giữa 2 đỉnh bất kỳ của cây chỉ tồn tại một đường đi duy nhất nối chúng với nhau . Ví dụ 4 Một người tên A có ba con là B C và D. B có hai con là E và F. C độc thân không có con. D có ba con là G H và I. H có hai con là J và K. Hình 2 5 KHOA CÔNG NGHỆ THÔNG TIN 2. CÂY Gốc của cây là một đỉnh đặc biệt do người dùng ấn định thông thường là đỉnh trên cùng của cây. Cho T là cây có gốc 0 . Giả sử x y z là các đỉnh trong T và 0 1 . . là đường đi trong T. Khi đó ta gọi 1 là cha của k 1 n. 0 1 . . 1 là tiền bối của k 1 n. là con của 1 k 1 n. y là hậu thế của x nếu x là tiền bối của y y và z là anh em nếu chúng đều là con của đỉnh x Nếu tập các nút rỗng ta có cây rỗng. Một nút không phải gốc và các nút hậu thế của nó tạo thành cây gọi là cây con. Bậc của nút là số nút con của nút đó.

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Lý thuyết đồ thị
• Thuật toán đường đi ngắn nhất
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm