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

Toán rời rạc: Đồ thị phẳng Bài tập 9 1. Các đồ thị sau đây có phẳng không? Nếu có hãy vẽ để nó không có cạnh cắt. a) b) c) d) e) 2. Giả sử một đồ thị phẳng hai phần liên thông có e cạnh và v đỉnh. Hãy chứng minh rằng e ≤ 2v − 4 nếu v ≥ 3. 3. Giả sử một đồ thị liên thông hai phần phẳng có e cạnh và v đỉnh và không chứa chu trình có độ dài ≤ 4. Hãy chứng minh rằng e ≤ (5/3)v − (10/3) nếu v ≥ 3. 4. Xét đồ thị phẳng có k thành phần liên thông, e cạnh, và v đỉnh. Ta cũng giả sử rằng biểu diễn phẳng của đồ thị chia mặt phẳng thành r miền. Hãy tìm công thức cho r theo e, v, và k. 5. Đồ thị nào trong các đồ thị không phẳng dưới đây có tính chất: xóa mọi đỉnh và mọi cạnh liên thuộc với đỉnh đó cho ta một đồ thị phẳng? Giải thích. 1 6. Các đồ thị dưới đây có chứa một minor là K3,3 không? a) b) c) 7. Định nghĩa. Giao số của đồ thị được định nghĩa là số giao điểm ít nhất khi vẽ đồ thị trên mặt phẳng sao cho không có ba cạnh nào cắt nhau tại cùng một điểm. a) Chứng minh rằng K3,3 có giao số bằng 1. b) *Tìm giao số của mỗi đồ thị không phẳng sau • K5 • K3,4 • K6 • K4,4 • K7 • K5,5 c) *Chứng minh rằng nếu m và n là các số nguyên chẵn, thì giao số của Km,n nhỏ hơn hoặc bằng mn(m− 2)(n− 2)/16. 2 8. Hãy dùng định lý Kuratowki-Wagner để xác định liệu các đồ thị sau đây có phẳng không? a) b) c) Bài tập lập trình Nếu bạn hoàn thành hai bài tập sau đây, hãy thông báo để giáo viên cộng 2 điểm vào bài thi giữa kỳ. 1. Hãy viết chương trình nhập vào một đồ thị (dưới dạng ma trận kề hoặc danh sách cạnh) từ file. Thông báo xem liệu đồ thị vừa nhập có phải đồ thị phẳng. 2. Hãy viết chương trình nhập hai đồ thị G1 và G2 từ file. Thông báo xem G1 có chứa G2 như một minor hay không. 3