Estructuras Discretas
Digrafos
Grafos Dirigidos
Asi como usamos grafos para representar relaciones simetricas,
podemos representar relaciones que no son necesariamente
simetricas por medio de grafos dirigidos o digrafos.
Definicion. Un digrafo (o grafo dirigido) G es un triple
(V (G);E(G); I(G)) donde V (G) es un conjunto (cuyos elementos
son llamados vertices), E(G) es otro conjunto, cuyos elementos son
llamados aristas, e I(G) es una funcion que le asocia a cada arista
e 2 E(G) un par ordenado de vertices. El primer elemento de dicho
par es llamado la cola de e, el segundo es llamado la cabeza de e;
tomados en conjunto, estos dos vertices son llamados los extremos
de e.
Notacion
Dada una arista decimos que va desde su cola y hacia su cabeza.
Generalmente un digrafo es dibujado en forma tal que cada vertice
queda representado por un punto en el plano, y cada arista por una
curva que une los representantes de sus extremos. Para distinguir
cabeza de cola, dibujamos una echa en la cabeza de la arista.
Definiciones adicionales
En un digrafo, un lazo es una arista en que los extremos
coinciden.
Si varias aristas tienen el mismo par ordenado de extremos,
decimos que son aristas multiples.
Un digrafo es simple si cada par ordenado de vertices es el par
(cabeza; cola) de a lo mas una arista (permitimos a lo mas un
lazo en cada vertice).
En un digrafo simple, si la cola de una arista e es u y su cabeza
es v, anotamos e = uv (
En un digrafo, si hay una arista uv, entonces decimos que u es
un predecesor de v (o que u precede a v) y que v es un sucesor
de u (o que v sucede a u).
En este caso, escribimos u ! v.
Caminos y ciclos
Definicion. Un digrafo G es un camino si es un digrafo simple y
sus vertices pueden ser ordenados de modo que cada par de vertices
consecutivos en el orden sean respectivamente la cola y la cabeza
de una arista, y cada arista se forme de esta manera.
La definicion de ciclo en el contexto de digrafos es similar,
ordenando los vertices en torno a un circulo.
Ejemplo: automatas fnitos
Un automata finito es una "maquina" que tiene un numero finito
de estados, y donde las transiciones de un estado a otro son
gobernadas por los simbolos leidos en una "entrada".
Un automata finito puede ser representado como un digrafo, en que
las transiciones entre estados corresponden a aristas, y donde cada
arista tiene asociado un simbolo.
Ejemplo: cadenas de Markov
Dado un sistema formado por un conjunto de estados, en que las
transiciones entre ellos ocurren con probabilidades dadas (que
dependen solo del estado de origen y del estado de destino de la
transicion), decimos que el sistema es una cadena de Markov.
Utilizando metodos de valores y vectores propios, podemos
determinar la distribucion promedio (en el largo plazo) de tiempos
transcurridos en cada estado.
Ejemplo: digrafos funcionales
Sea A un conjunto finito cualquiera, y sea f : A ! A una funcion.
Podemos representar f por un digrafo (llamado el digrafo funcional
de f), que tiene a A como conjunto de vertices y en el que las
aristas son los pares ordenados de la forma (x; f(x)) con x 2 A.
Asi, por ejemplo, el digrafo funcional de una permutacion esta
formado por una coleccion de ciclos disjuntos.
Un camino en un digrafo funcional corresponde a iterar la funcion.
Comentarios terminologicos
Algunos autores hablan de "nodos" y "arcos" en el contexto de
digrafos (para diferenciarlos de los vertices y aristas en el caso no
dirigido).
Tambien se habla de "camino dirigido" y "ciclo dirigido".
Aqui usaremos los mismos terminos para hablar de grafos y
digrafos. Muchos de los conceptos y resultados para grafos son
naturalmente "extendidos" a digrafos.
El grafo subyacente de un digrafo
Definicion. Dado un digrafo D, llamamos grafo subyacente d D al
grafo G que es obtenido al considerar las aristas de D como pares
no ordenado.
Al pasar de un digrafo D a un grafo G los conjuntos de vertices y
aristas se mantienen, y los extremos de cada arista pasan de formar
un par ordenado a formar un par no ordenado.
Subgrafos, isomorfismos. Matrices.
Las definiciones de subgrafo, isomorfismo, descomposicion y union
son las mismas para grafos y digrafos.
En la matriz de adyacencia A(G) de un digrafo G, el elemento aij
es el numero de aristas que van desde vi hacia vj .
En la matriz de incidencia M(G) de un digrafo sin lazos G,
definimos mij = +1 si vi es la cola de ej , y mij = -1 si vi
es la cabeza de ej .
Conexion
Hay dos conceptos de conexion para digrafos. Uno corresponde a la
conexion del grafo subyacente, la otra es mas propia de los digrafos.
Definicion. Un digrafo es debilmente conexo si su grafo
subyacente es conexo.
Un digrafo G es fuertemente conexo (o fuerte) si dados dos
vertices cualesquiera u; v 2 V (G), existe un camino en G desde
u a v.
Las componentes fuertemente conexas de un digrafo son sus
subgrafos maximales fuertemente conexos.
Juegos
Muchos juegos de dos jugadores (damas, ajedrez, nim, "gato")
pueden ser modelados usando digrafos. Las posibles "posiciones"
son los vertices, y las jugadas posibles corresponden a las aristas.
De entre los vertices, identicamos un conjunto W de vertices
"ganadores" (en algunos casos, combiene identificar dos conjuntos,
uno para vertices en que "ganan las blancas" y otro donde "ganan
las negras").
En una posicion dada, el jugador de turno tiene una "estrategia
ganadora" si puede llevar el juego a una posicion de ganadora, sin
importar como juegue su adversario.
Una posicion es "perdida" si, sin importar como juegue el jugador
de turno, llevara el juego a una posicion en que su contrincante
tendra una estrategia ganadora.
Kernels
Definicion. Un kernel en un digrafo G es un conjunto S conectado V (G)
tal que S no induce ninguna arista (o sea, es un conjunto
independiente) y todo vertice fuera de S tiene un sucesor en S.
Teorema (Richardson, 1953). Todo digrafo sin ciclos impares
tiene un kernel.
http://galeon.com/estructurasdiscretas/principal.html
