tailieunhanh - Cấu trúc dữ liệu ( chương 13)

Chương này trình bày về các cấu trúc toán học quan trong được gọi là đồ thị. Đồ thị thường được ứng dụng trong rất nhiều lĩnh vực, điều tra xã hội, hóa học, địa lý, kỹ thuật điện. | Chương 13 - Đồ thị Chương 13 - ĐỒ THỊ Chương này trình bày về các cấu trúc toán học quan trọng được gọi là đồ thị. Đồ thị thương được ưng dung trong rất nhiều lĩnh vực điều tra xà hồi hoa học địa ly ky thuàt điền . Chung tà sề tìm hiều các phương pháp biề9u điền đồ thị bàng càc cấu truc dữ liều và xày dưng mọt so giai thuật tiều biểu liền quan đến đồ thị. . Nen tảng toán học . Các định nghĩá vá ví du Mọt đo thị graph G gom mọt tàp V chưa càc đỉnh cua đo thị và tàp E chưa càc càp đỉnh khàc nhau từ V. Càc càp đỉnh này được gọi là càc canh cua G. Nếu e v Li là mọt canh co hài đỉnh V và LI thì chung tà gọi V và LI nàm trền e và e noi vơi V và LI. Nấu càc càp đỉnh khong co thứ tự G được gọi là đo thị vo hương undirected graph ngươc lài G đươc gọi là đo thị co hương directed graph Thong thương đo thị co hương đươc gọi tàt là digraph con từ graph thương mang nghĩa là đo thị vo hương. Càch tự nhiền đề về đo thị là biề9u diền càc đỉnh bàng càc điề9m hoàc vong tron và càc canh bàng càc đương thang hoàc càc cung nôi càc đỉnh. Đối vơi đo thị co hương thì càc đương thang hay càc cung càn co mui tền chỉ hương. Hình minh họa mọt so ví du về đo thị. Đo thị thứ nhất trong hình co càc thành pho là càc đỉnh và càc tuyền bay là càc canh. Trong đo thị thứ hài càc nguyền tử hydro và carbon là càc đỉnh càc liền kềt hoa học là càc canh. Hình thứ bà là mọt đo thị co hương cho biềt khà nàng truyền nhàn dữ liều trền mang càc nut cua mang A B . F là càc đỉnh và càc đương noi càc nut là co hương. Đoi khi càch chọn tàp đỉnh và tàp canh cho đo thị phu thuọc vào giai thuàt mà chung tà dung đề9 giai bài toàn chàng han bài toàn liền quan đốn quy trình cong viềc bài toàn xốp thơi khoa biề u . Đo thị đươc sử dung đề mo hình hoa rất nhiều dang quà trình cung như càu truc khàc nhau. Đo thị co thề9 biề9u diền mang giao thong giưa càc thành pho hoàc càc thành phàn cua mọt mach in điền tử và càc đương noi giưa chung hoàc cấu truc cua mọt phàn tử gom càc nguyền tử và càc liền kềt hoa .