Solucionando problemas caminos y circuitos mediante grafos.

 

Solucionando problemas caminos y circuitos mediante grafos

 

1. Explica cómo se pueden utilizar dos grafos de llamadas, uno con las llamadas hechas durante el mes de enero y el otro con las hechas durante el mes de febrero, para determinar el nuevo número de teléfono de las personas que hayan cambiado de número.

Construir dos grafos; en el primer grafo se utiliza un multígrafo dirigido donde el vértice es el número de teléfono, y la arista es la llamada la cual sale del número de teléfono desde el que se hace la llamada y llega al teléfono que la recibe; el segundo grafo es un grafo no dirigido en donde una arista conecta los dos números de teléfono si se ha realizado alguna llamada entre estos, así se puede determinar que personas han cambiado de número.

2. ¿Cómo se puede utilizar un grafo que represente los mensajes de correo electrónico enviado en una red para encontrar a personas que hayan cambiado recientemente su dirección principal de correo electrónico?

Se crea un grafo dirigido donde los vértices representan las direcciones de correo electrónico y las aristas los mensajes enviados entre esas direcciones, se puede crear a cada arista una propiedad de tiempo para identificar cuando se envió el último mensaje y así determinar que personas han cambiado su correo recientemente.

3. Describe un grafo que represente matrimonios. ¿Tiene este grafo alguna propiedad especial?

Se puede representar como un grafo no dirigido, los vértices representan las personas y las aristas los matrimonios, de esta forma las aristas conectan a las personas que están casadas entre sí. La propiedad especial es la conectividad, todos los vértices están conectados a una pareja.

4. Describe una estructura discreta basada en un grafo que se pueda utilizar para representar relaciones entre pares de individuos de un grupo suponiendo que cada individuo puede serle simpático, antipático o indiferente a cada uno de los demás individuos y que las relaciones pueden no ser recíprocas (Indicación: Dota de estructura a un grafo dirigido. Trata por separado las aristas con direcciones opuestas entre vértices que representen a dos individuos)

Se puede emplear un grafo dirigido donde las aristas tienen una dirección específica, cada individuo se representa con un vértice y las aristas representan la relación entre dos individuos, la dirección de la arista indica la dirección de la relación y se dibuja la arista desde cada vértice con la etiqueta que corresponda, ejemplo “simpatía”.