Các dòng tối đa và tối đa

Question

Tôi đang thực hiện bài tập dựa trên hình ảnh này. Tôi đã tìm thấy kích thước clique tối đa là 4. Tôi có một vài câu hỏi về khái niệm lý thuyết đồ thị.

Theo định nghĩa, một clique là một đồ thị con hoàn chỉnh, nơi mỗi cặp đỉnh được kết nối. Điều này có nghĩa là nếu tôi đếm 3-cliques, (3,4,5), (3,4,6), (3,5,6), và (4,5,6) sẽ được tính là 3-cliques ? Hoặc tôi nên bỏ qua các đồ thị con vì chúng là một phần của 4-clique.

Mỗi biểu đồ chỉ có một hình ảnh tối đa tối đa không? Tưởng tượng nó một cách trực quan trong tâm trí tôi, tôi cảm thấy như có thể có nhiều hơn một clique tối đa.

Một trong những câu hỏi trong bài tập hỏi xem mỗi đồ thị có một hoặc nhiều nút phải có ít nhất một clique. Có những thứ như một 2-clique (chỉ là một cạnh) hoặc nên mọi clique tạo thành một hình dạng khép kín?

Tôi dường như không thể vẽ một thể hiện của 4-clique mà không có 3-clique, vì vậy nó là an toàn để giả định rằng mỗi 4-clique có ít nhất một 3-clique? Làm thế nào tôi sẽ đi về kiểm tra cho một cái gì đó như thế này trên một quy mô lớn hơn?

Answer 1

Trước hết, tất cả 3 dòng chữ bạn đã đề cập thực sự là đồ cổ.
Như bạn đã nói, một clique là một đồ thị con nơi tất cả các nút được kết nối với tất cả các nút khác. Vì vậy, trong ví dụ của bạn, (3,4,5) là một clique, và như vậy là (3,4,5,6), và như vậy là (3) và (3,4) (cũng trả lời một số câu hỏi khác của bạn).

Về các đồ thị tối đa, tất nhiên bạn có thể có nhiều hơn 1 - ví dụ: nếu bạn lấy (3,4,5,6) từ biểu đồ của mình, hãy sao chép nó thành (3 ', 4', 5 ', 6 '), và kết nối 3 với 3', sau đó bạn có 2 4-cliques trong đồ thị của bạn, nhưng không có 5-cliques.

Ngoài ra, bất kỳ đồ thị con nào của một clique cũng là một clique, vì mọi đồ thị con vẫn đáp ứng nhu cầu cho tất cả các nút được kết nối với tất cả các nút khác. Ví dụ trong đồ thị của bạn, (3,4,5,6) là một 4-clique. Đi bất kỳ 3 nút từ đó, và bạn sẽ nhận được một 3-clique. Đi 2, và bạn nhận được một 2-clique. Vì vậy, trong thực tế, không chỉ mỗi 4-clique có ít nhất 1 3-clique trong nó, nhưng nó có chính xác 4 3-cliques trong đó (đó là 4C3). Tuy nhiên, hãy lưu ý rằng đôi khi các dòng được định nghĩa là có 2 hoặc nhiều hơn (hoặc đôi khi 3 hoặc nhiều hơn) các nút, vì bất kỳ thứ gì nhỏ hơn đều hơi nhỏ một chút, vì thiếu từ tốt hơn.