Digrafos Y Reticulados

República Bolivariana de Venezuela
Ministerio del Poder Popular para Educación Superior
Universidad Fermín Toro - Núcleo Portuguesa
Escuela de Ingeniería en Computación y Telecomunicaciones























Integrante C.I:
Aponte Albert 21.056.559


Araure, Noviembre del 2014
Dígrafos
Es un par ordenado donde V es un conjunto de vértices o nodos, es un conjunto de paresordenados de elementos de V denominados aristas o arcos, donde por definición un arco va del primer nodo (a) el segundo nodo (b) dentro del par. Dada una arista (a, b) a es su nodo inicial y b es su nodo final.
Camino y circuitos de un Dígrafo
1. El número de aristas del camino se llama la longitud del camino.
2. Si los vértices no se repiten el camino se dice propio o simple.
3. Si hay un camino nosimple entre 2 vértices, también habrá un camino simple entre ellos.
4. Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
5. Llamaremos ciclo a un circuito simple.
6. Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos.
7. Todo vértice es accesible respecto a si mismo.




Grafo y Subgrafo


Grafos
Un grafo es el ámbitode las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos, que consiste en un conjunto de nodos también llamados vértices y un conjuntos de arcos llamados aristas que establecen relaciones entre los nodos.
Subgrafos
Llamaremos subgrafo de un grafo a cualquier otro grafo con subgrafos particularmente importantes son aquellos que se obtienen de un grafosuprimiendo uno o varios vértices y las aristas incidentes en estos vértices.
Diagramas fuertemente conexos
Es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos máximos fuertemente conexos. Estos subgrafos forman una partición del grafo.

Cadenas yciclos de un grafo
Ciclo
Un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino.


Cadena
Se denomina cadena en un grafo. Los caminos deben realizarse de acuerdo a la dirección de los lados. Si no existen lados múltiplespodemos denotar sin ambigüedad la cadena como una sucesión de vértices.

Grafo Conexo
Se dice conexo si, para cualquier par de vértices a y b en G, existe al menos una trayectoria una sucesión de vértices adyacentes que no repita vértices de a hasta b.

Cadenas y Ciclos Eulerianos y Hamiltonianos
Ciclo Euleriano
Un modelo, compuesto por un número determinado de vértices nodos y un número de arcosaristas que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo.

Cadena Euleriana
Un recorrido es una cadena sin aristas repetidas se pueden repetir vértices pero llegan al mismo punto siempre.

Ciclo Hamiltoniano
Unciclo Hamiltoniano de G es un ciclo que contiene todos los vértices de G.

Cadena Hamiltoniana
Una cadena elemental de G de longitud, es decir que pasa por todos los vértices de G una y sólo una vez.







Árboles y Bosques
Un árbol es un grafo conexo y acíclico sin ciclos. Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos lasiguiente figura.

Figura: G1 es un árbol (y un bosque); G2 no es un árbol ni un bosque; G3 no es un árbol, pero sí es un bosque
Clases de Arboles
Generadores
Un árbol representa la mínima estructura necesaria para mantener la conexión entre los vértices. Y así se usa en la práctica: si únicamente interesa mantener la conexión del grafo, puedo eliminar todas las aristas innecesarias con...