Fundamentos de Combinatoria y Teoría de Grafos con SageMath

PRÁCTICA 1: COMBINATORIA

Combinaciones

Las combinaciones son listas de elementos distintos donde el orden no importa. Para crear combinaciones en SageMath, utilizamos la función Combinations(lista, numGrupo).

• Ejemplo: grupo = [1, 2, 3, 4]; c3 = Combinations(grupo, 3). Resultado: [Combinations of [1, 2, 3, 4] of length 3].
• Obtener lista de combinaciones: c3.list() produce [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]].
• Obtener cardinalidad: c3.cardinality() devuelve [4].
• Filtrado: Si queremos filtrar de la lista los que contengan el número ‘2’: for g in c3: if 2 in g: print(g). Resultado: [[1, 2, 3], [1, 2, 4], [2, 3, 4]].

Variaciones y Permutaciones

Se refieren a listas de elementos en un orden determinado.

Permutaciones

• Crear permutaciones: Permutations(lista).
• Ejemplo: lista = [2, 8, 3, 4]; p = Permutations(lista). Resultado: [Permutations of the set [2, 8, 3, 4]].
• Obtener lista: p.list() devuelve [[2, 8, 3, 4], [2, 8, 4, 3], [2, 3, 8, 4], ... [4, 3, 2, 8], [4, 3, 8, 2]].
• Cardinalidad: p.cardinality() devuelve [24].
• Filtrado específico: Para obtener permutaciones con un 2 en la segunda posición: p2 = [g for g in p if g[1] == 2]. Resultado: [[8, 2, 3, 4], [8, 2, 4, 3], [3, 2, 8, 4], [3, 2, 4, 8], [4, 2, 8, 3], [4, 2, 3, 8]].

Variaciones

• Crear variaciones: Se utiliza Permutations(lista, numGrupo).
• Ejemplo: lista = [1, 4, 6, 8]; v2 = Permutations(lista, 2). Resultado: [Permutations of the set [1, 4, 6, 8] of length 2].
• Obtener lista: v2.list() devuelve [[1, 4], [1, 6], [1, 8], [4, 1], [4, 6], [4, 8], [6, 1], [6, 4], [6, 8], [8, 1], [8, 4], [8, 6]].
• Cardinalidad: v2.cardinality() devuelve [12].

La fórmula matemática de las variaciones es V(n, r) = n! / (n - r)!. En SageMath: n = 4 | r = 2 | num = factorial(n) | den = factorial(n - r) | var = num / den.

EJERCICIOS DE COMBINATORIA

1. Formación de un tribunal: Se debe formar un tribunal de 3 personas (presidente, vocal y secretario) a partir de los candidatos: 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']
• candidatos3 = Permutations(candidatos, 3)
• Cardinalidad: candidatos3.cardinality() devuelve 60.
• Caso específico: ¿En cuántos Ada Lovelace es presidenta y Sophie Germain secretaria? resultado = [g for g in candidatos3 if (g[0] == 'Ada Lovelace' and g[2] == 'Sophie Germain')]. Resultado: [['Ada Lovelace', 'Alan Turing', 'Sophie Germain'], ['Ada Lovelace', 'Al-Juarismi', 'Sophie Germain'], ['Ada Lovelace', 'Maria Agnesi', 'Sophie Germain']]. El total es len(resultado), que es 3.

2. Distribución en aula: En un aula con 28 ordenadores y 28 estudiantes, ¿de cuántas formas se pueden sentar?

• permutaciones = Permutations(28)
• permutaciones.cardinality(): 304888344611713860501504000000.
• Comprobación con factorial: factorial(28) == permutaciones.cardinality() devuelve True.

3. Torneo de baloncesto: Seis equipos (A, B, C, D, E, F) se enfrentan una sola vez entre ellos.

• equipos = ['A', 'B', 'C', 'D', 'E', 'F']
• parejasEquipos = Combinations(equipos, 2)
• Total de partidos: parejasEquipos.cardinality() es 15.
• Lista de partidos: [['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'], ['A', 'F'], ['B', 'C'], ['B', 'D'], ['B', 'E'], ['B', 'F'], ['C', 'D'], ['C', 'E'], ['C', 'F'], ['D', 'E'], ['D', 'F'], ['E', 'F']].

4. Ordenación de letras: ¿De cuántas formas podemos ordenar las letras de la palabra ‘BIT’?

• palabra = 'BIT'; grupos = Permutations(palabra).
• Lista: [['B', 'I', 'T'], ['B', 'T', 'I'], ['I', 'B', 'T'], ['I', 'T', 'B'], ['T', 'B', 'I'], ['T', 'I', 'B']].
• Como cadenas: cadenas = [''.join(elemento) for elemento in grupos]. Resultado: ['BIT', 'BTI', 'IBT', 'ITB', 'TBI', 'TIB'].

PRÁCTICA 2: TEORÍA DE GRAFOS

Definición y Representación

Podemos definir un grafo con Graph() y añadir aristas con g.add_edge().

• Ejemplo manual: g = Graph({}); l = [(1, 5), (1, 6), (1, 7), (1, 8), (2, 5), (2, 6), (2, 7), (2, 8), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8)]; for arista in l: g.add_edge(arista).
• Visualización: g.show(figsize=8).
• Matriz de adyacencia: Representa conexiones con 1 y ausencias con 0. M = matrix([[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]); g = Graph(M); g.show().

Grafos Dirigidos y Pesados

Para grafos dirigidos usamos DiGraph().

• Ejemplo con etiquetas: stnc = 'abcdeba'; g = DiGraph({}); for x, y in [(stnc[i], stnc[i+1]) for i in range(len(stnc)-1)]: g.add_edge(x, y, y).
• Grafos pesados: M = matrix([[0, 2, 0, 1], [2, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]); g = Graph(M, format='weighted_adjacency_matrix'); g.graphplot(edge_labels=True).show().

Generación de Grafos y Sólidos Platónicos

Sage incluye funciones para grafos conocidos:

• Grafo completo: g = graphs.CompleteGraph(5).
• Mapa de Europa: cont_europe = graphs.EuropeMap(continental=True). Para verificar vecindad: cont_europe.has_edge("Vatican City", "Italy") devuelve True.
• Sólidos Platónicos: Se pueden visualizar con tetrahedron(), octahedron(), cube(), dodecahedron() e icosahedron(). Sus grafos correspondientes se obtienen con graphs.TetrahedralGraph(), graphs.OctahedralGraph(), etc.

Problema del Camino más Corto

Utilizamos shortest_paths para encontrar rutas óptimas.

• Ejemplo: from sage.graphs.base.boost_graph import shortest_paths.
• M = matrix([[0, 2, 0, 1, 0], [0, 0, 1, 0, 0], [1, 3, 0, 2, 0], [3, 2, 1, 0, 1], [4, 1, 2, 2, 0]]).
• g = DiGraph(M, format='weighted_adjacency_matrix').
• g.shortest_paths(1, by_weight=True) devuelve las rutas desde el nodo 1.

EJERCICIOS DE GRAFOS

1. Matriz de adyacencia y camino corto:

• 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]]).
• g = DiGraph(M).
• Camino de v1 a v5: g.shortest_paths(0). Resultado para el nodo 4: [0, 2, 3, 4].

2. Mapa de Europa no continental:

• cont_europe = graphs.EuropeMap(continental=False).
• Componentes conexas: cont_europe.connected_components_number() devuelve 4.
• Interpretación: Los nodos no conectados representan islas.

3. Grafos Hamiltonianos: Comprobación para el tetraedro y octaedro.

• Función de verificación:

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

• Pasos: g = graphs.TetrahedralGraph(); n1 = g.num_verts(); grados1 = g.degree(); esHamiltoniano(grados1, n1).

4. Grafo dirigido pesado:

• M = Matrix([[1, 1, 0, 2, 0], [0, 0, 4, 0, 0], [0, 6, 0, 0, 7], [3, 9, 2, 0, 0], [10, 0, 0, 5, 0]]).
• g = DiGraph(M, format='weighted_adjacency_matrix').
• Camino más corto de A (0) a D (3): g.shortest_paths(0, by_weight=True). Resultado: {3: [0, 3]}.
• Coste de la ruta a C (2): g.distance(0, 2, by_weight=True) devuelve 4.