Uno de los primeros y más importantes teoremas sobre grafos de línea se debe a Hassler Whitney,[3] quien demostró que, a excepción de un caso especial, la estructura de un grafo conexo G siempre puede ser restablecida completamente a partir de su grafo línea. En otras palabras, con una única excepción, un grafo conexo siempre puede ser obtenido si conocemos las adyacencias de sus aristas (líneas).
Definición formal
Dado un grafo G, su grafo línea L(G) es el grafo que cumple estas dos condiciones:
cada vértice de L(G) representa una arista de G; y
dos vértices de L(G) son adyacentes si y sólo si sus aristas correspondientes comparten un punto final en común (es decir, son adyacentes) en G.
En otras palabras, el grafo línea es el grafo de intersección de las aristas de G, representando cada arista por el conjunto de sus dos puntos finales.
Ejemplo
La siguiente figura muestra un grafo (a la izquierda, con vértices azules) y su grafo línea (derecha, con vértices verdes). Cada vértice del grafo línea está etiquetado con el par de nodos finales de la correspondiente arista en el grafo original. Por ejemplo, el vértice verde en la derecha etiquetado como 1,3 corresponde a la arista de la izquierda entre los vértices azules 1 y 3. El vértice verde 1,3 es adyacente a otros tres vértices verdes: 1,4 y 1,2 (correspondientes a aristas que comparten el nodo final 1 en el grafo azul) y 4,3 (correspondiente a una arista compartiendo el nodo final 3 en el grafo azul).
Whitney, H. (1932), «Congruent graphs and the connectivity of graphs», American Journal of Mathematics54 (1): 150-168, doi:10.2307/2371086.
Enlaces externos
line graphs, Information System on Graph Classes and their Inclusions.
Datos:Q1378376
Febrero 17, 2022
grafo, línea, teoría, grafos, grafo, línea, línea, lineal, representativo, grafo, dirigido, grafo, representa, adyacencias, entre, aristas, nombre, debe, artículo, harary, norman, 1960, aunque, tanto, whitney, 1932, como, krausz, 1943, definieron, antes, prime. En teoria de grafos el grafo linea de linea lineal o representativo 1 L G de un grafo no dirigido G es un grafo que representa las adyacencias entre las aristas de G Su nombre se debe a un articulo de Harary y Norman 1960 aunque tanto Whitney 1932 como Krausz 1943 los definieron antes 2 Uno de los primeros y mas importantes teoremas sobre grafos de linea se debe a Hassler Whitney 3 quien demostro que a excepcion de un caso especial la estructura de un grafo conexo G siempre puede ser restablecida completamente a partir de su grafo linea En otras palabras con una unica excepcion un grafo conexo siempre puede ser obtenido si conocemos las adyacencias de sus aristas lineas Indice 1 Definicion formal 2 Ejemplo 3 Referencias 4 Enlaces externosDefinicion formal EditarDado un grafo G su grafo linea L G es el grafo que cumple estas dos condiciones cada vertice de L G representa una arista de G y dos vertices de L G son adyacentes si y solo si sus aristas correspondientes comparten un punto final en comun es decir son adyacentes en G En otras palabras el grafo linea es el grafo de interseccion de las aristas de G representando cada arista por el conjunto de sus dos puntos finales Ejemplo EditarLa siguiente figura muestra un grafo a la izquierda con vertices azules y su grafo linea derecha con vertices verdes Cada vertice del grafo linea esta etiquetado con el par de nodos finales de la correspondiente arista en el grafo original Por ejemplo el vertice verde en la derecha etiquetado como 1 3 corresponde a la arista de la izquierda entre los vertices azules 1 y 3 El vertice verde 1 3 es adyacente a otros tres vertices verdes 1 4 y 1 2 correspondientes a aristas que comparten el nodo final 1 en el grafo azul y 4 3 correspondiente a una arista compartiendo el nodo final 3 en el grafo azul Grafo G Vertices en L G construidas desde aristas en G Aristas anadidas en L G El grafo linea L G Referencias Editar Hemminger y Beineke 1978 pp 273 Balakrishnan 1997 p 44 Hemminger y Beineke 1978 p 273 Whitney H 1932 Congruent graphs and the connectivity of graphs American Journal of Mathematics 54 1 150 168 doi 10 2307 2371086 Enlaces externos Editarline graphs Information System on Graph Classes and their Inclusions Datos Q1378376 Obtenido de https es wikipedia org w index php title Grafo linea amp oldid 133385850, wikipedia, wiki, leyendo, leer, libro, biblioteca,
