Đang chuẩn bị liên kết để tải về tài liệu:
GRAPH - Phần 1

Tham khảo tài liệu 'graph - phần 1', 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ả | Khoa Công Nghệ Thông Tin Đại hoc Khoa hoc Tự nhiên I.1 ĐỊNH NGHĨA Đồ THỊ ĐÓ THỊ CÓ 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 tạp cac đỉnh cua đo thị - tập hỢp U la tập cac canh cua đo thị - moi canh ueU đựỢc liên kêt vởi mọt cặp đỉnh i j eX2. Ví du 1 u6 liên kêt vỢi cap C D . Hình vê bên la minh hoa hình hoc cua mọt đo thị co - Tap đỉnh la A B C D . - Tap canh la u1 u2 u3 u4 u5 u6 . - Anh xa ọ định nghĩa nhự sau u1 va u2 liên kêt vỢi cap A B u3 liên kêt vỢi cap A C u4 liên kêt vỢi cap D A u5 liên kêt vỢi cap C B ĐÓ THỊ VÓ HƯỚNG Nếu chung ta khOng phan biêt thự tự cua cap đỉnh liên kết vỢi moi canh thì sê 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 cua đo thị - tap hỢp E la tap cac canh cua đo thị. - moi canh ế E đựỢc liên kết vỢi mOt cap đỉnh i j G X khOng phan biêt thự tự. Ví du 2 Hình vê dựỢi la minh hoa hình hoc cua mOt đo thị co - Tap đỉnh la A B C D . - Tap canh la ê1 ê2 ê3 ê4 ê5 ê6 ê7 . - Anh xa ọ định nghĩa nhự sau ê1 va ê2 liên kết vỢi A B ê3 liên kết vỢi A C ê4 liên kết vỢi A D ê5 liên kết vỢi B C ê6 liên kết vỢi C D ê7 liên kết vỢi D . MÓT SÓ TƯ NGƯ va QUI ƯỚC Khi mOt canh u đựỢc liên kêt vỢi cap đỉnh i j - ta noi canh u kê vỢi đỉnh i va kê vỢi đỉnh j hay cung noi đỉnh i va đỉnh j kê vỢi canh u - ta co thê viêt tat u i j nhự vay co luc ta viết u i j va v i j nhựng lai hiêu u v - nêu đ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. ChựỢng I Đai CựỢng Vê Đo Thị trang I 1 Khoa Công Nghệ Thông Tin Đại hoc Khoa hoc Tự nhiên - nêu đồ thị co hựông thì ta noi cạnh u bat đau tự đỉnh i va kêt thúc tại đỉnh j ta cung noi canh u đi ra khOi đỉnh i va đi vao đỉnh j. Ngoài ra trong giao trình nay chung ta chỉ lam việc vôi trựông hợp cac đo thị co tập đỉnh va tập canh hựu han. Đê cho chính xac thì phai nhấn manh la ĐÔ THỊ HỮU HẠN tuy nhiên đê ngan gon chung ta chỉ dung thuât