UNIDAD 5 Teoría de Grafos.

 Blog_  Elementos, Características y Componentes de los Gráficos.


Los gráficos  son estructuras matemáticas fundamentales en las matemáticas discretas que modelan relaciones entre objetos, Son utilizados en computación, en ingeniería, la biología y las ciencias sociales para resolver problemas de redes, rutas, optimización y más.

1. Elementos, Características y Componentes de los Grafos.

Un grafos está compuesto por un conjunto de vértices (también llamados nodos) y aristas (también llamadas arcos o enlaces) que conectan los vértices.
Un grafo se denota como común GRAMO = ( V , mi ) G = (V, E) , donde:

  • V V : Es el conjunto de vértices.
  • mi mi : Es el conjunto de aristas que conectan pares de vértices.

Componentes básicos:

  1. Vértices ( V V ):Representan los objetos o puntos de la red.
  2. Aristas ( mi mi ):Representan las conexiones entre vértices. Pueden ser:
    • No dirigidas: Conexiones bidireccionales. Ejemplo: una amistad en redes sociales.
    • Dirigidas: Conexiones unidireccionales. Ejemplo: el seguimiento en Twitter.
  3. Peso: Los aristas pueden tener un peso asociado, que representa costos, distancias o capacidades.

Características de los Gráficos:

  • Grado de un vértice: Número de aristas que inciden en un vértice.
  • Caminos y circuitos: Un camino es una secuencia de vértices conectados por aristas, mientras que un circuito es un camino cerrado.
  • Conectividad: Un grafo es conexo si existe al menos un camino entre cada par de vértices.

Tipos de grafos:

  • Grafo simple: No tiene bucles (aristas que conectan un vértice consigo mismo) ni múltiples aristas entre los mismos vértices.
  • Grafo ponderado: Sus aristas tienen pesos.
  • Grafo dirigido (dígrafo): Los aristas tienen una dirección.
  • Gráfico completo: Todos los vértices están conectados entre sí.
  • Grafo bipartito: Sus vértices pueden dividirse en dos subconjuntos, y las aristas solo conectan vértices de diferentes subconjuntos.

Representación de los Grafos

La forma en que se representan los gráficos depende de su estructura y del problema que se quiera resolver. Las principales representaciones son:

a. Matriz de Adyacencia

Es una matriz cuadrada A A de tamaño norte × norte n \veces n (donde norte norte es el número de vértices).

  • Si hay una arista entre el vértice i i y el vértice yo yo , A [ i ] [ yo ] = 1 A[i][j] = 1 ; en caso contrario, A [ i ] [ yo ] = 0 A[i][j] = 0 .
  • En un grafo ponderado, A [ i ] [ yo ] A[i][j] contiene el peso de la arista.

Ejemplo para un gráfico con 3 vértices ( V = { 1 , 2 , 3 } V = \{1, 2, 3\} ):

A = [ 0 1 0 1 0 1 0 1 0 ] A = \begin{bmatrix} 0 y 1 y 0 \\ 1 y 0 y 1 \\ 0 y 1 y 0 \end{bmatrix}

b. Lista de Adyacencia

Consiste en un arreglo o lista donde cada posición corresponde a un vértice y almacena una lista de los vértices a los que está conectado.
Ejemplo:

  • Vértice 1: [2]
  • Vértice 2: [1, 3]
  • Vértice 3: [2]

Esta representación es eficiente para gráficos dispersos.

c. Lista de artistas

Se enumeran todas las aristas en forma de pares de vértices.
Ejemplo:

mi = { ( 1 , 2 ) , ( 2 , 3 ) } mi = \{(1, 2), (2, 3)\}

 Algoritmos de Recorrido y Búsqueda.

Existen diversos algoritmos que permiten explorar o buscar en un gráfico. Los dos más comunes son:

a. Algoritmo de Búsqueda en Profundidad (DFS - Depth First Search)

El DFS explora tan lejos como sea posible a lo largo de cada rama antes de retroceder.

Pasos del algoritmo:

  1. Comienza en un vértice inicial y marca ese vértice como visitado.
  2. Explora recursivamente los vértices adyacentes no visitados.
  3. Retrocede cuando no hay más vértices por explorar.

Resultado de la aplicación:
El DFS se utiliza para detectar ciclos, encontrar componentes conectados y resolver problemas de laberintos.

b. Algoritmo de Búsqueda en Amplitud (BFS - Breadth First Search)

El BFS explora un gráfico nivel por nivel, visitando primero todos los vecinos de un vértice antes de pasar a los vecinos de los vecinos.

ejemplos de pasos del algoritmo:

  1. Comienza en un vértice inicial, lo marca como visitado y lo encola.
  2. Mientras la cola no esté vacía, extrae un vértice de la cola y visita a sus vecinos no visitados, agregándolos a la cola.

Aplicación:
El BFS se utiliza para encontrar caminos más cortos, explorar redes sociales y modelar propagación de información.

Ejemplos de DFS y BFS:

Para un grafo:

V = { A , B , hacer , D } ,mi = { ( A , B ) , ( A , hacer ) , ( B , D ) , ( hacer , D ) } V = \{A, B, C, D\}, \quad E = \{(A, B), (A, C), (B, D), (C, D)\}
  • DFS desde A: A → B → D → hacer A \a B \a D \a C
  • BFS desde A: A → B → do → D A \a B \a C \a D
¡¡¡terminado!!


Comments

Post a Comment

Popular posts from this blog

UNIDA 6 ARBOLES Y REDES

Image
  Blog: Árbol y Redes en Matemáticas Discretas Los árboles y las redes son estructuras fundamentales en las matemáticas discretas y tiene aplicaciones en computación, ingeniería.  Árboles Un árbol es un tipo especial de grafo que cumple con las siguientes características: Es un grafo conexo (existe al menos un camino entre cualquier par de vértices). No contiene ciclos (no hay caminos cerrados). En términos más formales, un árbol es un gráfico. yo = ( V , mi ) T = (V, E) tú = ( V , E ) donde: ∣ mi ∣ = ∣ V ∣ − 1 |E| = |V| - 1 ∣ Yo ∣ = ∣ V ∣ − 1 donde V es el conjunto de vértices y mi  conjunto de artistas. Características de los Árboles: Raíz: En un árbol dirigido, un vértice especial (la raíz) actúa como punto de inicio. Hojas: Son los vértices que no tienen hijos (vértices descendientes). Altura del árbol: Es la longitud del camino más largo desde la raíz hasta una hoja. Grado: El número de hijos de un vértice.   Ejemplo de Árbol: Un árbol simple con nu...
Read more

UNIDAD 3 LOGICA MATEMATICA.

 BLOG UNIDAD 3 LÓGICA MATEMÁTICA La lógica matemática es el lenguaje universal de las matemáticas discretas y, en general, de la computación. Desde el razonamiento deductivo hasta la demostración de propiedades, los conceptos como la lógica proposicional , la lógica de predicado , el álgebra declarativa y la inducción matemática tienen aplicaciones prácticas y profundas en el desarrollo de sistemas computacionales.  Lógica Proposicional:  La lógica proposicional es el primer paso en la lógica formal. Aquí trabajamos con proposiciones , que son declaraciones que pueden ser verdaderas o falsas, pero no ambas. Ejemplo de proposición: "El cielo es azul." (Verdadero) "5 es mayor que 10." (Falso) Operadores lógicos básicos: Negación ( ¬ pag \neg p ¬ p ): Cambia el valor de verdad de la proposición. Conjunción ( pag ∧ q p \ tierra q página ∧ q ): Es verdadero solo si pag pag p y q q q son verdaderas. Desilusión ( pag ∨ q p\lor q página ∨ q ): Es verdadera ...
Read more

UNIDAD 5 REPRESENTACION, ALGORITMO DE GRAFO

 BLOG UNIDAD 5 REPRESENTACION, ALGORITMOS DE GRAFO  Los gráfos son estructuras matemáticas que se utilizan para modelar relaciones y conexiones entre objetos. son lo mas importante en las matemáticas discretas debido que a su amplia aplicación en áreas como algoritmos o redes eh inteligencia artificial.   ¿Qué es un Grafo? Un grafo  se define como un par ordenado: GRAMO = ( V , mi ) , G = (V, E), GRAMO = ( V , mi ) , Dónde: V V V : Conjunto de vértices o nodos ( ∣ V ∣ = norte |V| = n ∣ V ∣ = (n ). mi mi E : Conjunto de aristas o conexiones entre pares de vértices ( ∣ mi ∣ = metro |E| = m ∣ Yo ∣ = m ). Los grafos pueden ser: Dirigidos: Los aristas tienen dirección (ej. un gráfico que representa seguidores en redes sociales). No dirigidos: Las aristas no tienen dirección (ej. una red de carreteras).  Tipos de Representación de Gráficos Matriz de Adyacencia Es una matriz cuadrada de tamaño norte × norte n \veces n norte × n , donde norte = ∣ V ∣ n = |V...
Read more