La similitud entre dos gráficos no dirigidos $G_1$ y $G_2$ que tienen el mismo $n$ los vértices pueden ser definidos usando:
$$ S(G_1,G_2) = \frac { \sum_i\min ( \deg (v_i \in G_1), \deg (v_i \in G_2))} {2 \times \max (|G_1|,|G_2|)} $$
donde $ \deg (v \in G)$ indica el grado de un vértice $v$ en el gráfico $G$ y $|G|$ indica el número de bordes en $G$ . Si $S(G_1, G_2) = 1$ ¿Las dos gráficas son equivalentes?
Desgraciadamente, El isomorfismo del grafo es un problema más difícil que el de hacer coincidir los grados de los vértices, como demuestra esta figura.
Ambos son grafos no dirigidos con los mismos seis vértices, etiquetados del "1" al "6". Los grados de los vértices de ambos son los mismos, vértice por vértice: un vértice ("1") tiene grado 5, dos ("3" y "6") tienen grado 2, y tres tienen grado 3. Por tanto su métrica de similitud es igual a $1$ .
Sin embargo, hay que tener en cuenta que los tres vértices de grado 3 (etiquetados como "2", "4" y "5") forman un triángulo a la izquierda pero no a la derecha. Por lo tanto, los dos gráficos no son isomorfos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
3 votos
¿Existe alguna métrica estándar para la similitud a la que se refiere? ¿Puede proporcionar una definición y/o una referencia?
0 votos
La similitud de dos grafos no dirigidos que tienen los mismos n vértices es 1
0 votos
Si esa es la definición, parece que has respondido a tu propia pregunta. Sin embargo, su afirmación parece una definición impar de gráfico similitud, cuando sólo tiene que ver con conjuntos de vértices . Normalmente, un gráfico se define como $\{E,V\}$ que incluye un conjunto de vértices $V$ así como un conjunto de bordes $E\subset V\times V$ (como mínimo, es decir, para un gráfico no ponderado).