Resolución de Problemas de Matemática Discreta y Teoría de Grafos con SageMath

1. Ejercicios de Combinatoria

1.1. Formación de Tribunales con Cargos Específicos

Tenemos que formar el tribunal que decidirá quién gana un premio. El tribunal está formado por 3 personas (la primera de ellas será el presidente; la segunda, el vocal; y la tercera, el secretario). Los candidatos y candidatas a formar parte del tribunal son: Alan Turing, Ada Lovelace, Sophie Germain, Al-Juarismi y Maria Agnesi.

¿Cuántos tribunales distintos podemos formar?

candidatos = ['Alan Turing', 'Ada Lovelace', 'Sophie Germain', 'Al-Juarismi', 'Maria Agnesi']
grupos3 = Permutations(candidatos, 3)
grupos3.list()
grupos3.cardinality()

¿En cuántos de estos tribunales Ada Lovelace es la presidenta y Sophie Germain la secretaria?

555 grupocondicion = [g for g in grupos3 if (g[0] == 'Ada Lovelace' and g[2] == 'Sophie Germain')] || grupocondicion

1.2. Distribución de Estudiantes en el Aula de Informática

En el aula de informática 3 de la EUPT, que tiene 28 ordenadores, se va a hacer una clase de prácticas de Matemática Discreta con 28 estudiantes. ¿De cuántas formas se podrán sentar los estudiantes?

numordenadores = 28
grupos = Permutations(numordenadores)
grupos
grupos.cardinality()

1.3. Organización de Partidos de Baloncesto

Tenemos seis equipos de baloncesto que denotamos de la siguiente forma: A, B, C, D, E y F. ¿Cuántos partidos se disputarán si cada equipo debe enfrentarse una única vez al resto de equipos? ¿Qué partidos tendrán lugar?

equipos = ['A', 'B', 'C', 'D', 'E', 'F']
grupo2 = Combinations(equipos, 2)
grupo2.list()
grupo2.cardinality()

1.4. Ordenación de Caracteres

¿De cuántas formas posibles podemos ordenar las letras de la palabra 'BIT'? Escribe las posibles formas como cadena de caracteres.

palabra = 'BIT'
grupos = Permutations(palabra)
grupos.cardinality()
palabras = [' '.join(elemento) for elemento in grupos]
palabras

2. Teoría de Grafos y Algoritmos

2.1. Creación de un Grafo Dirigido mediante Matriz de Adyacencia

Crea en Sage el siguiente grafo dirigido partiendo de su matriz de adyacencia.

M = matrix([[0,1,1,0,0], [0,0,1,0,0], [0,0,0,1,0], [0,0,0,0,1], [1,0,1,0,0]])

(La matriz que sea, cada corchete es un vértice y en cada vértice del grafo tienes que decir a qué vértice va cada arista).

g = DiGraph(M)
g.graphplot(edge_labels=False).show(figsize=4)

¿Existe algún camino que vaya de v1 a v5? En caso de que sí, encuentra el camino más corto.

from sage.graphs.base.boost_graph import shortest_paths
g.shortest_paths(0)

2.2. Componentes Conexas

Mostrar cuántas componentes conexas tiene el grafo:

cont_europe.connected_components_number()

2.3. Sólidos Platónicos y Grafos Hamiltonianos

Los sólidos platónicos presentan una proyección muy especial en el plano en forma de mapa. Comprueba que los grafos formados por la proyección del tetraedro y del octaedro son grafos hamiltonianos.

Grafo del Tetraedro:

g = graphs.TetrahedralGraph()
g.show()

Comprobamos que el grado de todos los nodos es mayor o igual a n/2:

n1 = g.num_verts()
n1

Tenemos 4 nodos (vértices).

grados1 = g.degree()
grados1

Todos los nodos tienen grado 3.

def esHamiltoniano(grados, n):
    for i in grados:
        if i < n/2:
            return False
    return True

esHamiltoniano(grados1, n1)

2.4. Grafo Dirigido con Pesos y Distancias

Crea en Sage el siguiente grafo dirigido partiendo de su matriz de adyacencia. Nota: no hace falta que le des a los nodos el nombre del dibujo.

Haces la matriz de adyacencia en función de cómo se llamen los nodos (a, b, c... o 0, 1, 2...) y en cada espacio del vector tienes que poner lo que te cuesta llegar a dicho vector desde el vector que estás. Ejemplo: si estás en el nodo A, hay 5 nodos y el nodo A tiene una distancia de 3 al nodo C, entonces el nodo A será así: [0,0,3,0,0].

M = Matrix([[0,1,2,0,0], [0,0,0,4,0], [3,9,0,2,0], [0,6,0,0,7], [10,0,5,0,0]])
M
g = DiGraph(M, format='weighted_adjacency_matrix')
g.graphplot(edge_labels=True).show(figsize=4)

¿Cuál es el camino más corto de A a D? ¿Y de S a B? ¿Cuál es el coste de cada ruta? Utiliza el método .distance(nodo_inicial, nodo_final, by_weight=True) para calcularlo.

g.distance(0, 3, by_weight=True)
g.distance(4, 1, by_weight=True)