{"id":53902,"date":"2024-08-29T18:52:00","date_gmt":"2024-08-29T23:52:00","guid":{"rendered":"https:\/\/niixer.com\/?p=53902"},"modified":"2024-09-11T14:47:15","modified_gmt":"2024-09-11T19:47:15","slug":"teoria-de-las-graficas","status":"publish","type":"post","link":"https:\/\/niixer.com\/index.php\/2024\/08\/29\/teoria-de-las-graficas\/","title":{"rendered":"Teor\u00eda de las gr\u00e1ficas"},"content":{"rendered":"\n

\u00bfQu\u00e9 es la teor\u00eda de las gr\u00e1ficas?, es una rama de las matem\u00e1ticas discretas que ha ido teniendo un gran avance en los \u00faltimos a\u00f1os gracias a que es una herramienta muy \u00fatil y eficaz, logrando as\u00ed ser utilizada en otras \u00e1reas como la qu\u00edmica<\/a>, ciencias sociales, ling\u00fc\u00edstica, f\u00edsica y otras; jugando adem\u00e1s un papel muy importante en el \u00e1rea de la ciencia de la computaci\u00f3n. En nuestra vida cotidiana tambi\u00e9n utilizamos inconscientemente esta teor\u00eda, algunos ejemplos claros los podr\u00edamos identificar en el modelado de redes sociales<\/a>, de transporte, el\u00e9ctricas, moleculares, etc.<\/p>\n\n\n\n

En este articulo tendr\u00e9 como prop\u00f3sito dar a conocer la teor\u00eda de las gr\u00e1ficas, bas\u00e1ndome en los conceptos clave y tomando teoremas fundamentales para entender y aplicar esta teor\u00eda.<\/p>\n\n\n\n

<\/p>\n\n\n\n

CONCEPTOS CLAVE Y RESULTADOS INICIALES<\/strong><\/h3>\n\n\n\n

El problema de los Puentes de K\u00f6nigsberg<\/a>: surgi\u00f3 en la actual cuidad de Kaliningrado en el siglo XVIII, que ten\u00eda dos islas conectadas a la orilla por siete puentes. La pregunta era si se pod\u00eda caminar por la ciudad pasando por cada puente una vez y regresar al principio. En 1739 Leonhard Euler<\/a> resolvi\u00f3 el problema dibujando la situaci\u00f3n con una gr\u00e1fica, los lugares representando v\u00e9rtices y los puentes representando aristas. Euler demostr\u00f3 que en vista de que la gr\u00e1fica ten\u00eda v\u00e9rtices con grados impares, un trayecto que pasara por cada puente una vez y regresara al principio no era posible. <\/p>\n\n\n\n

 El resultado de Euler propuso conceptos fundamentales en la teor\u00eda de las gr\u00e1ficas, como la importancia de los grados de los v\u00e9rtices en los recorridos y sent\u00f3 bases para el desarrollo de las matem\u00e1ticas. <\/p>\n\n\n\n

\"grafica<\/figure>\n\n\n\n

<\/p>\n\n\n\n

GR\u00c1FICAS <\/strong>: <\/strong><\/h4>\n\n\n\n

Es una estructura matem\u00e1tica que representa las conexiones y relaciones entre objetos. Dos ordenadas G=(V,E), que crea una gr\u00e1fica, donde: <\/p>\n\n\n\n

-Se le llama V a un conjunto de v\u00e9rtices (o nodos), que representan los objetos o entidades. <\/p>\n\n\n\n

-Se le denomina E es un conjunto de aristas (o enlaces), que representan las conexiones o relaciones entre los v\u00e9rtices. <\/p>\n\n\n\n

–Subgr\u00e1fiacas<\/strong>: si el conjunto de los v\u00e9rtices de G es un subconjunto de los v\u00e9rtices de G y el conjunto de las aristas de G es subconjunto de las aristas de G, una gr\u00e1fica G\u2019 seria una subgrafica de G.  <\/p>\n\n\n\n

-Isomorfismos<\/strong>: es una conexi\u00f3n que define una igualdad estructural entre dos gr\u00e1ficas. Si dos gr\u00e1ficos tienen la misma estructura, es decir, si se pueden asimilar iguales desde el punto de vista donde se conectan, se consideran isomorfos, sin embargo, los nombres de los v\u00e9rtices y etiquetas de las aristas pueden variar. Permite reconocer y ordenar las gr\u00e1ficas con la misma estructura subyacente. <\/p>\n\n\n\n

-Conexas<\/strong>: la familia de las gr\u00e1ficas conexas es una de las m\u00e1s importantes en este concepto. Decimos que, si existe una trayectoria uv en G, dos nodos u y v de una gr\u00e1fica G est\u00e1n conectados. Si para todo par de v\u00e9rtices o nodos u y v de la gr\u00e1fica G existe una trayectoria uv, es decir, si u y v estan conectados la gr\u00e1fica va a ser conexa. Si H no aparece en ninguna subgr\u00e1fica conexa de G con m\u00e1s v\u00e9rtices o m\u00e1s aristas que H, diremos que H es una componente conexa de G. <\/p>\n\n\n\n

-Bipartitas<\/strong>: si se encuentran dos conjuntos A y B de los v\u00e9rtices de una gr\u00e1fica G de manera que:  <\/p>\n\n\n\n

A \u222aB = V (G). Si uv pertenece a E(G), U pertenece a A y V a B. <\/p>\n\n\n\n

<\/p>\n\n\n\n

DIGR\u00c1FICAS:<\/strong><\/h4>\n\n\n\n

Si consideramos flechas en vez de aristas, Una digr\u00e1fica se puede entender a partir de una gr\u00e1fica. En otras palabras, una digrafica D es una estructura formada por V (D) un conjunto de v\u00e9rtices y F(D) un conjunto de parees ordenaos de V(D) conocidos como flechas o arcos. Hay que tener en cuenta que cunado consideramos pares ordenados, asignamos una direcci\u00f3n a la flecha. Si queda claro que estamos hablando de las flechas de una digrafica, indicaremos como uv para un par ordenado (u, v) en F(D).  <\/p>\n\n\n\n

<\/p>\n\n\n\n

\u00c1RBOLES Y SUS APLICACIONES EN GR\u00c1FICAS<\/strong><\/h3>\n\n\n\n

Un \u00e1rbol es una gr\u00e1fica conexa sin ciclos.<\/p>\n\n\n\n

Se presentaron por Arthur Cayley<\/a> para contar estructuras qu\u00edmicas y se consideraron estructuras matem\u00e1ticas en la teor\u00eda de las gr\u00e1ficas. Las leyes Kirchhoff fueron creadas por Gustav Kirchhoff<\/a> y se aplicaron a las redes el\u00e9ctricas, la qu\u00edmica molecular y las ciencias de la computaci\u00f3n, depende principalmente para dise\u00f1ar algoritmos y estructuras de datos. <\/p>\n\n\n\n

Mientras que los \u00e1rboles se pueden expresar con arreglos y matrices, la ilustraci\u00f3n din\u00e1mica con almacenaje unido es m\u00e1s com\u00fan en computaci\u00f3n porque es m\u00e1s f\u00e1cil insertar y eliminar v\u00e9rtices. <\/p>\n\n\n\n

Por su facilidad de uso, se enfoca en los \u00e1rboles binarios. Cualquier \u00e1rbol general puede transformarse en un \u00e1rbol binario equivalente. Adem\u00e1s, la eliminaci\u00f3n de v\u00e9rtices o aristas tiene un impacto en la uni\u00f3n de una gr\u00e1fica, con ejemplos de gr\u00e1ficas cuya conexidad no cambia al eliminar ciertos <\/p>\n\n\n\n

<\/p>\n\n\n\n

RECORRIDOS EN GR\u00c1FICAS<\/strong><\/h3>\n\n\n\n

Muchos problemas de este tipo pueden mostrarse a trav\u00e9s de gr\u00e1ficas, y las soluciones a estos problemas dan lugar a dos familias importantes de gr\u00e1ficas: las gr\u00e1ficas Eulerianas y Hamiltonianas. <\/p>\n\n\n\n

<\/p>\n\n\n\n

Gr\u00e1ficas Eulerianas:<\/strong><\/h4>\n\n\n\n

Es una gr\u00e1fica que le permite recorrer todas sus aristas solamente una vez. La idea proviene del problema de los Puentes de K\u00f6nigsberg que mencione anteriormente, el juego de dibujar la firma del diablo que representa los conceptos de los caminos y ciclos eulerianos. Es una forma de entrar a la familia de las gr\u00e1ficas eulerianas. Consiste en dibujar una figura compleja sin levantar el l\u00e1piz ni trazar una l\u00ednea dos veces, el recorrido es posible Si la gr\u00e1fica asociada cumple con las condiciones mencionadas. <\/p>\n\n\n\n

\"grafica<\/figure>\n\n\n\n

 <\/p>\n\n\n\n

<\/p>\n\n\n\n

Gr\u00e1ficas hamiltonianas:<\/strong><\/h4>\n\n\n\n

Son aquellas que tienen un ciclo que visita cada v\u00e9rtice una vez y luego regresa al punto de partida. El Juego Icosian<\/a> que se juega sobre un dodecaedro<\/a> regular, con cada v\u00e9rtice representando una ciudad europea dio lugar a la idea. El objetivo es descubrir un camino que recorra todas las ciudades (v\u00e9rtices) una vez y regrese al punto de inicio. Este problema demuestra la necesidad de encontrar un ciclo hamiltoniano en la gr\u00e1fica que corresponde al dodecaedro. <\/p>\n\n\n\n

<\/p>\n\n\n\n

PLANARIDAD Y CONEXIDAD<\/strong><\/h3>\n\n\n\n

Planaridad<\/strong>: <\/h4>\n\n\n\n

El termino se refiere a la capacidad de una gr\u00e1fica para dibujar\u00a0en un plano sin puntos de encuentros de aristas<\/a>. Los grafos planos son importantes\u00a0para el dise\u00f1o de redes y circuitos f\u00edsicos. Para determinar si una gr\u00e1fica es plana es bueno tener en cuenta las siguientes observaciones:\u00a0<\/p>\n\n\n\n

1. Toda subgr\u00e1fica de G es plana si G es una gr\u00e1fica plana.  <\/p>\n\n\n\n

2. Si la subgr\u00e1fica de G no es plana. Como resultado, G no es plana. <\/p>\n\n\n\n

<\/p>\n\n\n\n

Conexidad<\/strong>:<\/h4>\n\n\n\n

Indica si una gr\u00e1fica est\u00e1 completamente interconectada, lo que significa que hay caminos entre los pares de v\u00e9rtices. Es importante en redes de comunicaci\u00f3n y transporte para asegurar la redundancia y la accesibilidad. <\/p>\n\n\n\n

En la teor\u00eda de las gr\u00e1ficas ambos conceptos son\u00a0fundamentales para\u00a0poder resolver problemas y tienen aplicaciones pr\u00e1cticas en campos como en \u00e1reas que van desde el dise\u00f1o de redes hasta y la planificaci\u00f3n de circuitos.<\/a>\u00a0<\/p>\n\n\n\n

<\/p>\n\n\n\n

COLORACIONES DE GR\u00c1FICAS<\/strong><\/h3>\n\n\n\n

El problema de coloraci\u00f3n en teor\u00eda de las graficas, se centra en asignar colores a los v\u00e9rtices o aristas de una gr\u00e1fica para cumplir ciertas condiciones.<\/p>\n\n\n\n

Hace m\u00e1s de cien a\u00f1os se debati\u00f3 el problema de los cuatro colores. En 1852 Augustus de Morgan<\/a> le pregunt\u00f3 a Sir William Hamilton<\/a> por qu\u00e9 un mapa puede ser coloreado con cuatro colores para que dos regiones cercanas no compartan el mismo color. Al convertir el mapa en una gr\u00e1fica plana, donde cada regi\u00f3n es un v\u00e9rtice y cada frontera compartida es una arista la teor\u00eda de las gr\u00e1ficas nos ayuda a entender este problema. Actualmente se cree que cualquier gr\u00e1fica plana puede ser coloreada con cuatro colores de manera que ning\u00fan v\u00e9rtice cercano comparta el mismo color. <\/p>\n\n\n\n

\"coloraciones<\/figure>\n\n\n\n

<\/p>\n\n\n\n

Coloraci\u00f3n de v\u00e9rtices<\/strong>:<\/h4>\n\n\n\n

Se trata de asignar colores a los v\u00e9rtices de una gr\u00e1fica para que los v\u00e9rtices que est\u00e1n cerca tengan colores diferentes. El n\u00famero m\u00ednimo de colores necesarios para lograr esto es uno colorido. La teor\u00eda incluye teoremas importantes, como el de los cuatro colores y una variedad de algoritmos para encontrar coloraciones efectivas. En varios campos, como la programaci\u00f3n de horarios, la elecci\u00f3n de frecuencias y el dise\u00f1o de circuitos est\u00e1n t\u00e9cnicas son \u00fatiles.  <\/p>\n\n\n\n

<\/p>\n\n\n\n

Algoritmo Greedy:<\/strong><\/h4>\n\n\n\n

El algoritmo<\/a> Greedy es un m\u00e9todo\u00a0para encontrar aproximadamente la coloraci\u00f3n de los v\u00e9rtices. Funciona seleccionando colores a cada v\u00e9rtice de la gr\u00e1fica uno por uno, eligiendo el primer color disponible para que no cause conflicto con los v\u00e9rtices\u00a0que ya han sido coloreados.\u00a0<\/p>\n\n\n\n

<\/p>\n\n\n\n

Sudoku:<\/strong><\/h4>\n\n\n\n

El Sudoku es un juego en el que los jugadores deben llenar las casillas de una cuadricula de 9 por 9 que se divide en cuadriculas o conocidas tambi\u00e9n como cajas de 3 por 3. para lograrlo, se deben cumplir las siguientes reglas: <\/p>\n\n\n\n

1. los n\u00fameros deben ir del 1 al 9 para llenar cada casilla. <\/p>\n\n\n\n

2. el mismo n\u00famero no puede aparecer dos veces en el mismo rengl\u00f3n.  <\/p>\n\n\n\n

3. el mismo n\u00famero no puede repetirse en la misma columna.  <\/p>\n\n\n\n

4. el mismo n\u00famero no puede volver a colocarse en una caja de 3 por 3.   <\/p>\n\n\n\n

<\/p>\n\n\n\n

Coloraci\u00f3n por Aristas:<\/strong><\/h4>\n\n\n\n

Si se asignan colores a las aristas de la gr\u00e1fica de manera que dos aristas aleda\u00f1as (que comparten un v\u00e9rtice) no tengan el mismo color. <\/p>\n\n\n\n

Diremos que la gr\u00e1fica G= (V, E) tienen una coloraci\u00f3n por aristas.  <\/p>\n\n\n\n

<\/p>\n\n\n\n

Video referencia<\/strong>:<\/h3>\n\n\n\n
\n