TEMA 8

TEORÍA DE GRAFOS CON MATHEMATICA

La forma de trabajar grafos es distinta en mathematica 5.0, de hecho esta nueva versión trae un apartado en la ayuda dedicado expresamente a Combinatorica

· Help

· Add-ons

· Combinatorica

DiscreteMath`Combinatorica` tiene unas 450 funciones sobre combinatoria y teoría de grafos aunque en la ayuda se estudian sólo unas pocas, pero en el libro: Implementing Discrete Mathematics de Steven Skiena y editado por Addison-WesleyPublishing Company puedes encontrar toda la información sobre package

Empieza viendo en el package la parte correspondiente a grafos y mirando las posibilidades que tiene de trabajar con ellos: generación de grafos, representación de grafos, propiedades de grafos, algoritmos de grafos…..

Por supuesto, para poder usar los algoritmos, las propiedades,….. tienes que conocer el algoritmo, saber lo que indican las propiedades ….., por lo tanto es recomendable repasar un poco la teoría de grafos, de nada sirve tener un package que puede resolver muchos problemas, si no se saben interpretar las soluciones a los problemas o no se saben plantear. Señalamos que en todos estos problemas, la modelización dentro de la teoría de grafos e interpretación de la solución obtenida, es tan importante como el método y la solución en sí misma.

8.1- FORMA DE INTRODUCIR UN GRAFO CON Mathematica 5.0 o superior

Empezamos a trabajar con Mathematica y Grafos, para ello tenemos que saber como introducir un grafo.

Para Mathematica un grafo es Graph[e, v], donde:

1. “v” está formado por las coordenadas de los vértices

2. “e” está formado por las aristas. Para indicar una arista lo que hacemos es dar el par de los vértices que enlaza dicha arista

Ejemplo 1:

Vamos a definir un grafo, necesitamos “e” y “v”. Una vez introducidos esos datos, mediante la orden Graph[e, v], le decimos a Mathematica que ese es nuestro grafo, al cual vamos a llamar migrafo. Y después lo representamos mediante la orden ShowGraph.

In[]

<<DiscreteMath`Combinatorica`

e={{{1, 4}}, {{1, 5}}, {{2, 3}}, {{2, 5}}, {{3, 2}}, {{3, 4}}, {{4, 1}}, {{4, 3}}, {{5, 1}}, {{5, 2}}};

v={{{0.4, 0.9}}, {{0.5, 0.2}}, {{0.8, 0.7}}, {{0.1, 0.6}}, {{2, 0.5}}};

migrafo = Graph[e, v];

ShowGraph[migrafo];

Out[]

El color, estilo, etiquetas y nombre de los vértices, se pueden cambiar individualmente. También podemos cambiar el color de las aristas ………..

Ejemplo 2:

In[]

<<Graphics`Colors`

ShowGraph[SetGraphOptions[migrafo,{{1,2,VertexColor -> Green,VertexStyle-> Disk[Large]},{3,4,VertexColor-> Blue} ,{5,VertexColor-> Violet}}, EdgeColor-> Red, VertexLabel->{a,2,3,4,casa}], PlotRange->All];

Out[]

Mathematica representa (por defecto) el grafo como no dirigido, por eso hay que tener cuidado. Mira el siguiente ejemplo, el grafo es distinto del anterior (hemos quitado la arista

{ 5, 2}), pero obtenemos la misma representación gráfica.

Ejemplo 3:

In[]

e = {{{1, 4}}, {{1, 5}}, {{2, 3}}, {{2, 5}}, {{3, 2}}, {{3, 4}}, {{4, 1}}, {{4, 3}}, {{5, 1}}};

v = {{{0.4, 0.9}}, {{0.5, 0.2}}, {{0.8, 0.7}}, {{0.1, 0.6}}, {{2, 0.5}}};

grafo = Graph[e, v];

ShowGraph[SetGraphOptions[grafo, {{1, 2, VertexColor -> Green, VertexStyle -> Disk[Large]}, {3, 4, VertexColor -> Blue}, {5, VertexColor -> Violet}}, EdgeColor -> Red, VertexLabel -> {a, 2, 3, 4, casa}], PlotRange -> All];

Out[]

Por esta razón lo mejor es mirar la matriz de adyacencia de los grafos

In[]

ToAdjacencyMatrix[migrafo]//MatrixForm

ToAdjacencyMatrix[grafo]//MatrixForm

En migrafo, al ser no dirigido, la arista {2, 5} es la misma que la {5, 2} y por eso hay dos aristas que enlazan los vértices 2 y 5.

Pero en grafo, que también es no dirigido, ya no está la arista {5, 2} por eso sólo hay una forma de enlazar el vértice 2 con el 5

Además también podemos representar el grafo de forma dirigida y ver el sentido de las flechas.

Ejemplo 4:

In[]

<<DiscreteMath`Combinatorica`

<<Graphics`Colors`

e = {{{1, 4}}, {{1, 5}}, {{2, 3}}, {{2, 5}}, {{3, 2}}, {{3, 4}}, {{4, 1}}, {{4, 3}}, {{5, 1}}, {{5, 2}}};

v = {{{0.4, 0.9}}, {{0.5, 0.2}}, {{0.8, 0.7}}, {{0.1, 0.6}}, {{2, 0.5}}};

migrafouno = Graph[e, v, EdgeDirection ® True];

ShowGraph[SetGraphOptions[migrafouno, {{1, 2, VertexColor -> Green, VertexStyle -> Disk[Large]}, {3, 4, VertexColor -> Blue}, {5, VertexColor -> Violet}}, EdgeColor -> Red, VertexLabel -> {a, 2, 3, 4, casa}], PlotRange -> All];

ToAdjacencyMatrix[migrafouno]//MatrixForm

Out[]

migrafouno es dirigido, entonces la arista {1, 4} es distinta de la arista {4, 1} y tenemos una arista que enlaza el vértice uno con el cuatro y otra que enlaza el vértice cuatro con el uno. Pero la matriz de adyacencia es simétrica porque siempre que podemos ir del vértice “a” al “b” también podemos ir del vértice “b” al “a”

Ejemplo 5:

In[]

<<DiscreteMath`Combinatorica`

<<Graphics`Colors`

e = {{{1, 4}}, {{1, 5}}, {{2, 3}}, {{3, 2}}, {{3, 4}}, {{4, 3}}, {{5, 1}}, {{5, 2}}};

v = {{{0.4, 0.9}}, {{0.5, 0.2}}, {{0.8, 0.7}}, {{0.1, 0.6}}, {{2, 0.5}}};

migrafodos = Graph[e, v, EdgeDirection ® True];

ShowGraph[SetGraphOptions[migrafodos,{{1, 2, VertexColor -> Green, VertexStyle -> Disk[Large]}, {3, 4, VertexColor -> Blue}, {5, VertexColor -> Violet}}, EdgeColor -> Red, VertexLabel -> {a, 2, 3, 4, casa}], PlotRange -> All];

ToAdjacencyMatrix[migrafodos]//MatrixForm

Out[]

migrafodos es dirigido y además hemos eliminado dos aristas, por eso su matriz de adyacencia no es simétrica (podemos ir del vértice 1 al 4 pero no del 4 al 1 y podemos ir del vértice 5 al 2 pero no del 2 al 5).

Ejemplo 6:

Vamos a introducir un grafo y una vez introducido queremos la siguiente salida:

· Si el grafo es no dirigido

· Matriz de adyacencia del grafo.

· Lista de adyacencias del grafo.

· Representación gráfica

· Si el grafo es dirigido sólo queremos la representación gráfica.

In[]

Clear["Global`*"]

<<DiscreteMath`Combinatorica`

<<Graphics`Colors`

e = {{{1, 4}}, {{1, 5}}, {{2, 3}}, {{2, 5}}, {{3, 2}}, {{3, 4}}, {{4, 1}}, {{4, 3}}, {{5, 1}}, {{5, 2}}};

v = {{{0.4, 0.9}}, {{0.5, 0.2}}, {{0.8, 0.7}}, {{0.1, 0.6}}, {{2, 0.5}}};

grafo = Graph[e, v, EdgeDirection ® True];

If[ToAdjacencyMatrix[grafo] ¹ Transpose[ToAdjacencyMatrix[grafo]],

Print["El grafo es dirigido"];

ShowGraph[SetGraphOptions[grafo, VertexColor->Green, EdgeColor-> Red, VertexLabel -> {1, 2, 3, 4, 5, 6}], PlotRange -> All],

Print["El grafo es no dirigido"];

Print["la matriz de adyacencias es", ToAdjacencyMatrix[grafo]//MatrixForm];

Print["la lista de adyacencias es", TableForm[ToAdjacencyLists[grafo]]];

ShowGraph[SetGraphOptions[grafo, VertexColor -> Green, EdgeColor -> Red, VertexLabel -> {1, 2, 3, 4, 5, 6}], PlotRange -> All]];

Out[]

En el ejemplo, la matriz de adyacencia el grafo es simétrica, luego el grafo es no dirigido

8.2.- REPASO DE CONCEPTOS BÁSICOS DE LA TEORÍA DE GRAFOS

Veamos algunas de las muchas posibilidades que tiene el paquete

DiscreteMath`Combinatorica`

Para ello vamos a ir haciendo una serie de preguntas que debes contestar, utilizando la ayuda de Mathematica, los conceptos de grafos y los programas que necesites realizar.

(mientras no digamos lo contrario nos referimos a grafos no dirigidos)

· Quiero saber si un grafo determinado es conexo, ¿cómo lo puedo averiguar?.

· Quiero saber si un grafo determinado es plano, ¿cómo lo puedo averiguar?.

· Quiero saber si un grafo determinado admite camino de Hamilton, ¿cómo lo puedo averiguar?.

· En caso de tener un grafo hamiltoniano, ¿cómo puedo obtener un ciclo de Hamilton?

· ¿Cómo llama Mathematica al grafo completo de orden “n”?

· ¿Cómo puedo hacer el complementario de un grafo?

· ¿Cómo puedo hacer, con Mathematica, la potencia “n” de un grafo?, ¿Qué indica la matriz de la potencia “n” de un grafo?

· ¿Cómo interpreto la salida que obtengo con Mathematica, al introducir la orden:

BreadthFirstTraversal[grafo, 1]

· ¿Qué significa la salida que obtengo con Mathematica, al introducir la orden:

BreadthFirstTraversal[grafo, 1, Edge]

· ¿Cómo interpreto la salida que obtengo con Mathematica, al introducir la orden:

DepthFirstTraversal [grafo, 3]

· ¿Qué significa la salida que obtengo con Mathematica, al introducir la orden:

DepthFirstTraversal [grafo, 3, Edge]

· ¿Tiene mathematica el algoritmo de Prim?

(Ahora puedes hacer los problemas 1, 2 y 9 de este tema)

8.3.- COLORACIÓN DE GRAFOS

Una coloración de los vértices de un grafo G = (V, A) es una asignación de etiquetas o colores a los vértices del grafo de manera que no existan aristas conectadas con idéntico color de vértices. Es fácil colorear un grafo con “n” colores (si posee n vértices) el problema surge cuando se necesita conocer el mínimo número de colores necesario para hacer la coloración del grafo.

Se define el número cromático de un grafo G como el mínimo número de colores necesario para colorear todos los vértices de G y lo notamos por À(G).

· El único grafo donde À(G) = 1 es el grafo donde todos los vértices son aislados.

· Los grafos donde À(G) = 2 son bipartitos y viceversa (¿Por qué?)

· La situación se hace interesante cuando al menos tres colores son necesarios.

Sabemos por Matemática Discreta que todo grafo plano necesita como máximo 4 colores para su coloración. Pero si el grafo no es plano, pueden necesitarse más colores para su coloración, por ejemplo K₅ necesita cinco colores para ser coloreado.

Polinomio Cromático de un grafo

El polinomio cromático de un grafo es una función polinómica que índica el número de coloraciones posibles que se pueden hacer en el grafo usando x colores. El polinomio cromático es un concepto íntimamente ligado al cálculo de À(G)

Veamos como se puede obtener este polinomio.

a.- Si el grafo en cuestión es completo de orden “n”, está claro que su polinomio cromático es:

P(x) = x . (x-1) . (x-2) …….. (x-n+1)

b.- Si el grafo no es completo, para obtener su polinomio cromatico procedemos de la siguiente forma:

Ahora ya podemos construir el polinomio cromático de cualquier grafo porque usando lo anterior podemos ir consiguiendo grafos completos de los cuales conocemos su polinomio cromático.

Ejemplo 7:

Queremos calcular el polinomio cromático de :

vemos que le faltan las aristas {1, 3} y la {3, 4} para ser K[6]. Por lo tanto colorear este grafo es lo mismo que colorear los dos grafos siguientes:

Coloreamos {1 y 3} de distinto color. Hemos añadido la arista {1, 3}. Este grafo todavía no es K[6] y no conocemos su polinomio cromático por eso tenemos que repetir este proceso otra vez para este grafo	Hemos considerado el vértice 1 y el vértice 3 como un único vértice.(mismo color) y este es K[5] del que sabemos que su polinomio cromático es x.(x - 1)(x - 2)(x - 3)(x - 4)
Coloreamos {4 y 3} de distinto color. Hemos añadido la arista {4, 3}. Este grafo es K[6] y conocemos su polinomio cromático x(x - 1)(x - 2)(x - 3)(x - 4)(x - 5)	Hemos considerado {13, 4} como un único vértice.(mismo color) y este es K[5] del que sabemos que su polinomio cromático es x.(x - 1)(x - 2)(x - 3)(x-4)

Luego el polinomio cromático del grafo pedido es: dos veces el de K[5] más una vez el de K[6]

P(x) = 2 x(x - 1)(x - 2)(x - 3)(x - 4) + x.(x - 2)(x - 2)(x - 3)(x - 4)(x - 5)

Ahora contesta las siguientes cuestiones:

· Una vez conocido el polinomio cromático de un grafo, ¿Sabes como calcular À(G)?

· Si el número cromático de un grafo es tres, ¿Cuánto vale P(1)?, ¿Cuánto vale P(2)?

Mathematica posee funciones para calcular el polinomio cromático y el número cromático de un grafo conexo.

ChromaticPolynomial[grafo, x]

ChromaticNumber[grafo]

Para grafos bipartitos: TwoColoring[grafo]

¿Cómo interpretas la salida que obtines con Mathematica para estas funciones?

Como el problema de calcular el número cromático es NP_Completo, calcular el polinomio cromático es muy duro, por eso a veces encontrar una coloración de grafos se puede hacer de modo Heurístico, como el algoritmo visto en Matemáticas Discretas, pero este camino no nos asegura encontrar el mínimo número de colores, sólo nos dá una coloración.

Esto lo podemos hacer mediante:

ShowLabeledGraph[grafo,VertexColoring[grafo]]

· ¿Cómo podemos obtener el polinomio cromático de un grafo que no es conexo?.

(Ahora puedes hacer el problema 8 del tema)

8.4.- MATRIZ DE ACCESO

Dados dos vértices de un grafo G = (V, A), decimos que v_i alcanza a v_j si y solamente si existe una cadena de longitud mayor o igual que cero de v_i a v_j

Llamamos matriz de acceso del grafo G = (V, A) donde Cardinal de V = n, a una matriz B_nxn definida:

La pregunta inmediata es: ¿cómo obtener de forma cómoda la mencionada matriz de acceso de un grafo dado G?

Conocemos dos algoritmos que resuelven dicha cuestión:

1.- Búsqueda en amplitud (o extensión)

Si aplicamos el algoritmo de la búsqueda en amplitud al vértice 1 de un grafo, obtenemos un árbol generador con raíz en el vértice 1, es decir, obtendremos los accesos desde el vértice 1 a cualquier otro vértice.

Aplicando el algoritmo a todos los vértices del grafo y volcando los resultados en una matriz, obtendremos la matriz de acceso.

2.- Búsqueda en profundidad

Por la misma razón que en el algoritmo anterior también obtenemos la matriz de acceso.

Tanto el algoritmo de búsqueda en extensión, como el de la búsqueda en profundidad, tienen una complejidad temporal en el peor de los casos de n² (n es el número de vértices) si utilizamos matrices de adyacencia para representar G y proporcional a n + e (donde e es el número de aristas) si utilizamos listas de adyacencia.

3.-El algoritmo de Warshall

Con este algoritmo obtenemos directamente la matriz de acceso.

Vamos a hacerte una serie de preguntas para relacionar la matriz de acceso con la conectividad.

· Si un grafo no dirigido es conexo, ¿Cómo es su matriz de acceso?

· Si un grafo no dirigido no es conexo ¿Posee Mathematica alguna función para encontrar sus componentes conexas?

· Si un grafo dirigido es fuertemente conexo ¿Cómo es su matriz de acceso?

(Ahora puedes hacer el problema 3 del tema)

8.5.- EL PROBLEMA DEL CAMINO MÁS CORTO

Llamamos grafo ponderado a todo grafo G = (V, A) en el que hayamos asociado unos valores p(v_i, v_j), llamados pesos o costes, a cada una de las aristas del grafo.

Podemos representar un grafo ponderado mediante una matriz P_nxn de costes, definida:

Dado un camino Cu₁u₂u₃.........u_n en el grafo G, llamamos peso o coste del camino C al valor:

P(C) =

Se trata de encontrar “los caminos más cortos”, es decir los caminos de menor peso, ya sea de un vértice fijado a los restantes, o entre dos vértices cualesquiera.

En general cuando tratemos el problema del camino más corto, podemos suponer que no existen bucles. ¿Por qué?

En relación con los pesos de las aristas, pueden ser positivos negativos o cero. Sin embargo, no consideraremos grafos con ciclos de peso total negativo. ¿Por qué?

Recordemos dos algoritmos:

1.- Algoritmo de Dijkstra

Se aplica a matrices de pesos positivos (ver Matemática Discreta). El tiempo requerido por el algoritmo es del orden de n², donde n es el cardinal del conjunto de vértices.

· ¿Cómo se llama la función que posee Mathematica para obtener directamente el algoritmo de Dijkstra?

· ¿Cómo interpretas la salida que se obtiene al aplicar dicha función?

· ¿Hay alguna función que obtenga el camino más corto entre dos vértices?

2.- Algoritmo de Floyd

Resuelve el problema de averiguar el camino más corto entre dos vértices cualesquiera, suponiendo una matriz de costes en general.

Podríamos hacerlo, aplicando Dijkstra a cada uno de los vértices, pero entonces el tiempo sería del orden de n³ y sólo nos sirve para pesos positivos.

El algoritmo de Floyd tendrá un tiempo de ejecución también del orden de n³, pero sirve para pesos negativos.

En caso de no recordar este algoritmo puedes buscarlo en el libro:

Introducción a la teoría de grafos y sus algoritmos de Cristina Jordan Lluch y Juan R. Torregrosa Sánchez, Universidad Politécnica de Valencia.

· Mathematica tiene programado este algoritmo mediante la función:

AllPairsShortesPath[grafo]

¿Cómo interpretas la salida que da dicha función?

· ¿Sabes obtener el camino más corto (no la distancia) entre cualquier par de vértices?

(Ahora puedes hacer los problemas 4, 5, 6 y 7 del tema)

8.6.- ACOPLAMIENTOS Y PROBLEMA DE LA ASIGNACIÓN

Problema de la asignación

Comenzamos poniendo un ejemplo: En la Universidad de Córdoba se está planificando un nuevo curso. Faltan por asignar los profesores de tres grupos de primer curso de las asignaturas de Matemáticas I, Matemáticas II y de dos de segundo de Matemáticas y Mathematica. Si cada uno de los 8 profesores de que disponemos se va a encargar de un grupo y una asignatura, teniendo en cuenta la relación de sus preferencias y su disponibilidad de horarios reflejada en la tabla.

	P1	P2	P3	P4	P5	P6	P7	P8
1.m1	*		*
2.m1	*	*					*
3.m1			*	*	*			*
1.m2				*		*		*
2.m2						*	*
3.m2					*
1.mm			*		*
2.mm					*			*

¿Es posible encontrar una asignación profesor-asignatura-grupo que cubra todas la necesidades académicas y respete las preferencias del profesorado? En caso afirmativo ¿Cuál será una asignación de este tipo?

El problema de la asignación consiste básicamente en asignar a cada uno de los “n” trabajadores con los que contamos, un trabajo de los “n” a realizar, sabiendo que cada uno de los trabajadores es apto para uno o más trabajos.

Para solucionar este y muchos problemas de este tipo, necesitamos algunas definiciones

Definiciones.

G = (V, A) un grafo no dirigido con cardinal de V igual a “n”

Un acoplamiento M de G es un subconjunto no vacío de A tal que dos aristas distintas no tienen vértice común.

Un vértice v es M-saturado si existe una arista del acoplamiento M incidente en v.

Un acoplamiento M es perfecto si todos sus vértices son M-saturados.

Un acoplamiento es máximo si no existe en G otro acoplamiento de cardinal estrictamente mayor que el de M.

Claramente el acoplamiento más grande posible posee aristas (parte entera). No todos los grafos tienen un acoplamiento perfecto, pero todos los grafos tienen un acoplamiento máximo.

Ejemplo: el grafo con forma de estrella, no tiene acoplamiento perfecto

Acoplamiento perfecto acoplamiento ni máximo ni perfecto

El modelo matemático que describe el problema del principio, consiste en encontrar un acoplamiento perfecto en un grafo bipartito G((X, Y), A) en el que Card(X) = Card(Y). Dicho grafo será el obtenido considerando como X el conjunto de los trabajadores, Y el conjunto de trabajos y como conjunto de aristas

{(x, y) / x Î X, y Î Y, x cualificado para realizar y}

Mathematica resuelve este problema con la instrucción

BipartiteMaching[grafo]

¿Qué salida se obtiene con esta función si el grafo no tiene un acoplamiento perfecto?

Si tenemos un grafo bipartito G((X, Y), A) en el que Card(X) ¹ Card(Y) se soluciona el problema añadiendo vértices ficticios.

(Ahora puedes hacer el problema 10 del tema y el del ejemplo)

8.7.- PROBLEMAS Y EJERCICIOS CORRESPONDIENTES AL TEMA 8

1.- Vamos a trabajar un poco con los conceptos generales.

Introduce un grafo dirigido y resuelve las siguientes cuestiones con Mathematica

1. Representación gráfica del grafo.

2. Representación gráfica de su complementario.

3. Matriz de adyacencia del grafo complementario.

4. Que nos diga si el grafo es plano.

2.- Seguimos trabajando con conceptos básicos de grafos.

1. Representa un ciclo de orden 6

2. Añade una arista al grafo anterior entre los vértices 1 y 3

3. Quita la arista que has añadido y otra arista. ¿Es conexo el grafo obtenido?

4. Representa el grafo completo de orden 20

5. ¿Es de Euler el grafo completo de orden 11? , en caso de serlo obtener un ciclo de Euler.

3.-En la administración de una fábrica tenemos los siguientes puestos de trabajo:

1.-Directora de zona.

2.- Director general

3.- Subdirectora

4. y 5.- Secretarias.

6.- Jefe de personal.

7.- Administrativa.

8.- Telefonista.

9.- Portero.

10. y 11.- Técnicos de mantenimiento.

Las relaciones de influencia entre los distintos empleados la mostramos en el siguiente grafo:

¿Cuál es el conjunto total de relaciones de influencia, incluyendo las que se obtienen a través de otros intermediarios?

4.- Una agencia de Mudanzas oferta sus servicios desde Córdoba a algunas localidades de Andalucía. Por motivos de obras sólo se podrá circular en un sentido en algunas carreteras, siendo por tanto obligado tomar rutas alternativas. El único factor que se tendrá en cuenta a la hora de seleccionar la ruta es el kilometraje.

a.- ¿Qué recorrido elegirá la agencia de Mudanzas para ir desde Córdoba (notado por v1 en la tabla) a los distintos pueblos (vi i: 2,...,13 ) si el kilometraje de las vías en uso vienen representadas en la matriz de la tabla.

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10	V11	V12	V13
V1									85		58	50	61
V2			400		134	130
V3		400		62	96
V4			62		115					90
V5				115		47	122		111
V6		130			47		86
V7	137				122	86
V8											183
V9	85				111					67		40
V10				90					67
V11	58							183
V12	50
V13	160							112

b.- Dibuja el árbol que represente los recorridos anteriores.

5.- Consideramos el problema anterior de la agencia de Mudanzas con las modificaciones siguientes:

Una vez finalizadas las obras, la agencia se plantea un nuevo estudio de la situación, dando cierta prioridad al paso por los tramos recientemente arreglados. Para ello rebajará los costes en algunos tramos, llegando a cuantificar alguno con peso negativo. Si los costes asignados a los trayectos entre los diferentes pueblos son los de la tabla, ¿cuáles serán ahora los costes mínimos para ir de un lugar a otro?

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10	V11	V12	V13
V1							125		85		58	50	160
V2			315		134	130
V3		315		62	96
V4			62		115					97
V5		70	-40	115		47	122		111
V6		130			47		86
V7	125				122	86
V8											173		-2
V9	85				111					67		40
V10				97					67
V11	58							173
V12	50								-25
V13	160							12

6.- Sea G = (V, A)un grafo conexo con “n” vértices. ¿Cambian los caminos más cortos de un vértice a otro si a cada arista le sumamos una constante positiva?.

7.- Se puede aplicar el algoritmo de Floyd al grafo de matriz de pesos?

¿Cómo puedo saber , utilizando Mathematica si un grafo tiene un ciclo de longitud negativa?

8.-En la E.U.P. hay 7 asignaturas optativas que interesan a distintos cursos, por tanto se les debe poner un horario al que puedan asistir todos los interesados. Las asignaturas se imparten en la mañana del lunes y constan de una hora a la semana. La situación es la siguiente:

Optativa 1 interesa a 1º M.E. 2º EL. 1º I.

Optativa 2 interesa a 2º Mec. 3º Mec. 1ºE.L.

Optativa 3 interesa a 2º EL. 2º Mec. 2º I

Optativa 4 interesa a 3ºMec. 3ºI. 3º EL. 3ºM.E.

Optativa 5 interesa a 3ºI. 2ºI.

Optativa 6 interesa a 2ºI. 1ºI. 3ºI.

Optativa 7 interesa a 1ºM.E. 1ºMec. 1ºEL.

¿Cuál es mínimo número de horas necesario para impartir las 7 asignaturas?.

¿De cuantas formas podemos hacer el horario si disponemos de tres horas?

¿Y si disponemos de cuatro horas?

Hacer el mismo problema pero con las situación siguiente:

Optativa 1 interesa a 1º M.E. 2º EL. 1º I., 2ºMec, 3ºMec, 3ºI,

Optativa 2 interesa a 2º Mec. 3º Mec. 1º EL,

Optativa 3 interesa a 2º EL. 2º Mec. 2º I

Optativa 4 interesa a 3ºMec. 3ºI. 3º EL. 3ºM.E.

Optativa 5 interesa a 3ºI. 2ºI. 1ºM.E.

Optativa 6 interesa a 2ºI. 1ºI. 3ºI., 1ºMec

Optativa 7 interesa a 1ºM.E. 1ºMec. 1ºEL.

	Al	Gr	Ma	Ja	Co	Se	Ca	Hu
Al
Gr	130
Ma	258	90
Ja	208	85	210
C0	290	103	230	85
Se	360	190	170	190	58
Ca	410	250	270	310	170	75
Hu	525	310	350	400	220	75	90

9.- Se pretende conectar las 8 provincias andaluzas por medio de líneas férreas de alta velocidad. La tabla indica la distancia entre ciudades. Suponiendo que el costo por kilómetro es aproximadamente el mismo en cada trayecto, determínense las vías que habrán de construirse para minimizar presupuesto.

10.-a)Cinco estudiantes v, w, x, y, z , son miembros de cuatro comités c1, c2, c3, c4. Los miembros de c1 son v, x, y los de c2 son x, y, z, los de c3 son w, x , los de c4 son v, w, x, y, z. Cada comité debe enviar un representante a la administración. Un estudiante no puede representar a dos comités. Determinar los estudiantes elegidos para cada comisión. ¿Estarán todos representados?

b) El mismo problema pero con la situación de comités:

miembros de c1 son v, x, los de c2 son x, y,, los de c3 son x , los de c4 son v, w, x, y, z.

8.8.-ALGUNAS SOLUCIONES A LOS PROBLEMAS Y EJERCICIOS DEL TEMA 8

2.-

5.- Si es de Euler y un ciclo sería:

3.- Las relaciones de influencia vienen dadas por la matriz:

4.- el camino mas corto del vértice 1 al 1 es {1}

el camino mas corto del vértice 1 al 2 es {1,9,5,6,2}

el camino mas corto del vértice 1 al 3 es {1,9,10,4,3}

el camino mas corto del vértice 1 al 4 es {1,9,10,4}

el camino mas corto del vértice 1 al 5 es {1,9,5}

el camino mas corto del vértice 1 al 6 es {1,9,5,6}

el camino mas corto del vértice 1 al 7 es {1,9,5,7}

el camino mas corto del vértice 1 al 8 es {1,13,8}

el camino mas corto del vértice 1 al 9 es {1,9}

el camino mas corto del vértice 1 al 10 es {1,9,10}

el camino mas corto del vértice 1 al 11 es {1,11}

el camino mas corto del vértice 1 al 12 es {1,12}

5.- Aquí no se puede aplicar el algoritmo de Dijkstra porque hay pesos negativos.

La matriz que indica los costes mínimos de una localidad a otra es:

6.- Si cambian

8.- apartado a

el polinomio cromático es:

El número mínimo de horas es tres y con tres horas se pueden hacer 18 horarios. Con cuatro horas el número de horarios distintos es 552.

9.-

10.- apartado a: {{v , c₁},{w , c₃},{x , c₂},{y , c₄}}

apartado b: {{v , c₁},{w , c₄},{x , c₃},{y , c₂}}