Bài tập Toán rời rạc : Đồ thị

Tài liệu tham khảo các bài tập Đồ thị của môn Toán rời rạc. Bài 1: Cho G là một đồ thị có v đỉnh và e cạnh. M và m tương ứng là bậc lớn nhất và nhỏ nhất của các đỉnh của G. Chứng minh rằng, ...
Nội dung trích xuất từ tài liệu:
Bài tập Toán rời rạc : Đồ thị BÀI TẬP TOÁN RỜI RẠC *** CHƯƠNG 2: ĐỒ THỊ Giảng viên : Nguyễn Mậu Hân Sinh viên thực hiện : Nguyễn Thị DiệuHằng Lớp : Tin K30D 1 * Bài 1: Cho G là một đồ thị có v đỉnh và e cạnh.M và m tương ứng là bậc lớnnhất và nhỏ nhất của các đỉnh của G.Chứng minh rằng: m ≤ 2.e/v ≤ M Lời giải: Theo đề ra ta có: M: bậc lớn nhất của đỉnh của G. m: bậc nhỏ nhất của đỉnh của G. Như vậy: m ≤ deg(vi) ≤ M (với deg(vi) : bậc của đỉnh vi) v.m ≤ ∑deg(vi) ≤ v.M v.m ≤ 2.e ≤ v.M m ≤ 2.e ≤ M Vậy ta có điều phải chứng minh. * Bài 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khiđó e ≤ v2/4. Lời giải : Ta có: G=(V,E) là đơn đồ thị phân đôi. V=V1 U V2, V1 ∩ V2 =ø, V1 ≠ ø, V2 ≠ ø. Gọi n1 và n2 lần lượt là số phần tử của V1 và V2. n1 + n2 = v G là đồ thị phân đôi nên e đạt giá trị max khi G là đồ thị phân đôiđầy đủ.Khi đó: e = n1.n2 Có nghĩa là trong trường hợp tổng quát thì: e ≤ n1.n2 Như vậy, để chứng minh e ≤ v2/4 chỉ cần chứng minh: n1.n2≤ v2/4 Thật vậy: n1.n2 ≤ v2/4 2 n1.n2 ≤ (n1+ n2)2/4 4.n1.n2 ≤ n12 + n22 + 2.n1.n2 n12 + n22 - 2.n1.n2 ≥ 0≤ v2/4 (n1- n2)2 ≥ 0 (hiển nhiên đúng) Suy ra: e ≤ n1.n2 ≤ v2/4 Vậy ta có điều phải chứng minh. * Bài 3: Trong một phương án mạng kiểu lưới kết nối n=m2 bộ xử lý song song,bộ xử lý P(i,j) được kết nối với 4 bộ xử lý (P(i± 1) mod m, j), P(i, (j± 1)mod m), sao cho các kết nối bao xung quanh các cạnh của lưới. Hãy vẽmạng kiểu lưới có 16 bộ xử lý theo phương án này. Lời giải: P(0,0) P(0,1) P(2,0) P(2,1) P(0,3) P(0,2) P(2,3) P(2,2) P(3,0) P(3,1) P(1,0) P(1,1) P(3,3) P(3,2) P(1,3) P(1,2) 3 * Bài 4: Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau: a) b) 1 2 3 1 2 0 1 2 0 4 2 0 3 0 3 4 0 0 3 1 1 1 0 1 0 c) 0 1 3 0 4 1 2 1 3 0 3 1 1 0 1 0 3 0 0 2 4 0 1 2 3 Lời giải:a) b) V V V 1 2 1 V V V V 2 3 4 3 V c) 1 V V 5 2 V V 4 3 4 *Bài 5: Nêu ý nghĩa của tổng các phần tử trên một hàng (tương ứng cột) củamột ma trận liền kề đối với một đồ thị vô hướng ? Đối với đồ thị cóhướng ? Lời giải: Cho đồ thị G=(V,E).V= {v1,v2,...,vn } Ma trận liền kề của đồ thị G=(V,E) là ma trận: A=( aij ) với 1≤i,j≤n a11 a12 ... a1n a21 a22 ... a2n A= ......... an1 an2 ... ann *Nếu G là đồ thị vô hướng: aij là số cạnh nối đỉnh vi và vj -Tổng hàng i của ma trận A: n ∑ aij chính là bậc của đỉnh vi ...