Bài tập Toán rời rạc - Bài 12

Toán rời rạc: Đồ thị có hướng Bài tập 12 1. Xét trò chơi chọi gà như trong slides. (a) Mô tả một đồ thị cho trò chơi 10 con gà trong đó có một vua gà với bậc ra 1. (b) Mô tả một đồ thị cho trò chơi 5 con gà trong đó mọi con gà đều là vua. 2. Ta ký hiệu δ+(G) =min{outdeg(v) | v ∈ V (G)}, δ−(G) =min{indeg(v) | v ∈ V (G)}. Hãy chứng minh rằng: nếu δ+(G)≥ 1 hoặc δ−(G)≥ 1 thì G chứa chu trình. 3. Một đồ thị gọi là Euler nếu nó có một hành trình đóng đi qua mỗi cạnh đúng một lần. Một đồ thị gọi là nửa Euler nếu nó có một hành trình đi qua mỗi cạnh đúng một lần. (a) Hãy chứng minh rằng một đồ thị có hướng là Euler nếu và chỉ nếu outdeg(v) = indeg(v) với mọi đỉnh v, và đồ thị vô hướng nền của nó có đúng một thành phần liên thông. (b) Tìm tiêu chuẩn đề một đồ thị có hướng là nửa Euler. 4. Chứng minh rằng mọi u, v-hành trình có hướng đều chứa một u, v-đường đi có hướng. 5. Chứng minh hoặc bác bỏ rằng: Nếu D là một đồ thị định hướng của một đồ thị vô hướng với 10 đỉnh, vậy thì các bậc ra của D không thể đôi một khác nhau. 6. Chứng minh rằng: Tồn tại đồ thị thi đấu n đỉnh thỏa mãn mọi đỉnh đều có bậc vào bằng bậc ra nếu và chỉ nếu n lẻ. 7. Với n ≥ 1, hãy chứng minh hoặc bác bỏ rằng: mọi đồ thị có hướng với n đỉnh đều có hai đỉnh có cùng bậc ra hoặc hai đỉnh có cùng bậc vào. 8. Chứng minh rằng đồ thị có hướng là liên thông mạnh nếu với mọi cách phân hoạch tập đỉnh thành hai tập khác rỗng S và T , có một cahnh từ S tới T . 9. Chứng minh rằng trong đồ thị thi đấu G = (V, E) ta luôn có∑ v∈V indeg(v)2 = ∑ v∈V outdeg(v)2 10. Hãy thiết kế một thuật toán để kiểm tra xem một đồ thị có hướng cho trước có liên thông mạnh. 11. Hãy chứng minh rằng mọi đồ thị có hướng liên thông mạnh đều có chu trình Hamilton.