TAILIEUCHUNG - Giáo trình Turbo Pascal 7.0 - Lý thuyết, bài tập và lời giải part 8

Tham khảo tài liệu 'giáo trình turbo pascal - lý thuyết, bài tập và lời giải part 8', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | TS. Bùi Thê Tâm 140 Giáo trình Turbo Pascal Chương 13 Đồ thị hữu hạn Chương này trình bày vé đổ thị có hướng và dổ thị vò hướng tính sơ thành phần hèn thông của dổ thị tìm kiếm theo chiêu sâu và tìm kiếm theo chiều rộng trên đỏ thị tìm đường di ngắn nhất giữa mọi cặp đỉnh cùa đổ thị tìm cây bao trùm ngan nhất. 1. ĐỒ thị và tính liên thông Một đồ thị vô hướng G gồm hái tập hợp hữu hạn V và E. đồ thị G được ký hiệu là G V E . V gọi là tập dính của đó thị không giảm tổng quát ta có thế xem n đỉnh của G là tập n số nguyên dương đẩu Hôn V 1 2 . . . n . E là tập hợp con các tích đồ các V X V mà nếu i j thuộc E thì j i cũng thuộc E và ta đổng nhất i j với J i . Mổi phần tử của E gọi là một cạnh của đổ thị Nếu i j là một cạnh ta nói cạnh đó nói đính í với đinh j ta cũng nói hai đình i và j là kề nhau. Một đổ thị có hướng G gồm hai tập hợp hưu hạn V và E và ký hiệu ỉà G V E . V là tập đình của đồ thị. E là tập hợp các cung cùa đồ thị nó là tập con của tích đe các V X V Nếu i j là một cung thì ta nói i. j là cung di từ đỉnh i tới dính j. Trong đồ thị có hướng cung i j khác vói cung . i . Trong thực tế ta thường gặp dồ thị vừa có cạnh vô hướng vừa có cung có hướng chảng hạn như ịường giao thông trong thành phố. Đế chuyển một đổ thị vô hướng thành có hướng ta có thế thay mỗi cạnh vô hướng bàng hai cung có hướng ngược nhau cùng nối lien hai dỉnh. Biểu dicn hình học một đổ thị dùng dấu châm đe bĩcu thị đỉnh sò ở cạnh đỉnh là tên đinh cạnh nới đỉnh i và đỉnh j biếu thị bàng một đường nôi hai dinh cung nối hai đỉnh bleu thị bằng mũi tên. Hình 1 là đổ thị vó hướng Hình 2 là đổ thị có hướng. Biểu diễn đổ thị trèn máy tính bàng ma trận kề. Ta dùng một máng gồm n hàng và n cột a l .. n trong đó n là sô đỉnh của dồ thị. Nêu từ đỉnh i tới dinh j không có cạnh hay cung nào thì a 0 còn nêu có cạnh hay cung đi từ i den j thi a i j l. Ma trận ké của một đổ thị vờ hướng là một ma trận dối xứng ma trận kề cũa một đồ thị có hướng nói chung là không đối xứng. Một đường đi từ đỉnh u .

• Kỹ thuật lập trình
• Turbo Pascal
• kỹ thuật lập trình Turbo Pascal
• ứng dụng Turbo Pascal
• tài liệu Turbo Pascal
• giáo trình Turbo Pascal
• bài giảng Turbo Pascal
• mứng dụng Turbo Pascal
• lập trình Turbo Pascal
• kinh nghiệm lập trình Turbo Pascal
• hướng dẫn lập trình Turbo Pascal
• phương pháp lập trình Turbo Pascal
• Ngôn ngữ lập trình Pascal
• Bài giảng Ngôn ngữ lập trình Pascal
• Thực hành Turbo Pascal
• Turbo Pascal Version 5
• Turbo Pascal Version 7
• Cách khởi động Turbo Pascal
• Lập trình bằng Turbo Pascal
• đề cương Turbo Pascal