Bài tập 9 Toán rời rạc: Đồ thị phẳng thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

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ểudiễ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. Toán rời rạc: Đồ thị phẳng Bài tập 9 thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Toán rời rạc: Đồ thị phẳng
Bài tập 9
1. Các đồ thị sau đây phẳng không? Nếu hãy vẽ để không cạnh cắt.
a)
b)
c)
d)
e)
2. Giả sử một đồ thị phẳng hai phần liên thông e cạnh 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 e cạnh v đỉnh không chứa chu trình
độ 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 k thành phần liên thông, e cạnh, 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,
k.
5. Đồ thị nào trong các đồ thị không phẳng dưới đây tính chất: xóa mọi đỉnh 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 chứa một minor K
3,3
không?
a)
b)
c)
7.
Định nghĩa. Giao số của đồ thị được định nghĩa số giao điểm ít nhất khi vẽ đồ thị
trên mặt phẳng sao cho không ba cạnh nào cắt nhau tại cùng một điểm.
a) Chứng minh rằng K
3,3
giao số bằng 1.
b) *Tìm giao số của mỗi đồ thị không phẳng sau
K
5
K
3,4
K
6
K
4,4
K
7
K
5,5
c) *Chứng minh rằng nếu m n các số nguyên chẵn, thì giao số của K
m,n
nhỏ hơn
hoặc bằng mn(m 2)(n 2)/16.
2
8. Hãy dùng định Kuratowki-Wagner để xác định liệu các đồ thị sau đây 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 phải đồ thị phẳng.
2. Hãy viết chương trình nhập hai đồ thị G
1
G
2
từ file. Thông báo xem G
1
chứa
G
2
như một minor hay không.
3
| 1/3

Preview text:

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) d) b) e) c)
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) c) b) 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 • K6 • K7 • K3,4 • K4,4 • K5,5
c) *Chứng minh rằng nếu m n là các số nguyên chẵn, thì giao số của K nhỏ hơn m,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) c) b) 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