Câu hỏi:
52 lượt xemCho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của: 0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.
Lời giải
Hướng dẫn giải:
Đỉnh là đầu mút của 0 cạnh là đỉnh G.
Đỉnh là đầu mút của 1 cạnh là đỉnh F.
Các đỉnh là đầu mút của 2 cạnh là các đỉnh A, B.
Các đỉnh là đầu mút của 3 cạnh là các đỉnh C, D, E.
Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.
Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một đường đi nối đỉnh 1 và đỉnh 6.
Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có n(n−1)2??−12 cạnh.
Chứng minh rằng không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5.