Максимальные и максимальные клики

Я работаю над упражнением, основанным на этом изображении. Я нашел максимальный размер клики равным 4. У меня есть несколько вопросов о концепции теории графов.

По определению клика является полным подграфом, где каждая пара вершин соединена. Означает ли это, что если бы я считал 3-клики, (3,4,5), (3,4,6), (3,5,6) и (4,5,6) считались 3-кликами? Или я должен опустить эти подграфы, поскольку они являются частью 4-клики.

Есть ли у каждого графика только максимальная клика одна? Представляя это визуально в моем сознании, я чувствую, что возможно иметь более чем одну максимальную клику.

Один из вопросов в упражнении спрашивает, должен ли каждый граф с одним или несколькими узлами иметь хотя бы одну клику. Есть ли такая вещь, как 2-клика (только край) или каждая клика образует замкнутую форму?

Я не могу представить пример 4-клики, у которой нет 3-клики, поэтому можно с уверенностью предположить, что каждая 4-клика имеет хотя бы одну 3-клику? Как я могу проверить что-то подобное в более широком масштабе?

Ответы

Ответ 1

Прежде всего, все эти 3-клики, которые вы упомянули, действительно клики.
Как вы сказали, клика - это подграф, где все узлы соединены со всеми другими узлами. Таким образом, в вашем примере (3,4,5) является кликой, и так же (3,4,5,6), а также (3) и (3,4) (что также отвечает на некоторые из ваших других вопросов).

В отношении максимальных кликов, конечно, у вас может быть более 1 - например, если вы берете (3,4,5,6) из своего графика, дублируйте его на (3 ', 4', 5 ', 6 '), и соедините 3 с 3', тогда у вас есть 2 4-клика на вашем графике, но нет 5-кликов.

Кроме того, любой подграф клики также является кликой, поскольку каждый подграф все еще удовлетворяет требованию для всех узлов, связанных со всеми другими. Например, на вашем графике (3,4,5,6) есть 4-клика. Возьмите все 3 узла, и вы получите 3-клику. Возьмите 2, и вы получите 2-клику. Таким образом, на самом деле, не только каждая 4-клика имеет по крайней мере 1 3-клику в ней, но она имеет ровно 4 3-клика в ней (это 4C3).

Обратите внимание, однако, что иногда клики определяются как имеющие 2 или более (или иногда 3 или более) узла, потому что что-то меньшее немного тривиально из-за отсутствия лучшего слова.