En el campo matemático de la teoría de grafos, una subdivisión de aristas también llamada subdivisión elemental, subdivisión de grafos[1] o simplemente subdivisión es una operación que agrega un vértice a una arista, dividiendo la arista en dos (•——• por •—•—•). La contracción es una operación fundamental en la teoría de grafos.
Subdivisión
subdivisión de la arista uv en las aristas uw y wv
La operación de subdivisión de aristas toma un arista e = uv, luego un vértice w es agregado a la arista, dividiéndola en dos, de esta forma la arista original es reemplazada por e1 = uw y e2 = wv, de modo que se añade al grafo un vértice y una arista.
Más generalmente, la operación de subdivisión puede añadir un conjunto de vértices a una arista, dividiendo la arista y añadiendo un grafo camino Pn al grafo. La subdivisión se puede realizar en más de una arista a la vez.
Definición formal
Sea un grafo simple conexo, la subdivisión de la arista da como resultado el grafo , donde y [2]
donde w sería el vértice que se inserta en la arista.
Operación inversa
La operación inversa, suavizado o alisado de un grafo, un vértice w es eliminado de un par de aristas (e,f) que son incidentes a w, se elimina las aristas incidentes a w y se reemplaza por una nueva arista con los vértices extremos de e y f que no son w. Esta operación se puede hacer únicamente con vértices de grado 2.
Por ejemplo, el grafo G simple conexo con dos aristas e1 = uw y e2 = wv:
subdivisión, grafos, campo, matemático, teoría, grafos, subdivisión, aristas, también, llamada, subdivisión, elemental, subdivisión, grafos, simplemente, subdivisión, operación, agrega, vértice, arista, dividiendo, arista, contracción, operación, fundamental, . En el campo matematico de la teoria de grafos una subdivision de aristas tambien llamada subdivision elemental subdivision de grafos 1 o simplemente subdivision es una operacion que agrega un vertice a una arista dividiendo la arista en dos por La contraccion es una operacion fundamental en la teoria de grafos Subdivisionsubdivision de la arista uv en las aristas uw y wv La operacion de subdivision de aristas toma un arista e uv luego un vertice w es agregado a la arista dividiendola en dos de esta forma la arista original es reemplazada por e1 uw y e2 wv de modo que se anade al grafo un vertice y una arista Mas generalmente la operacion de subdivision puede anadir un conjunto de vertices a una arista dividiendo la arista y anadiendo un grafo camino Pn al grafo La subdivision se puede realizar en mas de una arista a la vez Indice 1 Definicion formal 2 Operacion inversa 3 Vease tambien 4 ReferenciasDefinicion formal EditarSea G V A displaystyle G V A un grafo simple conexo la subdivision de la arista u v A displaystyle u v in A da como resultado el grafo G w V A displaystyle G w V A donde V V w displaystyle V V cup w y A A u v u w v w displaystyle A A u v cup u w v w 2 donde w seria el vertice que se inserta en la arista Operacion inversa EditarLa operacion inversa suavizado o alisado de un grafo un vertice w es eliminado de un par de aristas e f que son incidentes a w se elimina las aristas incidentes a w y se reemplaza por una nueva arista con los vertices extremos de e y f que no son w Esta operacion se puede hacer unicamente con vertices de grado 2 Por ejemplo el grafo G simple conexo con dos aristas e1 uw y e2 wv tiene un vertice w que es alisado resultando Vease tambien EditarHomeomorfismo de grafos Anexo Operaciones en grafosReferencias Editar http scik org index php eml article view 154 54 http www math uchicago edu may VIGRE VIGRE2006 PAPERS Weiner pdf Datos Q6134791Obtenido de https es wikipedia org w index php title Subdivision grafos amp oldid 137277439, wikipedia, wiki, leyendo, leer, libro, biblioteca,
