tailieunhanh - Bài tập về lý thuyết đồ thị

1. Chứng minh định lý 1 về tính chất cơ bản của cây. 2. Chứng minh định lý 2 về tính chất cơ bản của cây. 3. Cho G-(S,A) là đồ thị có định hướng có n đỉnh G' là đồ thị không định hướng tương ứng với G. Chứng minh những phát biểu sau là tương đường với nhau: | BAI TẬP VE LY THUYET Đồ THỊ. Trương My Dung 2003 -2004. Bài tập Lý thuyết Đổ thị BAI TẬP VE LY THUYET Đồ THỊ. CH. 1. CÁC KHÁI NIỆM Cơ BAN VE LY THUYET Đồ THỊ. CH. 2. CÁU TRUC Cây. CH. 3. BÁI TOÁN TÌM ĐƯƠNG ĐI NGÁN NHÁT. CH. 4. Đồ THỊ PHÁNG BÁI TOÁN Tồ MÁU. BÁI TÁP TồNG HƠP. Trương Mý Dung 1 Bài tập Lý thuyết Đổ thị CH. 1. CAC KHAI NIÊN CƠ BAN VE LY THUYET Đồ THỊ. 1. Vế một đồ thị co định hướng không định hướng trong càc trường hợp sau 3 đĩnh và 3 canh. 4 đĩnh 4 canh và không cô vông không cô canh song song. Tính bạc cua cac đĩnh cua hai đô thị nếu trến. Liết kế 4 đô thị con đếu cô bâc cua môi đĩnh bang nhau trong 2 đô thị nếu trến. Đếu 4 đĩnh môi đĩnh bâc 3 không cô vông không cô canh song song. Đếu 5 đĩnh môi đĩnh bâc 3. 2. Môt đô thị không định hường cô 21 canh cô 7 đĩnh bâc 1 3 đĩnh bâc 2 7 đĩnh bâc 3 cac đĩnh côn lai bâc 4. Đô thị cô bao nhiếu đĩnh Nếu thếm 6 đĩnh bâc không thì cau tra lời la bao nhiếu 3. Cac đô thị sau đay cô bao nhiếu đĩnh nếu chung cô 12 canh tất ca đĩnh bâc 2. 15 canh 3 đĩnh bâc 4 cac đĩnh côm lai bâc 3. 20 canh cac đĩnh cô cung bâc. 4. Môt đô thị cô 19 canh va môi đĩnh đếu cô bâc 3. Đô thị nay tôi đa cô bao nhiếu đĩnh 5. Chưng minh bang qui nap tông bâc cac đĩnh la môt sô chan. 6. Chưng minh rang moi đô thị đếu cô môt sô chan cac đĩnh lế. 7. Môt đô thị cô đung hai đĩnh bâc lế thì phai cô môt đường nôi hai đĩnh nay. Hường dan. Chưng minh bang phan chứng. 8. Chứng minh Định ly 1 cua Định ly EULER. 9. Chứng minh Định ly 2 cua Định ly EULER. 10. Chứng minh Định ly 3 cua Định ly EULER. Trứơng My Dung