Bài giảng Bài tập đồ thị

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:40

Thêm vào BST

Báo xấu

89
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Bài tập đồ thị trình bày những bài tập về đồ thị. Bài giảng giúp các bạn vận dụng được những kiến thức lý thuyết đồ thị đã được học để giải bài tập. Bài giảng hữu ích với những bạn chuyên ngành Toán học và những bạn quan tâm tới lĩnh vực này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Bài tập đồ thị

BÀI TẬP LOẠI 1 1. Vẽ tất cả đồ thị a. 3 đỉnh và 3 cạnh. b. 4 đỉnh, 4 cạnh và không có vòng, không có cạnh //. c. liệt kê 4 đồ thị đều trong 2 trường hợp trên. d. đều, 4 đỉnh, mỗi đỉnh bậc 3, không vòng, không có cạnh //. e. đều, 5 đỉnh, mỗi đỉnh bậc 3. 2. Tại một câu lạc bộ có 9 thành viên ngồi ăn với nhau mỗi ngày ở một bàn tròn, mỗi người muốn mỗi ngày 2 người bạn kế bên là bạn mới. Sự xắp xếp kéo dài trong bao nhiêu ngày ?
INSTANT INSANITY 3. Cho 4 khối vuông, 6 mặt của mỗi khối vuông được tô bằng 4 màu khác nhau. Có thể xắp xếp 4 khối thành một cột sao cho mỗi mặt của cột có 4 màu khác nhau ?.
BÀI TẬP 4. Một đồ thị có 21 cạnh có 7 đỉnh bậc 1, 3 đỉnh bậc 2, 7 đỉnh bậc 3, các đỉnh còn lại bậc 4. Đồ thị có bao nhiêu đỉnh ?. Nếu thêm 6 đỉnh bậc 0 thì câu trả lời là bao nhiêu. 5. Chứng minh trong đồ thị đơn giản có ít nhất 2 đỉnh thì phải có ít nhất 2 đỉnh có cùng bậc. 6. Các đồ thị sau có bao nhiêu đỉnh nếu chúng có : a. 12 cạnh, tất cả đỉnh bậc 2. b. 15 cạnh, 3 đỉnh bậc 4, các đỉnh còn lại bậc 3. c. 20 cạnh, các đỉnh có cùng bậc.
BÀI TẬP 7. Số đỉnh lớn nhất trong một đồ thị 19 cạnh và các đỉnh có bậc ít nhất là 3 là bao nhiêu ?. 8. Chứng minh đồ thị đơn giản v đỉnh có số cạnh tối đa v(v 1)/2. 9. Nếu đồ thị đơn giản có 50 cạnh, số đỉnh nhỏ nhất là bao nhiêu?. Tổng quát cho n cạnh. 10. Chứng minh một đồ thị đều bậc lẻ phải có số đỉnh chẵn.
BÀI TẬP 11. Đồ thị có v đỉnh, tất cả các đỉnh có bậc lẻ ngoại trừ một đỉnh. Có bao nhiêu đỉnh bậc lẻ trong đồ thị bù của ?. 12. Gọi e là số cạnh, v là số đỉnh của đồ thị, t(i) là số đỉnh bậc i. chứng minh 2e v = t(0) + t(2) + 2t(3) +...+ (k 1)t(k).
BÀI TẬP LOẠI 2 1. Chứng minh phần bù của đồ thị không liên thông phải liên thông. 2. Chứng minh đồ thị có đúng hai đỉnh bậc lẻ chúng phải thuộc cùng thành phần liên thông. 3. Chứng minh một đồ thị đơn giản v đỉnh, p thành phần liên thông có số cạnh tối đa là e (v p)(v p+1)/2. 4. Chứng minh một đồ thị đơn giản v đỉnh có số cạnh nhiều hơn (v 1)(v 2)/2 là liên thông.
BÀI TẬP 5. Chứng minh một đồ thị đơn giản v đỉnh có số cạnh nhiều hơn (v 1)(v 2)/2 là liên thông. 6. Lấy , là hai đường khác nhau nối hai đỉnh của đồ thị . Chứng minh là một chu trình hoặc tập hợp những chu trình trong . 7. Chứng minh một đồ thị liên thông có 2k đỉnh bậc lẻ, khi đó tập hợp các cạnh có thể được phân hoạch vào k đường sao cho mọi cạnh được dùng đúng một lần. Điều kiện liên thông có cần thiết không hay có thể thay bằng một điều kiện yếu hơn ?.
BÀI TẬP LOẠI 3 1. Đồ thị sau đẳng cấu với nhau hay không : ? ?
BÀI TẬP 2. Đồ thị sau đẳng cấu với nhau hay không : ? ?
BÀI TẬP 3. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 4. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 5. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 6. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 7. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 8. Đồ thị sau đẳng cấu với nhau hay không :
BÀI TẬP 9. Tìm các đồ thị đẳng cấu với nhau.
BÀI TẬP 10. Liệt kê các đồ thị đơn giản có 4 đỉnh không đẳng cấu nhau. 11. Xây dựng đồ thị 6 đỉnh với tính chất sau : a. 3 đỉnh bậc 3 và 3 đỉnh bậc 1. b. các đỉnh có bậc 1, 2, 2, 3, 4, 5. c. các đỉnh có bậc 2, 2, 4, 4, 4, 4. Nếu không thể xây dựng được hãy giải thích lý do. 12. Tìm tất cả đồ thị đều bậc 3 không đẳng cấu nhau có : a. 4 đỉnh. b. 5 đỉnh. c. 6 đỉnh. d. 8 đỉnh.
BÀI TẬP 13. Chứng minh hai đồ thị liên thông v đỉnh tất cả các đỉnh bậc 2 thì đẳng cấu. 14. Độ liên thông đỉnh của đồ thị Kv là bao nhiêu ?. 15. Độ liên thông cạnh của đồ thị Kv là bao nhiêu ?. 16. Chứng minh đồ thị liên thông có 3 đỉnh trở lên có ít nhất 2 đỉnh không là đỉnh cắt. 17. Chứng minh Đồ thị không khả tách mọi cặp đỉnh thuộc một chu trình không giao nhau.
BÀI TẬP 18. Chứng minh : Một đồ thị đơn giản là không khả tách mọi cặp cạnh trong đồ thị có một chu trình chứa chúng. 19. Chứng minh một đồ thị v đỉnh có độ liên thông đỉnh là k phải có ít nhất kv/2 cạnh. Một trường hợp đặc biệt của kết quả này là bậc của mọi đỉnh trong đồ thị không khả tách ít nhất là 2. 20. Mọi đồ thị đều bậc 3 là không khả tách ?. 21. Xây dựng đồ thị có độ liên thông cạnh là 4, độ liên thông đỉnh là 3 và bậc của mọi định 5.
BÀI TẬP 22. Cho thí dụ hai đồ thị có cùng hạng và cùng độ không mà không đẳng cấu bậc 2. 23. Hai đồ thị đẳng cấu cạnh nếu có một tương ứng 11trên giữa tập cạnh của chúng sao cho hai cạnh là kề trong đồ thị này nếu và chỉ nếu cũng kề trong đồ thị kia. 24. Cho một thí dụ đồ thị đẳng cấu cạnh nhưng không đẳng cấu.