Capitulo 9 - INTRODUCCIÓN Y CONCEPTOS TEORÍA DE GRAFOS

UNIVERSIDAD NACIONAL DE LOJA
FACULTAD DE LA ENERGÍA, LAS INDUSTRIAS Y LOS RECURSOS NATURALES

NO RENOVABLES
MAESTRÍA EN ELECTRICIDAD
MENCIÓN EN SISTEMAS ELÉCTRICOS DE POTENCIA
NOMBRE DE LA ASIGNATURA
TEMA 1: MÉTODOS MATEMÁTICOS DE LA INTELIGENCIA ARTIFICIAL
DOCENTE: ING. RAÚL CUBILLO BETANCOURT, MSc

CORREO: [email protected]
PERIODO: Agosto 2021

TEMA 9: INTRODUCCIÓN Y CONCEPTOS TEORIA DE GRAFOS
1. Procesos estocásticos
2. Probabilidades de Transición
3. Aplicación de la Probabilidad como Matriz de Transición
4. Clasificación de Estados
• https://www.dmae.upct.es/~mcruiz/Telem06/Teoria/apuntes_procesos.pdf
• https://lya.fciencias.unam.mx/lars/libros/procesos2012.pdf
9. INTRODUCCIÓN TEORIA DE GRAFOS
NOCIONES BÁSICAS
Un grafo de manera general se podría definir como un conjunto de puntos (llamados elementos, vértices,
nudos o nodos) con líneas que unen pares de vértice de ellas.
DEFINICIÓN
Grafo es una abstracción matemática que designaremos por G= (V, A) donde V es un conjunto de puntos 𝑣𝑖 ,
𝑉 ≠ ∅ 𝑦 𝑨 es un conjunto de líneas que unen dos puntos de V; A puede ser ∅, llamado conjunto de las aristas, y que
están relacionados mediante una función T.
𝑉 = 𝑣1 , 𝑣2 , … , 𝑣𝑛
𝐴= 𝑣1 , 𝑣1 , 𝑣1 , 𝑣2 , 𝑣1 , 𝑣3 , … 𝑣1 , 𝑣𝑘 , … 𝑣𝑛 , 𝑣𝑘 , … 𝑣𝑘 , 𝑣𝑘 = 𝑎1 , 𝑎2 , … , 𝑎𝑘 , … 𝑎𝑘
𝑇: 𝑉 → 𝐴; 𝑣1 → 𝑣𝑗
NODO 𝑣𝑖
A
ARISTA (a)
B D
CAMINO
Denominamos camino a una sucesión de
nodos unidos por aristas de forma que no se
C repite ninguna arista
GRAFO NO CONEXO GRAFO CONEXO
GRADO DE
CIRCUITO INCIDENCIA
Es un camino que Es el número de aristas que
empieza y termina en el inciden en dicho nodo.
mismo nodo sin repetir
ninguna arista.
ÁRBOL
Existe un tipo de grafos especiales denominados Árboles, que suelen ser utilizados
para representar esquemas de toma de decisiones.
Dado un grafo G = (V, E) se dice que es un árbol si verifica las siguientes condiciones:
• Es conexo
NODO
• No tiene circuitos. RAÍZ
Al nodo situado en el extremo

superior se le denomina Nodo
Raíz y a los nodos situados en la
parte inferior se le denomina
Nodos Terminales.
1 2 3
NODO
TERMINAL
9. INTRODUCCIÓN PROCESOS ESTOCASTICOS
INTRODUCCION A PROCESOS ESTOCASTICOS
• La teoría de los procesos estocásticos se centra en el estudio y modelización de sistemas que
evolucionan a lo largo del tiempo, o del espacio, de acuerdo a unas leyes no determinísticas,
esto es, de carácter aleatorio
• La forma habitual de describir la evolución de un sistema es mediante sucesiones o colecciones
de variables aleatorias.
una sucesión de v.a.
donde el subíndice indica el instante de tiempo Refleja el concepto de proceso estocástico
• En términos mucho más sencillos, un proceso estocástico es aquel que no se puede predecir, se
mueve “ puede ir” y su movimiento es al azar
INTRODUCCIÓN A PROCESOS ESTOCÁSTICOS

EJEMPLO CONJUNTO DE ESTADOS

Se lanza una moneda varias veces. Supóngase que cada vez que sale cara, un jugador gana 1 unidad y
si sale cruz pierde 1 unidad.
E = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .}
Podemos estudiar la trayectoria de X(w):
El conjunto posibles de estados para t=3

t=0
t=1
t=2
t =3
CLASIFICACIÓN DE LOS PROCESOS ESTOCÁSTICOS SEGÚN ESTRUCTURA
Existen dos tipos de procesos estocásticos. La diferencia entre los mismos, tiene que ver con
predictibilidad de una serie temporal:
• La estructura del conjunto paramétrico T y

del conjunto de estados E.
• Las características probabilísticas de las
v.a.
CADENA: Presenta posibles estados, entonces Xn ≡ 𝐸𝑠𝑡𝑎𝑑𝑜 (la v.a tomara los diferentes estados)
PROCESO PUNTUAL: en cierto tiempo t habrá k elementos, que en ese instante de tiempo cumplen
cierta condición Xn ≡ 𝑛𝑢𝑚𝑒𝑟𝑜 𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠
SUCESIÓN DE v.a: Xn ≡ 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑒𝑠𝑝𝑒𝑟𝑎𝑑𝑎 Condición a cumplieres en un una unidad de tiempo
PROCESO CONTINUO: Xt ≡ tiempo de espera Teoría de colas
CLASIFICACIÓN DE LOS PROCESOS SEGÚN LAS CARACTERÍSTICAS PROBABILÍSTICAS

1. Procesos Estocásticos Estacionarios.
Un proceso estocástico estacionario es aquel cuya distribución de probabilidad

varía de forma más o menos constante a lo largo de cierto periodo de tiempo con otras
palabras, una serie de números puede parecer (y ser) caótica pero tomar valores dentro de un
rango limitado.
1. Procesos Markovianos
La característica principal de los procesos estocásticos Markovianos es que la distribución de

𝑋𝑛+1 sólo depende de la distribución de 𝑿𝒏 y no de las anteriores (𝑋𝑛−1 , 𝑋𝑛−2 ,…)
Se puede resumir diciendo que el estado futuro del proceso, sólo depende del estado
presente, y no del resto de estados pasados.
3. Procesos de incrementos independientes (ortogonales).
Todo proceso de incrementos ortogonales es un proceso Markoviano (estadísticamente no

correlacionado)
CADENA DE MARKOV
Una cadena es un proceso en tiempo discreto en el que una variable aleatoria 𝑥𝑛 va cambiando
con el paso del tiempo. Las cadenas de Markov tienen la propiedad de que la probabilidad de que
𝑥𝑛 = j sólo depende del estado inmediatamente anterior del sistema: 𝑥𝑛−1 . Cuando en una cadena
dichas probabilidades no dependen del tiempo en que se considere, n,
Probabilidades de Transición
CLASIFICACIÓN DE ESTADOS
ESTADO ALCANZABLE: un estado es ALCANZABLE si existe camino entre (i) y (j)
A B C
• (A) NO es alcanzable desde (C): no hay camino

• (C) SI es alcanzable desde (A): el camino va desde A hasta C
ESTADOS QUE SE COMUNICAN: (i) y (j) se comunican entre si, si son alcanzables entre ellos.
A B C
• (B) SI es alcanzable desde (C)

• (C) SI es alcanzable desde (B): entonces se comunican entre si
ESTADOS TRASCIENTES: Un estado (i) es trasciente si existe un estado (j) es alcanzable desde (i)
Pero (i) no es alcanzable desde (j)
A B
• Si salgo de A, puedo llegar a C,
Pero no se puede regresar a A
• Si salgo de A, puedo llegar a D,
Pero no se puede regresar a A
• Si salgo de B, puedo llegar a C,

Pero no se puede regresar a B
• Si salgo de B, puedo llegar a D,
C
D Pero no se puede regresar a B
ESTADOS RECURRENTE: Todo estado que no es trasciente es recurrente
A B
• Como A y B son Trascientes

• Entonces C y D son RECURRENTES
C
D
CLASE COMUNICANTE: Es un grupo de nodos que se comunican entre si
A B C
D
CLASIFICACIÓN DE CLASES
CADENA DE MARKOV IRREDUCIBLE: Es cuando la cadena solo se compone de una clase comunicante
A C A B
C D
B D
ES IRREDUCIBLE
NO ES IRREDUCIBLE
CLASIFICACIÓN DE CLASES
ESTADO ABSORVENTE: Un estado es absorbente cuando la probabilidad de quedarse allí es 1
B D
C
A
ABSORVENTE PARA CADENAS DE
MARKOV TIEMPO CONTINUO
ABSORVENTE PARA CADENAS DE

MARKOV TIEMPO DISCRETO
https://youtu.be/bAbLC9hfhuQ
9. INTRODUCCIÓN TEORÍA DE GRAFOS
EJEMPLO CONJUNTO DE ESTADOS – APLICACIÓN DE TEORÍA DE GRAFOS
E1 E2 E3 E4
En este grafo, todos los estados tienen periodo 3
E1
E2
E3
E4

Capitulo 9 - INTRODUCCIÓN Y CONCEPTOS TEORÍA DE GRAFOS

Cargado por

Copyright:

Formatos disponibles

Capitulo 9 - INTRODUCCIÓN Y CONCEPTOS TEORÍA DE GRAFOS

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Capitulo 9 - INTRODUCCIÓN Y CONCEPTOS TEORÍA DE GRAFOS

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD NACIONAL DE LOJA

FACULTAD DE LA ENERGÍA, LAS INDUSTRIAS Y LOS RECURSOS NATURALES

DOCENTE: ING. RAÚL CUBILLO BETANCOURT, MSc

PERIODO: Agosto 2021

TEMA 9: INTRODUCCIÓN Y CONCEPTOS TEORIA DE GRAFOS

Al nodo situado en el extremo

una sucesión de v.a.

donde el subíndice indica el instante de tiempo Refleja el concepto de proceso estocástico

INTRODUCCIÓN A PROCESOS ESTOCÁSTICOS

EJEMPLO CONJUNTO DE ESTADOS

E = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .}

Podemos estudiar la trayectoria de X(w):

El conjunto posibles de estados para t=3

• La estructura del conjunto paramétrico T y

CLASIFICACIÓN DE LOS PROCESOS SEGÚN LAS CARACTERÍSTICAS PROBABILÍSTICAS

Un proceso estocástico estacionario es aquel cuya distribución de probabilidad

La característica principal de los procesos estocásticos Markovianos es que la distribución de

3. Procesos de incrementos independientes (ortogonales).

Todo proceso de incrementos ortogonales es un proceso Markoviano (estadísticamente no

ESTADO ALCANZABLE: un estado es ALCANZABLE si existe camino entre (i) y (j)

• (A) NO es alcanzable desde (C): no hay camino

• (B) SI es alcanzable desde (C)

• Si salgo de B, puedo llegar a C,

ESTADOS RECURRENTE: Todo estado que no es trasciente es recurrente

• Como A y B son Trascientes

ABSORVENTE PARA CADENAS DE

EJEMPLO CONJUNTO DE ESTADOS – APLICACIÓN DE TEORÍA DE GRAFOS

También podría gustarte