TUTORÍA VIRTUAL
Estimados estudiantes el presente trabajo esta detallado a continuación.
TEMA:
CURSO:
SEGUNDO BGU.
PARCIAL: QUIMESTRE:
TERCER. SEGUNDO.
FECHA:SEGUNDO BGU.
PARCIAL: QUIMESTRE:
TERCER. SEGUNDO.
17 -01-2016. UNION.
INSTRUCCION: PASAR AL CUADERNO Y ESTUDIAR.
Rutas en una red de caminos
Un grafo puede ser usado para modelar caminos entre distintos puntos de una red
caminera, eléctrica, hidráulica, o de telecomunicaciones por fibra óptica, etc. Los
vértices son las intersecciones de los caminos y las aristas son los tramos de caminos
entre intersecciones.
Se conoce como camino de longitud n entre los vértices de un grafo a una sucesión
finita de aristas del grafo; cada arista sucesiva empieza donde terminó la anterior.
• Un camino es un circuito cerrado si empieza y termina en el mismo vértice.
• Un camino es simple si no contiene a la misma arista más de una vez.
• Un circuito que no pasa dos veces por el mismo vértice (salvo el inicial, por el que
pasa dos veces), se llama ciclo.
Un problema importante y con mucha aplicación en Teoría de Grafos es hallar el camino
más corto entre dos puntos
Condiciones suficientes en un grafo,para un circuito de Euler
Las condiciones suficientes en un grafo para que contenga un circuito de Euler
son las siguientes:
• No puede haber más de dos vértices de grado impar en el grafo.
• Si el grafo tiene dos vértices de grado impar, todo camino euleriano debe comenzar
en uno de ellos y terminar en el otro.
• Si el grafo no tiene vértices de grado impar, todo camino euleriano debe ser un
circuito, y puede comenzar en cualquier vértice.
• Un multígrafo contiene un camino euleriano, pero no un circuito euleriano, si
y solo si, tiene exactamente dos vértices de grado impar.
• Un multígrafo conexo contiene un circuito euleriano, si y solo si, cada uno de sus
vértices tiene grado par.
Resultado de la obtenciónde un circuito de Euler
Sea G un grafo, tal que G = (V, A) y que todas sus aristas estén en la misma componente
conexa, se dice que admite un camino euleriano no cerrado, si y solo si, contiene
exactamente dos vértices de grado impar.
Demostración
1. Se supone que G = (V, A) admite un camino euleriano no cerrado:
(a, v1, v2,…, vn – 1, b), donde a y b son los extremos del camino.
2. Sea w un nuevo vértice que no pertenece a V, y G1 un nuevo grafo que contiene
los vértices de V, incluido el vértice w, y como aristas, además de las de A = {wa, bw}.
3. Se hace evidente que G1 es un grafo que admite un camino euleriano cerrado
(w, a, v1, v2,…, vn – 1, b, w); en consecuencia, todos los vértices de G1 son de grado par.
4. Al eliminar las aristas {wa, bw} y el vértice w de G1 para obtener G, concluimos
que todos los vértices son de grado par, a excepción de a y b.
5. Recíprocamente, si todos los vértices de G, salvo dos, a y b, tienen grado par, construyendo
el grafo G1 con un nuevo vértice w, no perteneciente a V, obtendremos
un grafo en el que todos los vértices son de grado par, siendo (w, a, v1, v2,…, vn – 1,
b, w) un circuito euleriano mientras que, (a, v1, v2,…, vn – 1, b) es un circuito no
cerrado que conecta a y b.
Considerando todo este proceso, ya se está en condiciones de demostrar que no es
posible encontrar un circuito que resuelva el problema de los puentes de Königsberg,
pues el grafo que representa el problema tiene más de dos vértices de grado impar.
La característica de Euler
Planaridad
La característica de planaridad nos permite responder a la pregunta: ¿Puede un grafo
ser dibujado en el plano, sin que se crucen las aristas?
Consideremos este ejemplo. ¿Es posible unir tres casas a las distribuidoras de televisión
por cable, teléfono e Internet sin que se crucen los cables?
Fórmula de Euler
Según Euler, si G es un grafo plano conexo, con n vértices, e aristas y f caras, entonces:
n – e + f = 2
De esta fórmula se pueden concluir algunas consecuencias.
• Todas las representaciones planas de un grafo G tienen el mismo número de caras.
• Si G es un grafo plano no conexo, la fórmula de Euler tal como está, no es válida;
sería necesario agregar aristas para conectarlas todas y aplicar la fórmula original,
pero el agregar estas aristas no cambia el número de caras en G, por lo que, en
este caso:
n – e + f = k + 1
donde k es el número de componentes.
Circuito de Hamilton
En 1856, el matemático William Hamilton presentó al mundo un puzle (juego de
mesa). El juego estaba basado en un dodecaedro regular cuyos 20 vértices se marcaban
cada uno con el nombre de una ciudad importante en aquella época. El juego
consistía en salir de una determinada ciudad y encontrar una ruta que permitiera
pasar por todas las demás ciudades una sola vez y regresar al punto de partida.
El dodecaedro era tan incómodo de manipular que Hamilton desarrolló una versión
del juego en la que lo reemplazaba por un grafo con 20 vértices unidos mediante
30 aristas. El grafo resultante se conoce como grafo del dodecaedro.
Operaciones con grafos
Grafo del dodecaedro.
Bloque 3
Se dice que un grafo es de Hamilton si existe un ciclo que recorre todos sus vértices
y se lo denomina ciclo hamiltoniano.
A pesar de la preocupación y el estudio de los matemáticos, no existe hoy en día un
teorema que permita determinar si un grafo es hamiltoniano o no. El método de
ensayo y error es la única forma posible de encontrar una respuesta al problema.
Se denomina camino hamiltoniano en un grafo con aristas no orientadas G = (V, A) a
cualquier camino simple que contenga a todos los vértices de G pasando una sola vez
por cada uno de ellos, pero permitiendo que el vértice inicial de dicho camino sea igual
al vértice final. Si el camino hamiltoniano es cerrado, se lo denomina circuito hamiltoniano.
Grafos hamiltonianos.
Problema del transporte
Red de transporte
Una Red de Transporte es una gráfica dirigida, simple, con pesos y que debe cumplir
las condiciones siguientes:
a. Poseer una fuente o vértice fijo que no tiene aristas de entrada.
b. Poseer un sumidero o vértice fijo que no tiene arista de salida
c. El peso Cij de la arista dirigida de i a j llamado capacidad de «ij» es un número no
negativo.
Considerando la siguiente gráfica dirigida (red de transporte), que representa una tubería
de petróleo. El petróleo se descarga en el muelle a y se bombea por toda la red de
la refinería z . Los vértices b, c, d y e representan estaciones de bombeo intermedias.
Las aristas dirigidas representan subtuberías del sistema y muestran la dirección en
que puede fluir el petróleo. Las etiquetas de las aristas indican las capacidades de las
subtuberías. El problema es encontrar la manera de maximizar el flujo del muelle a
la refinería y calcular el valor de este flujo máximo.
Este es un ejemplo de una red que parte de un punto a que es un muelle y llega a un
punto z que es una refinería:
Problemas de transporte
A = muelle 2 Z = refinería
Problemas de transporte
Cuando se presentan problemas en los que cada arista viene caracterizada por su
distancia o por su capacidad para trasladar objetos por ella, la riqueza de situaciones
se multiplica. Entramos de lleno en los problemas de optimización, de los que algunos
ejemplos se mencionan a continuación:
• Obtener una ruta entre dos vértices por el camino más corto.
• Obtener una ruta entre dos vértices de coste mínimo.
• Transportar un conjunto de objetos entre dos vértices de forma que se aproveche
al máximo la capacidad de cada ruta.
Ejemplos de este tipo de situaciones son:
• El caso de un comerciante que necesita recorrer un grupo de ciudades alcanzando
finalmente la ciudad de partida después de recorrer la menor distancia.
• El caso de un autobús escolar que tiene que recoger a niños en un número determinado
de paradas situadas en distintas calles de una red urbana. El objetivo es
encontrar una ruta con la menor longitud posible.
r
Un grafo dirigido o también
llamado dígrafo es un grafo
en el que las aristas tienen una
dirección definida.
Probabilidad
Generalidades
La probabilidad estudia experimentos en los que se pueden esperar varios resultados
y no solamente uno. Los experimentos se pueden clasificar como aleatorios o
determinísticos.
Para que un experimento sea aleatorio debe reunir las siguientes tres condiciones:
• Antes de realizar el experimento se deben conocer todos los posibles resultados.
• No es posible predecir un resultado en particular.
• El experimento se puede ejecutar infinitas veces con las mismas condiciones.
A cada uno de los resultados del espacio muestral se le denomina punto muestral.
Como los eventos son conjuntos, se les puede aplicar las operaciones y propiedades
de la teoría de conjuntos:
Evento simple o elemental: es aquel subconjunto de S que contiene un solo punto
muestral.
Evento compuesto: es un subconjunto de S con más de un punto muestral.
Evento imposible: es un subconjunto de S que no contiene ningún punto muestral,
es decir, un subconjunto vacío.
Evento seguro: subconjunto que contiene de S los mismos puntos del espacio
muestral S.
Unión de eventos: si ocurren por lo menos uno o varios eventos a la vez. Así, si ocurre
el evento E o el evento F, ocurre E < F.
Intersección de eventos: si los eventos ocurren al mismo tiempo, es decir, si ocurre el
evento G y el evento H a la vez, ocurre G > H.
NOTA: NO FALTAR ESTE JUEVES AL PROYECTO SI ES POSIBLE LLEVAR COMPUTADOR PORTATIL, IR CON EL UNIFORME..
No hay comentarios:
Publicar un comentario