Son "sin etiqueta" gráficos de clases de isomorfismo de grafos etiquetados? ¿Cómo puede la gente decir cosas como $K_n$ es "el" grafo completo en $n$ vértices?

Question

Por ejemplo, cuando uno dice algo a lo largo de las líneas de $K_n$ es el grafo completo en $n$-vértices exactamente qué se refieren? Una etiqueta gráfico o una etiqueta gráfico?

Si su etiqueta, a continuación, no tienen que especificar $E(K_n)$ $V(K_n)$ primero?

Si su etiqueta, a continuación, es un isomorfismo de clase? Si no, entonces ¿qué es formalmente?

No tienen etiqueta gráficos no clases de isomorfismo de grafos etiquetados?

Answer 1

La matemática es más importante que la descripción formal de las matemáticas.

Sí, si estamos definiendo un (simple) gráfico como un par $(V,E)$, donde cada una de las $e \in E$ es un subconjunto de a $V$ del tamaño de la $2$, entonces hay varios gráficos que son "completos gráficos en $n$ vértices". Así que podría dejar el $K_n$ denotar el isomorfismo de la clase de completar los gráficos en $n$ vértices, y a veces nos referimos a un isomorfismo de la clase como un "sin etiqueta gráfico".

Pero en la práctica, es conveniente hacer declaraciones como "El grafo completo en $n$ vértices ha $\binom n2$ bordes", y casi todo el mundo hace cuando el vértice conjunto es irrelevante, que es casi siempre. Sería técnicamente más correcto decir "Cada grafo completo en $n$ vértices ha $\binom n2$ bordes", pero esta afirmación es un poco confuso. Nos recuerda la declaración de "Todo árbol en $n$ vértices ha $n-1$ bordes", pero a diferencia de la declaración sobre los árboles, la declaración completa de los gráficos no es realmente necesario considerar varios casos diferentes. Una vez que hayas comprobado que un grafo completo en $n$ vértices ha $\binom n2$ bordes, usted sabe que todos hacen.

En uso real, tiene más sentido para interpretar $K_n$ como denotando una arbitraria grafo completo, cuyo conjunto de vértices no nos importa, porque todo lo que dicen va a trabajar, no importa lo que es.

P. S. me gustaría tener cuidado acerca de la palabra "etiqueta gráfico". Este, en uso real, puede ser entendido a significar algo así como "grafo con conjunto de vértices $\{1, 2, \dots, n\}$ algunos $n$". Por ejemplo:

• Cuando nos preguntan "¿cuántos no marcado de los árboles hay en $n$ vértices?" es justo que traducen a "¿cuántas clases de isomorfismo de los árboles con $n$ vértices tiene?"
• Cuando nos preguntan "¿cuántos etiquetado de los árboles hay en $n$ vértices?", la respuesta es $n^{n-2}$, no $\infty$: nos están preguntando sobre el número de árboles en un conjunto fijo de $n$ vértices, que no necesita ser$\{1,2,\dots,n\}$, pero bien podría ser.

Answer 2

Cuando la gente habla de $K_n$ de los que están hablando sin etiquetar los gráficos. Sin etiquetar los gráficos son mucho más comunes de lo que la etiqueta de los gráficos, y si no hay calificador se da, es todo, pero seguro que una etiqueta gráfico que se quiere decir. Sí, es (un representante) de un isomorfismo de clase.

No entiendo muy bien el significado de la última pregunta. Sin etiquetar los gráficos no están etiquetados gráficos, claramente, así que ¿cómo podrían ser clases de isomorfismo de grafos etiquetados? También, una gráfica no es un isomorfismo de clase, pero un representante de dicha clase.