08 - Grafos dirigidos Flashcards
¿Cuales son las características principales de los digrafos o grafos dirigidos?
- Las aristas tienen una direccion
- Son relaciones asimetricas entre nodos, es decir que si hay una relacion de A a B, no siginifica que tambien exista la relacion de B a A.
- Ej: se usan para diagramas de flujos de datos o para transporte, si se puedo tomar una ruta de una ciudad a otro, pero no se puedo volver por la misma.
A -> B
¿Cual es la diferencia entre grafos dirigidos y no dirigidos?
Grafos no dirigidos:
- Las aristas no tiene direccion.
- Son simétricos (la relacion es de ida y vuelta)
- Ej. se usan para las relaciones en redes sociales.
En el siguiente ejemplo:
V(C) = {a, b, c, d, e}
E(D) = {ab, ac, ae, bc, bd, cb, ce, ed}
Cuantos arcos tiene el digrafo? cuantas entradas y cuentas salidas?
Tiene arcos simetricos?
Cuantos arcos tiene el digrafo? 8
Cuantas entradas? 8
Cuantas salidas? 8
El numero de salidas es igual al de entradas que a su vez es igual al numero de arcos.
Cuantos arcos simetricos?
BC y CB son simétricos, todos los demas asimetricos.
¿Que son los grafos DAG?
Acíclico: no debe tener ciclos
Dirigido: las aristas tienen sentido (arcos)
- Es los DAG no hay forma de regresar el vertice previamente visitado.
- Se usa para representar dependencias, donde la relacion fluye en un solo sentido.
- Los DAG se utilizan para representar ordenes parciales
¿Qué es un camino crítico en una red?
El camino crítico en una red es la secuencia de actividades que determina el tiempo mínimo necesario para completar un proyecto. En un diagrama de red, es el conjunto de tareas que, si se retrasan, retrasan todo el proyecto.
¿Qué es un puente en un grafo?
Un puente es una arista cuya eliminación desconecta el grafo, dividiéndolo en dos componentes disjuntos. Los puentes son esenciales para mantener la conectividad en el grafo.
¿Qué significa que un grafo es fuertemente conectado?
Un grafo fuertemente conectado es un grafo dirigido en el que existe un camino dirigido entre cada par de vértices, en ambas direcciones. Es decir, puedes ir de cualquier vértice ( u ) a otro ( v ), y también regresar de ( v ) a ( u ).
¿Qué es un grafo débilmente conectado?
Un grafo débilmente conectado es un grafo dirigido en el que, si se ignoran las direcciones de las aristas, existe un camino entre todos los vértices. Sin embargo, con las direcciones presentes, puede que no haya caminos en ambas direcciones entre ciertos pares de vértices.
¿Qué es un grafo unilateral?
Un grafo unilateral es un grafo dirigido en el que existe un camino dirigido entre cada par de vértices, pero solo en una dirección. Es decir, puede que exista un camino de ( u ) a ( v ), pero no necesariamente uno de ( v ) a ( u ).
¿Qué establece el Teorema de Robbins?
El Teorema de Robbins establece que un grafo no dirigido puede ser orientado de manera que el grafo resultante sea fuertemente conectado si y solo si el grafo original no contiene puentes.
¿Qué es el grado de entrada de un vértice en un dígrafo?
El grado de entrada de un vértice es el número de aristas que llegan a ese vértice desde otros vértices. En un dígrafo, este grado representa cuántos caminos llegan a ese nodo.
¿Qué es el grado de salida de un vértice en un dígrafo?
El grado de salida de un vértice es el número de aristas que salen de ese vértice hacia otros vértices. Representa cuántos caminos parten desde ese nodo.
¿Qué es un ciclo en un grafo?
Un ciclo en un grafo es un camino que empieza y termina en el mismo vértice, pasando por otros vértices una sola vez antes de regresar al vértice inicial.
¿Qué es un camino hamiltoniano?
Un camino hamiltoniano es un camino que pasa una vez por cada vértice de un grafo, sin repetir vértices, pero que no necesariamente regresa al vértice de inicio.
¿Qué es un ciclo hamiltoniano?
Un ciclo hamiltoniano es un ciclo que pasa por cada vértice de un grafo exactamente una vez y regresa al vértice de inicio.
