tailieunhanh - Bài giảng Cấu trúc dữ liệu: Chương 5 - TS. Trần Cao Đệ

Bài giảng Cấu trúc dữ liệu: Chương 5 - Đồ thị trình bày các kiểu dữ liệu trừu tượng đồ thị, biểu diễn đồ thị, các phép duyệt đồ thị,. Tham khảo nội dung bài giảng để hiểu rõ hơn về các nội dung trên. | CHƯƠNG V ĐỒ THỊ GRAPH TS. Trần Cao Đệ Năm 2007 ĐỔ THỊ Một đồ thị G V E . V tập hợp các đỉnh nút điểm E tập hợp các cung cạnh Cung nối giữa hai đỉnh v w hai đỉnh này có thể trùng nhau. Hai đỉnh có cung nối nhau gọi là hai đỉnh kề Cung v w có thứ tự thì ta có cung có thứ tự ngược lại thì cung không có thứ tự. Ă Ằ 1 r 1 r 1 r Đồ thị có hướng vô hướng Đường đi path là một dãy tuần tự các đỉnh v1 v2 . vn sao cho vi vi 1 là một cung trên đồ thị i 1 . n-1 . Đường đi này là đường đi từ v1 đến vn và đi qua các đỉnh v2 . vn-1. Đỉnh v1 còn gọi là đỉnh đầu vn gọi là đỉnh cuối. Độ dài của đường đi này băng n-1 . Trường hợp đặc biệt dãy chỉ có một đỉnh v thì ta coi đó là đường đi từ v đến chính nó có độ dài băng không. đỉnh đầu và đỉnh cuối có thể trùng nhau. Một đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là một chu trình cycle . Một chu trình đơn là một đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau và có độ dài ít nhất là 1. Ví dụ trong hình thì 3 2 4 3 tạo thành một chu trình có độ dài 3. Trong nhiều ứng dụng ta thường kết hợp các giá trị value hay nhãn label với các đỉnh và hoặc các cạnh lúc này ta nói đỗ thị có nhãn. Đỗ thị con của một đỗ thị G V E là một đỗ thị G- V E trong đó V ũV và E gỗm tất cả các cạnh v w E sao cho v w V