tailieunhanh - Phần tích thiết kế giải thuật (phần 12)

Lại trở lại với kiến thức có liên quan tới đồ thị , trong tài liệu này sẽ cung cấp và bổ sung cho bạn thêm những kiến thwucs về đồ thị cơ bản, rất hữu ích cho sinh viên công nghệ thông tin | định nghĩa đO thi ĐO thị co hướng Một đồ thị co hướng G X U được định nghĩa bôi tập hợp X 0 được gội la tap cac đỉnh của đồ thị tạp hợp U la tap cac canh của đồ thị mồi canh ủeU được liên kốt với một cặp đỉnh i j eX2. Ly Thuyết Đo Thị - Các khai niệm cơ ban - Khoa CNTT - Đai Hoc KHTN 2 1 Đồ THỊ CO Hướng Oi Hình ve ben la minh hoa hình học của một đồ thị co Tập đỉnh la A B C D . Tập canh la ủ1 ủ2 ủ3 ủ4 ủ5 ủ6 . Anh xa ọ định nghĩa như saủ ủ1 va ủ2 lien kết với cap A B ủ3 lien kết với cap A C ủ4 lien kết với cặp D A ủ5 lien kết với cap C B ủ6 lien kết với cap C D . Ly Thuyết Đo Thị - Cac khai niệm cơ ban - Khoa CNTT - Đai Hoc KHTN 3 Đồ THỊ Vồ Hướng Nêu chủng ta khong phan biệt thứ tư của cạp đỉnh lien kết với moi canh thì se co đước đo thị vo hướng. Đo thị vo hướng G X E đước định nghĩa bới tap hớp X 0 đước goi la tap cac đỉnh của đo thị tap hớp E la tap cac canh của đo thị. moi canh eeE đước lien kết với mot cap đỉnh i j ç X khong phan biet thứ tự. Ly Thuyết Đo Thị - Cac khai niệm cơ ban - Khoa CNTT - Đai Hoc KHTN 4 2 ĐO thị vO hướng Hình ve dưới la minh hoa hình học cua mọt đo thị co Tập đỉnh la A B C D . Tập canh la e1 e2 e3 e4 e5 e6 e7 . Anh xa ọ định nghĩa như sau el va e2 lien kết với A B e3 lien kết với A C e4 lien kết với A D e5 lien kết với B C e6 lien kết với C D e7 lien kết với D . Ly Thuyết Đo Thj - Cac khai niệm cơ ban - Khoa CNTT - Đai Hoc KHTN MỘT SO TỪ NGỮ va QUI ước Khi một canh u đước lien kết với cặp đỉnh i j ta noi canh u ke với đỉnh i va ke với đỉnh j hay cung noi đỉnh i va đỉnh j ke với canh u ta co the viết tat u i j như vạy co luc ta viết u i j va v i j nhưng lai hiếu u v neu đo thị vo hướng ta noi hai đỉnh i va j đước nôi với nhau nếu đo thị co hướng tưc cap đỉnh i j đước ton trong thư tự ta noi đỉnh i đước nối tới đỉnh j. neu đo thị co hướng thì ta noi canh u bat đau từ đỉnh i va kết thuc tai đỉnh j ta cung noi canh u đi ra khoi đỉnh i va đi vao đỉnh j. Ly Thuyết Đo Thj - Cac khái niệm cơ ban - Khoa CNTT - Đai Hoc KHTN 6