Máxima y la Máxima de Camarillas

Question

EDITAR
Estoy trabajando en un ejercicio basado en la imagen de arriba y se han recogido las respuestas correspondientes para describir la gráfica:

• Una máxima de la clique de tamaño en este gráfico es de 4
• (3,5,6) es una máxima de la camarilla en este gráfico
• (1,2,7) es una máxima de la camarilla en este gráfico
• El número de máximo de 3 grupos en este gráfico es de 6
• (4,5,6) es una camarilla en este gráfico
• Cada gráfico con uno o más nodos deben tener al menos una camarilla
• Cada k-clique ha (k * (k-1)) / 2 aristas

Las respuestas que me deja sin control fueron:

• Cada gráfica tiene sólo UN máximo de camarilla
• Si el gráfico de 4 camarilla, entonces no necesariamente tiene 3 camarilla

Hacer estas respuestas parecen a la derecha o dónde he metido hasta en la comprensión del concepto?

Estoy teniendo problemas para comprender el concepto de la teoría de grafos.

Por definición, un clique es un subgrafo completo en el que cada par de vértices está conectado. ¿Significa esto que si yo tuviera un 4-camarilla que contiene triángulos más pequeños de 3 vértices y 3 bordes, ¿me podrían estos triángulos más pequeños como de 3 camarillas?? O debo omitir los subdiagramas, ya que son parte de la 4-clique.

Cada gráfica tiene sólo un máximo camarilla? Imaginar visualmente en mi mente, me siento como que es posible tener más de una camarilla máxima.

Hay tal cosa como un 2-grupo (sólo un borde) o cada grupo forma una forma cerrada?

Me parece que no puede dibujar una instancia de un 4-camarilla que no tiene un 3-la camarilla, por lo que es seguro asumir que cada 4-camarilla tiene al menos un 3-la camarilla? Cómo voy a ir yo acerca de la comprobación de algo como esto en una escala mayor?

Lo siento por el montón de preguntas, pero mi nota para el instructor son difíciles de seguir.

Answer 1

Un $k$- "camarilla" es cualquier colección de $k$ vértices en la que cada borde posible está presente. Por lo tanto, tiene el derecho de decir, por ejemplo, una de 4 camarilla contiene muchos diferentes 3-camarillas y 2-cliques (el último, de ser sólo un borde).

Para tu otra pregunta, puede ser confuso de las palabras "máximo" y "máxima". Para apreciar la diferencia, considere la posibilidad de un gráfico en el que es distinto de la unión de 3 camarilla y dos de 4 camarillas (por lo que la gráfica tiene tres componentes).

Tanto de la 4-estos grupos son máximode tamaño de las camarillas en el gráfico, ya que son la más grande de las camarillas que usted puede encontrar en cualquier lugar del gráfico.

La camarilla es maximal si no se puede hacer más en ese gráfico en particular. En nuestro ejemplo, los tres componentes son cada máxima de las camarillas. Como se dijo antes, el 4-camarillas contienen muchos 3-camarillas dentro de ellos. Estos "subcliques" son no máxima, ya que pueden hacerse más grande (en particular, pueden extenderse a las 4 camarilla que los contienen).

Observe que el 3-camarilla componente es máxima (no se puede hacer más con vértices en nuestro gráfico), pero no máximo (no es un más grande de la camarilla en el gráfico).

Answer 2

La camarilla es, como usted dice, un subgrafo inducido en el que cada vértice está conectado a todos los otros vértices. Las pandillas pueden estar contenidos en el uno al otro: de hecho, cada subgrafo de un clique es necesariamente la misma camarilla. Nada de malo o problemática con la que. Así que si usted tiene un 4-la camarilla, entonces cada uno de sus cuatro subdiagramas con tres vértices son camarillas así.

No, no, cada gráfica tiene un único máximo de la camarilla. Por ejemplo, tomar dos triángulos y conecte un vértice de uno de ellos a otro vértice de la otra. No hay ningún conjunto de cuatro vértices están mutuamente conectados, así que no hay de 4 grupos en que gráfico; los dos triángulos son ambos máxima camarillas, y no hay una sola "más grande de la camarilla".

2-cliques sentido, sino que son el caso trivial de camarillas (interesante).

Answer 3

Tomando la Wikipedia la definición, "Una camarilla en un grafo no dirigido G = (V, E) es un subconjunto de vértices conjunto C ⊆ V, tal que para cada par de vértices en C, existe una arista que conecta a los dos." dos vértices que están conectados por una arista de un formulario a una pandilla. Si usted tiene alguna camarilla, cualquier subconjunto de vértices forman un grupo cerrado, por lo que una de 4 camarilla se incluyen cuatro diferentes 3-camarillas. Ciertamente, es posible tener más de una máxima de la camarilla. Por ejemplo, dibuja dos triángulos (que cada uno se forma una camarilla). Si quieres un grafo conexo con dos máximos de las camarillas, conecte un vértice de un triángulo con un vértice de la otra.