Số chéo của K (9, 9)
Tôi đang học lý thuyết đồ thị và tôi không thể tìm ra cách giải quyết vấn đề này. Tôi không giỏi về đồ thị và tôi khá khó giải quyết những vấn đề kiểu này. Tôi sẽ đánh giá rất cao nếu bạn có thể giải thích cho tôi. Cảm ơn trước!
Câu hỏi: Có đúng là mọi k-kết nối ($k>1$) đồ thị không có chu trình Hamilton có chu trình chứa $k$đỉnh độc lập và lân cận của chúng? Điều này được biết là đúng với$k = 2$ và $3$. Ví dụ, đồ thị bên phải là 3 liên thông nhưng không phải là Hamilton. Và chu trình chấm được hiển thị chứa$3$các đỉnh độc lập (ba đỉnh có màu sáng hơn) và các đỉnh lân cận của chúng. Để thấy rằng nó không phải là Hamilton, hãy chú ý rằng đồ thị này chỉ là đồ thị lưỡng phân hoàn chỉnh$K(3,4)$.
Trả lời
Đầu tiên chúng ta hãy nghĩ về trường hợp khi $G$đã kết nối. Nếu$|V| < k$, thì chắc chắn chúng ta không thể phân vùng $V$ thành $k$ các tập con không trống, vì vậy hãy giả sử $|V| \geq k$.
Tôi khẳng định rằng trong trường hợp này có một phân vùng phù hợp. Để hiển thị điều này, chỉ cần tìm một tập hợp con là đủ$V' \subseteq V$ với $|V'| = k-1$ như vậy mà $G - V'$ được kết nối: sau đó chúng ta có thể lấy $V_1$ được $V - V'$ và chúng tôi có thể $V'$ thành các bộ với mỗi phần tử một để lấy $V_2,\dots,V_k$. Làm thế nào để chúng tôi tìm thấy một$V'$? Theo trực giác, chúng tôi lấy một cây bao trùm của$G$ và "ngắt" từng chiếc lá một cho đến khi chúng tôi chụp xong $k-1$. Về mặt hình thức, chúng ta có thể đi qua$G$theo một số thuật toán (ví dụ: DFS). Để cho$v_1, \dots, v_n$là thứ tự mà chúng ta ghé thăm các đỉnh trong quá trình truyền tải này. Thực tế là chúng ta có thể đi qua các đỉnh theo thứ tự này cho thấy rằng$n-(k-1)$ các đỉnh tạo ra một đồ thị con được kết nối của $G$, vì vậy chúng tôi có thể lấy $V'$ là người cuối cùng $k-1$ các đỉnh.
Chuyện gì xảy ra nếu $G$không được kết nối? Chà, nếu nó có nhiều thành phần được kết nối hơn$k$, thì không thể có một phân vùng như vậy (tại sao?). Nếu không (với điều kiện là$|V| \geq k$), về cơ bản chúng ta có thể sử dụng cùng một ý tưởng: lấy một khu rừng bao trùm $G$ và ngắt các lá cho đến khi số lượng các lá bị chặt cộng với số các thành phần được kết nối còn lại là $k$. Một lần nữa, điều này có thể được thực hiện bằng cách sử dụng một thứ tự duyệt, chỉ trong trường hợp này, nó đòi hỏi một số suy nghĩ để xác định có bao nhiêu lá mà chúng ta cần bẻ ra.