Copyright HébergementWebs.com - License GPL

Teoría de grafos - Isomorfismo

Tutorial de teoría de grafos   2020-11-18 03:46:36

Teoria de grafos - Isomorfismo Un grafo puede existir en diferentes formas con el mismo numero de vertices, aristas y tambien la misma conectividad de borde. Estos graficos se denominan graficos isomorfos. Tenga en cuenta que en este capitulo etiquetamos los graficos principalmente con el proposito de hacer referencia a los demas y reconocerlos. Graficos isomorficos Se dice que dos graficos G 1 y G 2 son isomorfos si - Su numero de componentes (vertices y aristas) es el mismo. Se conserva su conectividad periferica. Nota - En resumen, de los dos graficos isomorfos, uno es una version modificada del otro. Un grafico sin etiquetar tambien se puede considerar un grafico isomorfo. Existe una funcion "f " desde los vertices de G 1 a los vertices de G 2 [f: V (G 1 ) ⇒ V (G 2 )], como en el caso (i): f es una biyeccion (tanto segura como activa). (ii): f conserva la contiguidad de los vertices, es decir, si el borde {U, V} ∈ G 1 , entonces el borde {f (U) , f (V)} ∈ G 2 , luego G 1 ≡ G 2 . Nota Si G 1 ≡ G 2 entonces - | V (G 1 ) | = | V (G 2 ) | | E (G 1 ) | = | E (G 2 ) | Las secuencias de grados de G 1 y G 2 son identicas. Si los vertices {V 1 , V 2 , .. Vk} forman un ciclo de longitud K en G 1 , entonces los vertices {f (V 1 ), f (V 2 ),… f (Vk)} deben formar un ciclo de longitud K en G 2 . Todas las condiciones anteriores son necesarias para que los graficos G 1 y G 2 sean isomorfos, pero no suficientestes para demostrar que las graficas son isomorfas. (G 1 ≡ G 2 ) si y solo si (G 1 - ≡ G 2 -) donde G 1 y G 2 son graficos simples. (G 1 ≡ G 2 ) si las matrices de adyacencia de G 1 y G 2 son identicos. (G 1 ≡ G 2 ) si y solo si los subgrafos correspondientes de G 1 y G 2 (obtenidos al eliminar ciertos vertices de G1 y sus imagenes en el grafico G 2 ) son isomorfos. Ejemplo ¿Cual de los siguientes graficos es isomorfo? En el grafico G 3 , el vertice "w " n "tiene solo grado 3, mientras que todos los demas vertices del grafico tienen grado 2. Entonces G3 n " no es isomorfo a G 1 o G 2 . Complementos de G 1 y G 2 , tienes - Aqui, (G 1 - ≡ G 2 -), entonces (G 1 ≡ G 2 ). Graficos planar Se dice que un grafico "G " es plano si se puede dibujar en un plano o una esfera de modo que ninguna arista se cruce en un punto que no sea vertice. Ejemplo Regiones Cada grafico de plano Ejemplo Grado de una region acotada r = deg (r) = Numero de bordes que rodean r regiones. grado (1) = 3 grados (2) = 4 grados (3) = 4 grados (4) = 3 grados (5) = 8 Grado de region ilimitada r = deg (r) = Numero de bordes que rodean r regiones. deg (R 1 ) = 4 deg (R 2 ) = 6 En los graficos planos, las siguientes propiedades son validas: En un grafico plano con "n " vertices, la suma de grados de todos los vertices es - n Σ i = 1 deg (V i ) = 2 | E | Segun Suma de grados de regiones / Teorema, en un grafico plano con "n " regiones, la suma de grados de regiones es - n Σ i = 1 grado (ri) = 2 | E | Basandose en el teorema anterior, puede sacar las siguientes conclusiones: En un grafico plano, Si el grado de cada region es K, entonces la suma de los grados de las regiones es - K | R | = 2 | E | Si el grado de cada region es al menos K (≥ K), entonces K | R | ≤ 2 | E | Si el grado de cada region es como maximo K (≤ K), entonces K | R | ≥ 2 | E | Nota : suponga que todas las regiones tienen el mismo grado. De acuerdo con las formulas de Euler en graficos planosnaries, Si un grafico "G " es un plano conectado, entonces | V | + | R | = | E | + 2 Si es un grafico plano con componentes "K", entonces | V | + | R | = | E | + (K + 1) Donde, | V | es el numero de vertices, | E | es el numero de aristas y | R | es el numero de regiones. Desigualdad del vertice del borde Si "G " es un grafico plano conectado con el grado de cada region 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 grafico plano conectado simple, | E | ≤ 3 | V | - 6 | R | ≤ 2 | V | - 4 Existe al menos un vertice V • ∈ G, tal que deg (V) ≤ 5. Si "G " es un grafico plano simple conectado (con por lo menos 2 aristas) y sin triangulos, asi que | E | ≤ {2 | V | - 4} Teorema de Kuratowski Un grafico "G " no es plano si y solo si "G " tiene un subgrafo que es homeomorfo a K 5 o K 3, 3 . Homomorfismo Se dice que dos graficos G 1 y G 2 son homomorficos, si cada uno de estos graficos se puede obtener de del mismo grafico "G" Divida el borde "rs " en dos bordes agregando un vertice. Los siguientes graficos son homomorficos al primer grafico. Si G 1 es isomorfo a G 2 , luego G es homeomorfo a G2 pero no es necesario que lo contrario sea cierto. Cualquier grafico con 4 o menos vertices es plano. Cualquier graficophe con 8 aristas o menos es plano. Un grafico completo K n es plano si y solo si n ≤ 4. El grafico bipartito completo K m, n es plano si y solo si m ≤ 2 o n ≤ 2. Un grafico no plano simple con el numero minimo de vertices es el grafico completo K 5 . El grafico no plano simple con un numero minimo de aristas es K 3, 3 . Grafo poliedrico Un grafo plano simple conectado se llama grafo poliedrico si el grado de cada vertice es ≥ 3, es decir, grados (V) ≥ 3 ∀ V ∈ G. 3 | V | ≤ 2 | E | 3 | R | ≤ 2 | E |