Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh cùng bậc.
Câu hỏi trong đề: Chuyên đề Toán 11 KNTT Bài tập cuối chuyên đề 2 có đáp án !!
Quảng cáo
Trả lời:
Giải bởi Vietjack
Lời giải:
Giả sử G là một đơn đồ thị có n đỉnh (n ≥ 2).
Vì G là đơn đồ thị nên mỗi đỉnh của G không có khuyên và chỉ có thể nối với các đỉnh khác không quá một cạnh, nghĩa là mỗi đỉnh của G có bậc tối đa là (n – 1) (*).
Giả sử bậc của các đỉnh của G đều khác nhau. Khi đó bậc của n đỉnh của G lần lượt là 0, 1, ..., (n – 1), nghĩa là G phải có đỉnh bậc 0.
Do G có đỉnh bậc 0 nên các đỉnh khác của G có bậc tối đa là (n – 2) (mâu thuẫn (*)).
Vậy có ít nhất 2 đỉnh của G có cùng bậc.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay
Đăng ký VIP để học và luyện thi không giới hạn
Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.
- Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
- Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
- Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
- Tải xuống đề thi [DOCX] với đầy đủ đáp án
- Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
- Bao gồm tất cả các bậc từ Tiểu học đến Đại học
- Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
- Đăng ký ngay
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Lời giải:
Đồ thị Hình 2.42 chỉ có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D đến E (đường đi này đi qua mỗi cạnh đúng một lần).
Một đường đi Euler từ D đến E là DBACDEBCE và tổng độ dài của nó là
2 + 4 + 4 + 2 + 6 + 3 + 5 + 1 = 27.
Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến D theo thuật toán gắn nhãn vĩnh viễn.
Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.
Vậy một chu trình cần tìm là DBACDEBCECD và có độ dài là 27 + 3 = 30.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Lời giải:
Ta vẽ được đồ thị G như hình trên.
Đồ thị G này không có khuyên và hai đỉnh chỉ được nối với nhau bằng nhiều nhất một cạnh nên là một đơn đồ thị.
Đồ thị G không phải đồ thị đầy đủ vì không phải tất cả các cặp đỉnh của nó đều được nối với nhau bằng một cạnh.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập