Clips massimo e massimo

Question

Sto lavorando a un esercizio basato su questa immagine. Ho trovato che la dimensione massima della clique è 4. Ho alcune domande sul concetto di teoria dei grafi.

Per definizione, una cricca è un sottografo completo in cui ogni coppia di vertici è collegata. Ciò significherebbe che se dovessi contare su 3-clique, (3,4,5), (3,4,6), (3,5,6) e (4,5,6) conterei come 3-clique ? O dovrei omettere quei sottografi dal momento che fanno parte della 4-clique.

Ogni grafico ha solo una clique massima di? Immaginandolo visivamente nella mia mente, sento che è possibile avere più di una cricca massima.

Una delle domande nell'esercizio chiede se ogni grafico con uno o più nodi deve avere almeno una cricca. Esiste una cricca 2 (solo un bordo) o ogni cricca dovrebbe formare una forma chiusa?

Non riesco a disegnare un'istanza di una 4-clique che non ha una 3-cricca, quindi è lecito ritenere che ogni 4-clique abbia almeno una 3-clique? Come farei a controllare qualcosa di simile su una scala più ampia?

Answer 1

Prima di tutto, tutte quelle 3-clique che hai menzionato sono in effetti delle cricche.
Come hai detto, una cricca è un sottografo in cui tutti i nodi sono connessi a tutti gli altri nodi. Quindi nel tuo esempio, (3,4,5) è una cricca, e così è (3,4,5,6), e così sono (3) e (3,4) (che risponde anche ad alcune delle tue altre domande).

Per quanto riguarda le clique massime, ovviamente si potrebbe avere più di 1 - ad esempio, se si prende il (3,4,5,6) dal grafico, duplicarlo in (3 ', 4', 5 ', 6 ') e connetti 3 con 3', quindi nel tuo grafico ci sono 2 4-clique, ma non ci sono 5-clique.

Inoltre, qualsiasi sottografo di una clique è anche una cricca, poiché ogni sottografo soddisfa ancora la richiesta di tutti i nodi connessi a tutti gli altri. Per esempio nel tuo grafico, (3,4,5,6) è un 4-gruppo. Prendi qualsiasi 3 nodi da lì e otterrai una 3-cricca. Prendi 2, e ottieni una 2-cricca. In effetti, non solo ogni 4-cricca ha almeno 1 3-cricca, ma ha esattamente 4 3-clique in esso (cioè 4C3).

Si noti, tuttavia, che a volte le clique sono definite come aventi 2 o più (o talvolta 3 o più) nodi, perché qualsiasi cosa più piccola è un po 'banale, per mancanza di una parola migliore.