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

Trong tài liệu này các bạn sẽ đi chi tiết vào việc hiểu một cấu trúc của đồ thị các thể hiện nó , và nhưng các phương pháp thể hiện khác nhau của đồ thị trong lập trình, và một số ma trận thông dụng để thể hiện đồ thị | C hương 1. Các Khai niệm cơ ban về ĐỒ thị. CHƯƠNG 1. CÁC KHÁI NIÊM CƠ BẢN VE ĐO THỊ. ĐỊNH NGHĨA THÍ DỤ. ĐỊNH NGHĨA. Đô thị co định hướng. Một đồ thị G G X U được xác định bôi Táp hưu hán X xi X2 . Xn táp các đỉnh háy nứt. Táp U u1 u2 . un Ì X x X táp các cung cánh . Đồi vôi một cung u xi Xj Xi lá đỉnh đi Xj lá đỉnh đến háy cồn gội lá gộ c vá đích . Cung u đi tư xi vá đến Xj. Cung u dược bieu diễn một cách hình hộc như sáu 0-------------------------- xi xj . Cung u xi Xj Một cung x i Xi được gọi lá một vong khuyên . Một p-đô thị lá một độ thị trộng độ khộng cộ quá p cung dưôi dáng i j giưá hái đỉnh bất ky. Thí dụ. FIG. . Độ thị xác định bơi X U X xi X2 X3 X4 X5 U ui u2 u3 u4 u5 u6 u7 us Trượng My Dung 1 C hương 1. Các Khai niệm cơ ban về ĐỒ thị. Đồ thị không định hướng. Khi kháo sát một vái tính chát sự định hương cua các cung không đóng một vai tro gì. Tá chỉ quan tám đến sự hiện diện cua các cung giựá hái đỉnh má thôi không cán định rô thư tự . Một cung không định hương được gội lá cạnh. Đôi vơi một canh u xi Xj u đươc gội lá CẠNH TỚI cua hái đỉnh xi vá Xj. Thí dụ. ui FIG. . Độ thị xác định bơi X U X Xi X2 X3 X4 X5 U ui u2 u3 u4 us u6 u7 u8 Một đô thị đươc gội lá đạ đô thị nếu cô nhiếu hơn một canh giữa hái đỉnh. Một đồthị được gọi la đơn nếu 1. Khồng phai lađa đồthị 2. Khồng tồn tai một vồng nao. Hai canh u va v được gội la song song khi chung cung la canh tôi cua hai đỉnh phan biết. Ky hiếu u i v. Thếồ thí du trến ta cồ u1 i u2 Trương Mỹ Dung 2 C hương 1. Các Khai niệm cơ ban về ĐỒ thị. Một sô định nghĩa cơ bản. ANH XẬ ĐA TRỊ. v Xj đươc gọi lá ĐỈNH SAU SUCCESSEUR cua xi nếu xi Xj e U Táp các đỉnh sau cua Xi ky hiệu lá r xi . v Xj được gọi lá ĐỉnH trước PREDECESSEUR cua Xi nếu Xj xi e U Táp các đỉnh trươc cua Xi ky hiệu lá r-1 xi . v Anh Xá r được định nghĩa vơi mọi phan tưcua X tương ưng vơi mọt táp cọn cua X đươc gọi lá mọt Anh xa đa trị. v Đọi vơi mọt 1 -đồ thị G cọ thế họán toán xác định bơi X r đáy lá mọt ky .