in

Teoría de grafos – Isomorfismo

graphs are isomorphic

Un gráfico puede existir en diferentes formas con el mismo número de vértices, aristas y también la misma conectividad de aristas. Estos gráficos se denominan gráficos isomórficos. Tenga en cuenta que etiquetamos los gráficos en este capítulo principalmente con el propósito de hacer referencia a ellos y reconocerlos entre sí.

Gráficos isomórficos

Dos gráficos G1 y G2 se dice que son isomorfos si –

Nota – En resumen, de los dos gráficos isomórficos, uno es una versión modificada del otro. Un gráfico sin etiquetar también se puede considerar como un gráfico isomórfico.

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

Nota

Si G1 ≡ G2 entonces –

| V (G1) | = | V (G2) |

| E (G1) | = | E (G2) |

Secuencias de grados de G1 y G2 son idénticos.

Si los vértices {V1, V2, .. Vk} forman un ciclo de longitud K en G1, luego los vértices {f (V1), f (V2),… F (Vk)} debe formar un ciclo de longitud K en G2.

Todas las condiciones anteriores son necesarias para los gráficos G1 y G2 para ser isomorfo, pero no suficiente para probar que los gráficos son isomorfos.

  • (GRAMO1 ≡ G2) si y solo si (G1– ≡ G2-) donde G1 y G2 son gráficos simples.

  • (GRAMO1 ≡ G2) si las matrices de adyacencia de G1 y G2 son idénticos.

  • (GRAMO1 ≡ G2) si y solo si los incisos correspondientes de G1 y G2 (obtenido al eliminar algunos vértices en G1 y sus imágenes en el gráfico G2) son isomorfos.

Ejemplo

¿Cuáles de las siguientes gráficas son isomórficas?

Los gráficos son isomorfos

En el gráfico G3, el vértice ‘w’ tiene solo grado 3, mientras que todos los demás vértices del gráfico tienen grado 2. Por lo tanto, G3 no es isomorfo a G1 o G2.

Tomando complementos de G1 y G2, tienes –

Otros vértices de gráfico

Aquí, (G1– ≡ G2-), por lo tanto (G1 ≡ G2).

Gráficos planos

Se dice que una gráfica ‘G’ es plana si se puede dibujar en un plano o una esfera de modo que no se crucen dos aristas en un punto que no sea vértice.

Ejemplo

Gráficos planos

Regiones

Cada gráfico plano divide el plano en áreas conectadas llamadas regiones.

Ejemplo

Regiones

Grado de una región acotada r = grados (r) = Número de aristas que encierran las regiones r.

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

Región ilimitada

Grado de una región ilimitada r = grados (r) = Número de aristas que encierran las regiones r.

deg(R1) = 4
deg(R2) = 6

En gráficos planos, las siguientes propiedades son válidas:

En un gráfico plano con ‘n’ vértices, la suma de grados de todos los vértices es –

n Σ i = 1 grado (VI) = 2 | E |

De acuerdo a Suma de grados de regiones/ Teorema, en un gráfico plano con ‘n’ regiones, la suma de grados de regiones es –

n Σ i = 1 grado (ri) = 2 | E |

Basado en el teorema anterior, puede sacar las siguientes conclusiones:

En un gráfico plano,

Si el grado de cada región es K, entonces la suma de los grados de las regiones es –

K | R | = 2 | E |

Si el grado de cada región es al menos K (≥ K), entonces

K | R | ≤ 2 | E |

Si el grado de cada región es como máximo K (≤ K), entonces

K | R | ≥ 2 | E |

Nota – Suponga que todas las regiones tienen el mismo grado.

De acuerdo a Fórmulas de Euler en gráficos planos,

Si un gráfico ‘G’ es un plano conectado, entonces

| V | + | R | = | E | + 2

Si es un gráfico plano con componentes ‘K’, entonces

| V | + | R | = | E | + (K + 1)

Donde, | V | es el número de vértices, | E | es el número de aristas y | R | es el número de regiones.

Desigualdad de vértice de borde

Si ‘G’ es un gráfico plano conectado con el grado de cada región al menos ‘K’ entonces,

| E | ≤ k / (k-2) {| v | – 2}

Ya sabes, | V | + | R | = | E | + 2

K. | R | ≤ 2 | E |

K (| E | – | V | + 2) ≤ 2 | E |

(K – 2) | E | ≤ K (| V | – 2)

| E | ≤ k / (k-2) {| v | – 2}

Si ‘G’ es un gráfico plano simple conectado, entonces

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

Existe al menos un vértice V • ∈ G, tal que deg (V) ≤ 5.

Si ‘G’ es un gráfico plano simple conectado (con al menos 2 aristas) y sin triángulos, entonces

|E| ≤ {2|V| – 4}

Teorema de Kuratowski

Un gráfico ‘G’ no es plano si y solo si ‘G’ tiene un subgráfico que es homeomorfo a K5 o K3,3.

Homomorfismo

Dos gráficos G1 y G2 se dice que son homomórficos, si cada uno de estos gráficos se puede obtener del mismo gráfico ‘G’ dividiendo algunas aristas de G con más vértices. Eche un vistazo al siguiente ejemplo:

Homomorfismo

Divida la arista ‘rs’ en dos aristas agregando un vértice.

Un vértice

Los gráficos que se muestran a continuación son homomórficos al primer gráfico.

Gráfico completo

Si G1 es isomorfo a G2, entonces G es homeomorfo a G2 pero no es necesario que lo contrario sea cierto.

  • Cualquier gráfico con 4 vértices o menos es plano.

  • Cualquier gráfico con 8 aristas o menos es plano.

  • Un gráfico completo Knorte es plano si y solo si n ≤ 4.

  • El gráfico bipartito completo Km, n es plano si y solo si m ≤ 2 o n ≤ 2.

  • Un gráfico no plano simple con un número mínimo de vértices es el gráfico completo K5.

  • El gráfico no plano simple con un número mínimo de aristas es K3, 3.

Gráfico poliédrico

Una gráfica plana simple conectada se llama gráfica poliédrica si el grado de cada vértice es ≥ 3, es decir, grados (V) ≥ 3 ∀ V ∈ G.

  • 3 | V | ≤ 2 | E |

  • 3 | R | ≤ 2 | E |

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Página no encontrada – Informatique Mania

apple touch icon@2

bytecode – ¿Puede «compilar» código PHP y cargar un archivo binario, que será ejecutado por el intérprete de código de bytes?