Bài giảng Toán rời rạc: Đồ thị - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Đồ thị được biên soạn gồm các nội dung chính sau: các định nghĩa và ví dụ; biểu diễn đồ thị bằng ma trận; bậc của đỉnh; đẳng cấu; đồ thị con; đường đi, chu trình, đồ thị liên thông; những đơn đồ thị đặc biệt. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Đồ thị - ThS. Hoàng Thị Thanh Hà Toán rời rạc (3): ĐỒ THỊ Ths. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học Trường Đại học Kinh tế Đại học Đà Nẵng27 September 2012 1 Nội dung1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN3. BẬC CỦA ĐỈNH4. ĐẲNG CẤU5. ĐỒ THỊ CON6. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG7. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT27 September 2012 2 1 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. Lý thuyết đồ thị giải quyết các bài toán sau: – Tìm đường đi ngắn nhất – Tìm cây bao trùm tối thiểu – Chu trình đường đi Euler, Hamilton – …27 September 2012 3 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN1: Đồ thị vô hướng G=(V,E) là một bộ gồm 2 tập hợp: i. Tập V tập khác rỗng chứa các đỉnh ii. Tập E chứa các cạnh (đó là các cặp không có thứ tự của các đỉnh). Cạnh e nối 2 đỉnh v, w kí hiệu là e=(v,w) – Mỗi đỉnh được biểu diễn bằng 1 điểm, mỗi cạnh là một đoạn thẳng hoặc đường cong nối giữa 2 điểm đó – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cạnh e hay e liên thuộc cạnh v và w – Hai cạnh song song khi chúng liên thuộc cùng với 1 cặp đỉnh – Cạnh có 2 đầu mút trùng nhau gọi là khuyên27 September 2012 4 2 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cạnh e hay e liên thuộc cạnh v và w – Hai cạnh song song khi chúng liên thuộc cùng với 1 cặp đỉnh – Cạnh có 2 đầu mút trùng nhau gọi là khuyên27 September 2012 5 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN2: Đồ thị vô hướng không có cạnh song song, không có khuyên gọi là Đơn đồ thị vô hướng27 September 2012 6 3 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN3: Đồ thị vô hướng có cạnh song song nhưng không có khuyên gọi là Đa đồ thị vô hướng – Đơn đồ thị là đa đồ thị27 September 2012 7 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN4: Đồ thị vô hướng có cạnh song song và có khuyên gọi là Giả đồ thị vô hướng27 September 2012 8 4 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị vô hướng: Giả đồ thị Đa đồ thị Đơn đồ thị27 September 2012 9 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ ĐN5: Đa đồ thị có hướng G=(V,E) là một bộ gồm 2 tập hợp: i. Tập V tập khác rỗng chứa các đỉnh ii. Tập E chứa các cung, đó là các cặp có thứ tự hai đỉnh. Cung e nối 2 đỉnh v, w kí hiệu là e=(v,w), ta nói cung e đi từ v đến w – Mỗi đỉnh được biểu diễn bằng 1 điểm, mỗi cung là một đoạn thẳng hoặc đường cong có hướng nối giữa 2 điểm27 September 2012 10 5 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ – Nếu e=(v,w) thì đỉnh v và w gọi là kề nhau hay v, w liên thuộc cung e hay e liên thuộc cung v và w, v là đỉnh gốc (đầu), w là đỉnh ngọn (cuối) – Hai cung song song khi chúng có cùng gốc và ngọn – Cung có gốc và ngọn trùng nhau gọi là khuyên ĐN6: Đồ thị có hướng không chứa các cạnh song song gọi là đồ thị có hướng27 September 2012 11 1. CÁC ĐỊNH NGHĨA VÀ VÍ DỤ Đồ thị Cạnh Cạnh song song Khuyên Đơn đồ thị vô Vô hướng Không Không hướng Đa đồ thị vô hướng Vô hướng Có Không Giả đồ thị vô Vô hướng Có Có hướng Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng có có27 September 2012 12 6 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN ĐN1: Ma trận liền kề (ma trận kề): – Cho đồ thị G = (V,E) với V = {1,2,…n}, ma trận kề của G là ma trận A(n*n) với aij= số cạnh nối từ đỉnh i đến đỉnh j – Như vậy, ma trận liền kề của một đồ thị vô hướng là ma trận vuông đối xứng trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng.27 September 2012 13 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ví dụ: Ma trận liền kề của đồ thị v1 v2 0 3 0 2   3 0 1 1 0 1 1 2   2 1 2 0 v4 v3  27 September 2012 14 7 2. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬNMa trận liền kề với thứ tự các đỉnh v1, v2, v3, v4, v5 v1 1 1 0 1 1 ...