55.2.1 Construyendo grafos

Función: create_graph (v_list, e_list) ¶

Función: create_graph (n, e_list) ¶

Función: create_graph (v_list, e_list, directed) ¶

Crea un nuevo grafo sobre el conjunto de vértices v_list con aristas e_list.

v_list es una lista de vértices ([v1, v2,..., vn]) o una lista de vértices junto con sus respectivas etiquetas ([[v1,l1], [v2,l2],..., [vn,ln]]).

n es el número de vértices, los cuales se identificarán desde 0 hasta n-1.

e_list es una lista de aristas ([e1, e2,..., em]) o una lista de aristas con sus respectivas ponderaciones ([[e1, w1], ..., [em, wm]]).

Si directed is not false, se devolverá un grafo orientado.

Ejemplos:

Crea un ciclo de 3 vértices.

(%i1) load ("graphs")$
(%i2) g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
(%i3) print_graph(g)$
Graph on 3 vertices with 3 edges.
Adjacencies:
  3 :  1  2
  2 :  3  1
  1 :  3  2

Crea un ciclo de 3 vértices y aristas ponderadas:

(%i1) load ("graphs")$
(%i2) g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
                                [[1,3], 3.0]])$
(%i3) print_graph(g)$
Graph on 3 vertices with 3 edges.
Adjacencies:
  3 :  1  2
  2 :  3  1
  1 :  3  2

Crea un grafo orientado:

(%i1) load ("graphs")$
(%i2) d : create_graph(
       [1,2,3,4], 
       [
        [1,3], [1,4],
        [2,3], [2,4]
       ],
       'directed = true)$
(%i3) print_graph(d)$
Digraph on 4 vertices with 4 arcs.
Adjacencies:
  4 :
  3 :
  2 :  4  3
  1 :  4  3

Función: copy_graph (g) ¶

Devuelve una copia del grafo g.

Función: circulant_graph (n, d) ¶

Devuelve un grafo cirlulante de parámetros n y d.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : circulant_graph(10, [1,3])$
(%i3) print_graph(g)$
Graph on 10 vertices with 20 edges.
Adjacencies:
  9 :  2  6  0  8
  8 :  1  5  9  7
  7 :  0  4  8  6
  6 :  9  3  7  5
  5 :  8  2  6  4
  4 :  7  1  5  3
  3 :  6  0  4  2
  2 :  9  5  3  1
  1 :  8  4  2  0
  0 :  7  3  9  1

Función: clebsch_graph () ¶

Devuelve el grafo de Clebsch.

Función: complement_graph (g) ¶

Devuelve el complemento del grafo g.

Función: complete_bipartite_graph (n, m) ¶

Devuelve el grafo bipartido completo de n+m vértices.

Función: complete_graph (n) ¶

Devuelve el grafo completo de n vértices.

Función: cycle_digraph (n) ¶

Devuelve el ciclo dirigido de n vértices.

Función: cycle_graph (n) ¶

Devuelve el ciclo de n vértices.

Función: cuboctahedron_graph (n) ¶

Devuelve el grafo cubooctaédrico.

Función: cube_graph (n) ¶

Devuelve el cubo de n dimensiones.

Función: dodecahedron_graph () ¶

Devuelve el grafo del dodecaedro.

Función: empty_graph (n) ¶

Devuelve el grafo vacío de n vértices.

Función: flower_snark (n) ¶

Devuelve el grafo de flor de 4n vértices.

Ejemplo:

(%i1) load ("graphs")$
(%i2) f5 : flower_snark(5)$
(%i3) chromatic_index(f5);
(%o3)                                  4

Función: from_adjacency_matrix (A) ¶

Devuelve el grafo definido por la matriz de adyacencia A.

Función: frucht_graph () ¶

Devuelve el grafo de Frucht.

Función: graph_product (g1, g1) ¶

Devuelve el producto dirigido de los grafos g1 y g2.

Ejemplo:

(%i1) load ("graphs")$
(%i2) grid : graph_product(path_graph(3), path_graph(4))$
(%i3) draw_graph(grid)$

Función: graph_union (g1, g1) ¶

Devuelve la unión (suma) de los grafos g1 y g2.

Función: grid_graph (n, m) ¶

Devuelve la rejilla n x m.

Función: great_rhombicosidodecahedron_graph () ¶

Devuelve el grafo gran rombicosidodecaédrico.

Función: great_rhombicuboctahedron_graph () ¶

Devuelve el grafo gran rombicocubicooctaédrico.

Función: grotzch_graph () ¶

Devuelve el grafo de Grotzch.

Función: heawood_graph () ¶

Devuelve el grafo de Heawood.

Función: icosahedron_graph () ¶

Devuelve el grafo icosaédrico.

Función: icosidodecahedron_graph () ¶

Devuelve el grafo icosidodecaédrico.

Función: induced_subgraph (V, g) ¶

Devuelve el grafo inducido por el subconjunto V de vértices del grafo g.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) V : [0,1,2,3,4]$
(%i4) g : induced_subgraph(V, p)$
(%i5) print_graph(g)$
Graph on 5 vertices with 5 edges.
Adjacencies:
  4 :  3  0
  3 :  2  4
  2 :  1  3
  1 :  0  2
  0 :  1  4

Función: line_graph (g) ¶

Devuelve el grafo de línea del grafo g.

Función: make_graph (vrt, f) ¶

Función: make_graph (vrt, f, oriented) ¶

Crea un grafo por medio de la función de predicado f.

vrt es una lista o conjunto de vértices o un simplemente un número entero. Si vrt es un número entero, entonces los vértices del grafo serán los enteros desde 1 hasta vrt.

f es una función de predicado. Dos vértices a y b se conectarán si f(a,b)=true.

Si directed no es false, entonces en grafo será dirigido.

Ejemplo 1:

(%i1) load("graphs")$
(%i2) g : make_graph(powerset({1,2,3,4,5}, 2), disjointp)$
(%i3) is_isomorphic(g, petersen_graph());
(%o3)                         true
(%i4) get_vertex_label(1, g);
(%o4)                        {1, 2}

Ejemplo 2:

(%i1) load("graphs")$
(%i2) f(i, j) := is (mod(j, i)=0)$
(%i3) g : make_graph(20, f, directed=true)$
(%i4) out_neighbors(4, g);
(%o4)                    [8, 12, 16, 20]
(%i5) in_neighbors(18, g);
(%o5)                    [1, 2, 3, 6, 9]

Función: mycielski_graph (g) ¶

Devuelve el grafo de Mycielski del grafo g.

Función: new_graph () ¶

Devuelve el grafo sin vértices ni aristas.

Función: path_digraph (n) ¶

Devuelve el camino dirigido de n vértices.

Función: path_graph (n) ¶

Devuelve el camino de n vértices.

Función: petersen_graph () ¶

Función: petersen_graph (n, d) ¶

Devuelve el grafo de Petersen P_{n,d}. Los valores por defecto para n y d son n=5 y d=2.

Función: random_bipartite_graph (a, b, p) ¶

Devuelve un grafo aleatorio bipartido a partir de los vértices a+b. Cada arista se genera con probabilidad p.

Función: random_digraph (n, p) ¶

Devuelve un grafo aleatorio dirigido de n vértices. Cada arco se presenta con una probabilidad p.

Función: random_regular_graph (n) ¶

Función: random_regular_graph (n, d) ¶

Devuelve un grafo aleatorio d-regular de n vértices. El valor por defecto para d es d=3.

Función: random_graph (n, p) ¶

Devuelve un grafo aleatorio de n vértices. Cada arco se presenta con una probabilidad p.

Función: random_graph1 (n, m) ¶

Devuelve un grafo aleatorio de n vértices y m arcos aleatorios.

Función: random_network (n, p, w) ¶

Devuelve una red aleatoria de n vértices. Cada arco se presenta con probabilidad p y tiene un peso dentro del rango [0,w]. La función devuelve una lista [network, source, sink].

Ejemplo:

(%i1) load ("graphs")$
(%i2) [net, s, t] : random_network(50, 0.2, 10.0);
(%o2)                         [DIGRAPH, 50, 51]
(%i3) max_flow(net, s, t)$
(%i4) first(%);
(%o4)                   27.65981397932507

Función: random_tournament (n) ¶

Devuelve un torneo aleatorio de n vértices.

Función: random_tree (n) ¶

Devuelve un árbol aleatorio de n vértices.

Función: small_rhombicosidodecahedron_graph () ¶

Devuelve el grafo pequeño rombicosidodecaédrico.

Función: small_rhombicuboctahedron_graph () ¶

Devuelve el grafo pequeño rombicocubicooctaédrico.

Función: snub_cube_graph () ¶

Devuelve el grafo cúbico volteado.

Función: snub_dodecahedron_graph () ¶

Devuelve el grafo dodecaédrico volteado.

Función: truncated_cube_graph () ¶

Devuelve el grafo cúbico truncado.

Función: truncated_dodecahedron_graph () ¶

Devuelve el grafo dodecaédrico truncado.

Función: truncated_icosahedron_graph () ¶

Devuelve el grafo icosaédrico truncado.

Función: truncated_tetrahedron_graph () ¶

Devuelve el grafo del tetraedro truncado.

Función: tutte_graph () ¶

Devuelve el grafo de Tutte.

Función: underlying_graph (g) ¶

Devuelve el grafo asociado al grafo orientado g.

Función: wheel_graph (n) ¶

Devuelve el grafo de rueda de n+1 vértices.

55.2.2 Propiedades de los grafos

Función: adjacency_matrix (gr) ¶

Devuelve la matriz de adyacencia del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c5 : cycle_graph(4)$
(%i3) adjacency_matrix(c5);
                                [ 0  1  0  1 ]
                                [            ]
                                [ 1  0  1  0 ]
(%o3)                           [            ]
                                [ 0  1  0  1 ]
                                [            ]
                                [ 1  0  1  0 ]

Función: average_degree (gr) ¶

Devuelve el grado medio de los vértices del garfo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) average_degree(grotzch_graph());
                                      40
(%o2)                                 --
                                      11

Función: biconnected_components (gr) ¶

Devuelve los subconjuntos de vértices biconectados del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph(
            [1,2,3,4,5,6,7],
            [
             [1,2],[2,3],[2,4],[3,4],
             [4,5],[5,6],[4,6],[6,7]
            ])$
(%i3) biconnected_components(g);
(%o3)               [[6, 7], [4, 5, 6], [1, 2], [2, 3, 4]]

Función: bipartition (gr) ¶

Devuelve una bipartición de los vértices del grafo gr, o una lista vacía si gr no es bipartido.

Ejemplo:

(%i1) load ("graphs")$
(%i2) h : heawood_graph()$
(%i3) [A,B]:bipartition(h);
(%o3)         [[8, 12, 6, 10, 0, 2, 4], [13, 5, 11, 7, 9, 1, 3]]
(%i4) draw_graph(h, show_vertices=A, program=circular)$

Función: chromatic_index (gr) ¶

Devuelve el índice cromático del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) chromatic_index(p);
(%o3)                                  4

Función: chromatic_number (gr) ¶

Devuelve el número cromático del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) chromatic_number(cycle_graph(5));
(%o2)                                  3
(%i3) chromatic_number(cycle_graph(6));
(%o3)                                  2

Función: clear_edge_weight (e, gr) ¶

Elimina el peso del arco e del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
(%i3) get_edge_weight([0,1], g);
(%o3)                                 1.5
(%i4) clear_edge_weight([0,1], g)$
(%i5) get_edge_weight([0,1], g);
(%o5)                                  1

Función: clear_vertex_label (v, gr) ¶

Elimina la etiqueta del vértice v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
(%i3) get_vertex_label(0, g);
(%o3)                               Zero
(%i4) clear_vertex_label(0, g);
(%o4)                               done
(%i5) get_vertex_label(0, g);
(%o5)                               false

Función: connected_components (gr) ¶

Devuelve las componentes conexas del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g: graph_union(cycle_graph(5), path_graph(4))$
(%i3) connected_components(g);
(%o3)                  [[1, 2, 3, 4, 0], [8, 7, 6, 5]]

Función: diameter (gr) ¶

Devuelve el diámetro del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) diameter(dodecahedron_graph());
(%o2)                                 5

Función: edge_coloring (gr) ¶

Devuelve una coloración óptima de los arcos del grafo gr.

La función devuelve el índice cromático y una lista que representa el coloreado de los arcos de gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) [ch_index, col] : edge_coloring(p);
(%o3) [4, [[[0, 5], 3], [[5, 7], 1], [[0, 1], 1], [[1, 6], 2], 
[[6, 8], 1], [[1, 2], 3], [[2, 7], 4], [[7, 9], 2], [[2, 3], 2], 
[[3, 8], 3], [[5, 8], 2], [[3, 4], 1], [[4, 9], 4], [[6, 9], 3], 
[[0, 4], 2]]]
(%i4) assoc([0,1], col);
(%o4)                           1
(%i5) assoc([0,5], col);
(%o5)                           3

Función: degree_sequence (gr) ¶

Devuelve una lista con los grados de los vértices del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) degree_sequence(random_graph(10, 0.4));
(%o2)            [2, 2, 2, 2, 2, 2, 3, 3, 3, 3]

Función: edge_connectivity (gr) ¶

Devuelve la conectividad de las aristas del grafo gr.

Véase también min_edge_cut.

Función: edges (gr) ¶

Devuelve la lista de las aristas (arcos) del grafo (dirigido) gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) edges(complete_graph(4));
(%o2)         [[2, 3], [1, 3], [1, 2], [0, 3], [0, 2], [0, 1]]

Función: get_edge_weight (e, gr) ¶

Función: get_edge_weight (e, gr, ifnot) ¶

Devuelve el peso de la arista e del grafo gr.

Si la arista no tiene peso, la función devuelve 1. Si la arista no pertenece al grafo, la función emite un mensaje de error o devuelve el argumento opcional ifnot.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c5 : cycle_graph(5)$
(%i3) get_edge_weight([1,2], c5);
(%o3)                                 1
(%i4) set_edge_weight([1,2], 2.0, c5);
(%o4)                               done
(%i5) get_edge_weight([1,2], c5);
(%o5)                                2.0

Función: get_vertex_label (v, gr) ¶

Devuelve la etiqueta del vértice v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
(%i3) get_vertex_label(0, g);
(%o3)                               Zero

Función: graph_charpoly (gr, x) ¶

Devuelve el polinomio característico (de variable x) del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) graph_charpoly(p, x), factor;
                                         5        4
(%o3)                     (x - 3) (x - 1)  (x + 2)

Función: graph_center (gr) ¶

Devuelve el centro del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : grid_graph(5,5)$
(%i3) graph_center(g);
(%o3)                               [12]

Función: graph_eigenvalues (gr) ¶

Devuelve los valores propios del grafo gr. La función devuelve los valores propios en el mismo formato en el que lo hace la función eigenvalue.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) graph_eigenvalues(p);
(%o3)                     [[3, - 2, 1], [1, 4, 5]]

Función: graph_periphery (gr) ¶

Devuelve la periferia del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : grid_graph(5,5)$
(%i3) graph_periphery(g);
(%o3)                          [24, 20, 4, 0]

Función: graph_size (gr) ¶

Devuelve el número de aristas del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) graph_size(p);
(%o3)                                15

Función: graph_order (gr) ¶

Devuelve el número de vértices del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) graph_order(p);
(%o3)                                10

Función: girth (gr) ¶

Devuelve la longitud del ciclo más corto del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : heawood_graph()$
(%i3) girth(g);
(%o3)                                 6

Función: hamilton_cycle (gr) ¶

Devuelve el ciclo de Hamilton del grafo gr o una lista vacía si gr no es hamiltoniano.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c : cube_graph(3)$
(%i3) hc : hamilton_cycle(c);
(%o3)              [7, 3, 2, 6, 4, 0, 1, 5, 7]
(%i4) draw_graph(c, show_edges=vertices_to_cycle(hc))$

Función: hamilton_path (gr) ¶

Devuelve el camino de Hamilton del grafo gr o una lista vacía si gr no los tiene.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) hp : hamilton_path(p);
(%o3)                  [0, 5, 7, 2, 1, 6, 8, 3, 4, 9]
(%i4) draw_graph(p, show_edges=vertices_to_path(hp))$

Función: isomorphism (gr1, gr2) ¶

Devuelve un isomorfismo entre los grafos/digrafos gr1 y gr2. Si gr1 y gr2 no son isomorfos, devuelve una lista vacía.

Ejemplo:

(%i1) load ("graphs")$
(%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
(%i3) isomorphism(clk5, petersen_graph());
(%o3) [9 -> 0, 2 -> 1, 6 -> 2, 5 -> 3, 0 -> 4, 1 -> 5, 3 -> 6, 
                                          4 -> 7, 7 -> 8, 8 -> 9]

Función: in_neighbors (v, gr) ¶

Devuelve la lista de los nodos hijos del vértice v del grafo orientado gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : path_digraph(3)$
(%i3) in_neighbors(2, p);
(%o3)                                 [1]
(%i4) out_neighbors(2, p);
(%o4)                                 []

Función: is_biconnected (gr) ¶

Devuelve true si gr está biconectado y false en caso contrario.

Ejemplo:

Example:

(%i1) load ("graphs")$
(%i2) is_biconnected(cycle_graph(5));
(%o2)                         true
(%i3) is_biconnected(path_graph(5));
(%o3)                         false

Función: is_bipartite (gr) ¶

Devuelve true si gr es bipartido (2-coloreable) y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_bipartite(petersen_graph());
(%o2)                               false
(%i3) is_bipartite(heawood_graph());
(%o3)                               true

Función: is_connected (gr) ¶

Devuelve true si el grafo gr es conexo y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_connected(graph_union(cycle_graph(4), path_graph(3)));
(%o2)                               false

Función: is_digraph (gr) ¶

Devuelve true si gr es un grafo orientado (digrafo) y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_digraph(path_graph(5));
(%o2)                               false
(%i3) is_digraph(path_digraph(5));
(%o3)                               true

Función: is_edge_in_graph (e, gr) ¶

Devuelve true si e es una arista (arco) del grafo (digrafo) g y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c4 : cycle_graph(4)$
(%i3) is_edge_in_graph([2,3], c4);
(%o3)                               true
(%i4) is_edge_in_graph([3,2], c4);
(%o4)                               true
(%i5) is_edge_in_graph([2,4], c4);
(%o5)                               false
(%i6) is_edge_in_graph([3,2], cycle_digraph(4));
(%o6)                               false

Función: is_graph (gr) ¶

Devuelve true si gr es un grafo y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_graph(path_graph(5));
(%o2)                               true
(%i3) is_graph(path_digraph(5));
(%o3)                               false

Función: is_graph_or_digraph (gr) ¶

Devuelve true si gr es una grafo, orientado o no, y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_graph_or_digraph(path_graph(5));
(%o2)                               true
(%i3) is_graph_or_digraph(path_digraph(5));
(%o3)                               true

Función: is_isomorphic (gr1, gr2) ¶

Devuelve true si los grafos/digrafos gr1 y gr2 son isomorfos y false en caso contrario.

Véase también isomorphism.

Ejemplo:

(%i1) load ("graphs")$
(%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
(%i3) is_isomorphic(clk5, petersen_graph());
(%o3)                         true

Función: is_planar (gr) ¶

Devuelve true si gr es un grafo planar y false en caso contrario.

El algoritmo utilizado es el de Demoucron, que es de tiempo cuadrático.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_planar(dodecahedron_graph());
(%o2)                                true
(%i3) is_planar(petersen_graph());
(%o3)                                false
(%i4) is_planar(petersen_graph(10,2));
(%o4)                                true

Función: is_sconnected (gr) ¶

Devuelve true si el grafo orientado gr es fuertemente conexo, devolviendo false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_sconnected(cycle_digraph(5));
(%o2)                               true
(%i3) is_sconnected(path_digraph(5));
(%o3)                               false

Función: is_vertex_in_graph (v, gr) ¶

Devuelve true si v es un vértice del grafo g y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c4 : cycle_graph(4)$
(%i3) is_vertex_in_graph(0, c4);
(%o3)                               true
(%i4) is_vertex_in_graph(6, c4);
(%o4)                               false

Función: is_tree (gr) ¶

Devuelve true si gr es un árbol y false en caso contrario.

Ejemplo:

(%i1) load ("graphs")$
(%i2) is_tree(random_tree(4));
(%o2)                               true
(%i3) is_tree(graph_union(random_tree(4), random_tree(5)));
(%o3)                               false

Función: laplacian_matrix (gr) ¶

Devuelve el laplaciano de la matriz del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) laplacian_matrix(cycle_graph(5));
                          [  2   - 1   0    0   - 1 ]
                          [                         ]
                          [ - 1   2   - 1   0    0  ]
                          [                         ]
(%o2)                     [  0   - 1   2   - 1   0  ]
                          [                         ]
                          [  0    0   - 1   2   - 1 ]
                          [                         ]
                          [ - 1   0    0   - 1   2  ]

Función: max_clique (gr) ¶

Devuelve el clique máximo del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : random_graph(100, 0.5)$
(%i3) max_clique(g);
(%o3)       [6, 12, 31, 36, 52, 59, 62, 63, 80]

Función: max_degree (gr) ¶

Devuelve el grado máximo de los vértices del grafo gr y un vértice de grado máximo.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : random_graph(100, 0.02)$
(%i3) max_degree(g);
(%o3)                        [6, 79]
(%i4) vertex_degree(95, g);
(%o4)                           3

Función: max_flow (net, s, t) ¶

Devuelve el flujo maximal de la red net con origen en s y final en t.

La función devuelve el valor del flujo maximal y una lista con los pesos de los arcos del flujo óptimo.

Ejemplo:

Example:

(%i1) load ("graphs")$
(%i2) net : create_graph(
  [1,2,3,4,5,6],
  [[[1,2], 1.0],
   [[1,3], 0.3],
   [[2,4], 0.2],
   [[2,5], 0.3],
   [[3,4], 0.1],
   [[3,5], 0.1],
   [[4,6], 1.0],
   [[5,6], 1.0]],
  directed=true)$
(%i3) [flow_value, flow] : max_flow(net, 1, 6);
(%o3) [0.7, [[[1, 2], 0.5], [[1, 3], 0.2], [[2, 4], 0.2],
[[2, 5], 0.3], [[3, 4], 0.1], [[3, 5], 0.1], [[4, 6], 0.3],
[[5, 6], 0.4]]]
(%i4) fl : 0$
(%i5) for u in out_neighbors(1, net) 
         do fl : fl + assoc([1, u], flow)$
(%i6) fl;
(%o6)                                 0.7

Función: max_independent_set (gr) ¶

Devuelve un conjunto maximal independiente de vértices del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) d : dodecahedron_graph()$
(%i3) mi : max_independent_set(d);
(%o3)             [0, 3, 5, 9, 10, 11, 18, 19]
(%i4) draw_graph(d, show_vertices=mi)$

Función: max_matching (gr) ¶

Devuelve un conjunto maximal independiente de aristas del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) d : dodecahedron_graph()$
(%i3) m : max_matching(d);
(%o3) [[5, 7], [8, 9], [6, 10], [14, 19], [13, 18], [12, 17], 
                               [11, 16], [0, 15], [3, 4], [1, 2]]
(%i4) draw_graph(d, show_edges=m)$

Función: min_degree (gr) ¶

Devuelve el grado mínimo de los vértices del grafo gr y un vértice de grado mínimo.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : random_graph(100, 0.1)$
(%i3) min_degree(g);
(%o3)                              [3, 49]
(%i4) vertex_degree(21, g);
(%o4)                                 9

Función: min_edge_cut (gr) ¶

Devuelve el mínimo edge cut del grafo gr. Un edge cut es un conjunto de aristas cuya eliminación aumenta el número de componentes del grafo.

Véase también edge_connectivity.

Función: min_vertex_cover (gr) ¶

Devuelve el mínimo nodo covering del grafo gr.

Función: min_vertex_cut (gr) ¶

Devuelve el mínimo vertex cut del grafo gr.

Véase también vertex_connectivity.

Función: minimum_spanning_tree (gr) ¶

Devuelve el grafo de expansión mínimo del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : graph_product(path_graph(10), path_graph(10))$
(%i3) t : minimum_spanning_tree(g)$
(%i4) draw_graph(g, show_edges=edges(t))$

Función: neighbors (v, gr) ¶

Devuelve la lista de los vecinos del vértice v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : petersen_graph()$
(%i3) neighbors(3, p);
(%o3)                             [4, 8, 2]

Función: odd_girth (gr) ¶

Devuelve la longitud del ciclo impar más corto del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : graph_product(cycle_graph(4), cycle_graph(7))$
(%i3) girth(g);
(%o3)                                 4
(%i4) odd_girth(g);
(%o4)                                 7

Función: out_neighbors (v, gr) ¶

Devuelve la lista de los nodos padres del vértice v del grafo orientado gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : path_digraph(3)$
(%i3) in_neighbors(2, p);
(%o3)                                 [1]
(%i4) out_neighbors(2, p);
(%o4)                                 []

Función: planar_embedding (gr) ¶

Devuelve la lista de caminos faciales en una proyección planar de gr, o false si gr no es un grafo planar.

El grafo gr debe estar biconectado.

El algoritmo utilizado es el de Demoucron, que es de tiempo cuadrático.

Ejemplo:

(%i1) load ("graphs")$
(%i2) planar_embedding(grid_graph(3,3));
(%o2) [[3, 6, 7, 8, 5, 2, 1, 0], [4, 3, 0, 1], [3, 4, 7, 6], 
                                      [8, 7, 4, 5], [1, 2, 5, 4]]

Función: print_graph (gr) ¶

Muestra alguna información sobre el grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c5 : cycle_graph(5)$
(%i3) print_graph(c5)$
Graph on 5 vertices with 5 edges.
Adjacencies:
  4 :  0  3
  3 :  4  2
  2 :  3  1
  1 :  2  0
  0 :  4  1
(%i4) dc5 : cycle_digraph(5)$
(%i5) print_graph(dc5)$
Digraph on 5 vertices with 5 arcs.
Adjacencies:
  4 :  0
  3 :  4
  2 :  3
  1 :  2
  0 :  1
(%i6) out_neighbors(0, dc5);
(%o6)                                [1]

Función: radius (gr) ¶

Devuelve el radio del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) radius(dodecahedron_graph());
(%o2)                                 5

Función: set_edge_weight (e, w, gr) ¶

Asigna el peso w a la arista e del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph([1, 2], [[[1,2], 1.2]])$
(%i3) get_edge_weight([1,2], g);
(%o3)                                1.2
(%i4) set_edge_weight([1,2], 2.1, g);
(%o4)                               done
(%i5) get_edge_weight([1,2], g);
(%o5)                                2.1

Función: set_vertex_label (v, l, gr) ¶

Asigna la etiqueta l al vértice v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
(%i3) get_vertex_label(1, g);
(%o3)                                One
(%i4) set_vertex_label(1, "oNE", g);
(%o4)                               done
(%i5) get_vertex_label(1, g);
(%o5)                                oNE

Función: shortest_path (u, v, gr) ¶

Devuelve el camino más corto desde u hasta v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) d : dodecahedron_graph()$
(%i3) path : shortest_path(0, 7, d);
(%o3)                          [0, 1, 19, 13, 7]
(%i4) draw_graph(d, show_edges=vertices_to_path(path))$

Función: shortest_weighted_path (u, v, gr) ¶

Devuelve la longitud del camino más corto ponderado y el propio camino más corto ponderado desde u hasta v en el grafo gr.

La longitud del camino ponderado es la suma de los pesos de las aristas del camino. Si una arista no tiene peso asignado, su valor por defecto es la unidad.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g: petersen_graph(20, 2)$
(%i3) for e in edges(g) do set_edge_weight(e, random(1.0), g)$
(%i4) shortest_weighted_path(0, 10, g);
(%o4) [2.575143920268482, [0, 20, 38, 36, 34, 32, 30, 10]]

Función: strong_components (gr) ¶

Devuelve las componentes fuertes del grafo orientado gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) t : random_tournament(4)$
(%i3) strong_components(t);
(%o3)                         [[1], [0], [2], [3]]
(%i4) vertex_out_degree(3, t);
(%o4)                                 3

Función: topological_sort (dag) ¶

Devuelve el orden topológico de los vértices del grafo orientado dag o una lista vacía si dag no es un grafo orientado acíclico.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g:create_graph(
         [1,2,3,4,5],
         [
          [1,2], [2,5], [5,3],
          [5,4], [3,4], [1,3]
         ],
         directed=true)$
(%i3) topological_sort(g);
(%o3)                           [1, 2, 5, 3, 4]

Función: vertex_connectivity (g) ¶

Devuelve la conectividad de los vértices del grafo g.

Véase también min_vertex_cut.

Función: vertex_degree (v, gr) ¶

Devuelve el grado del vértice v del grafo gr.

Función: vertex_distance (u, v, gr) ¶

Devuelve la longitud del camino más corto entre u y v del grafo o digrafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) d : dodecahedron_graph()$
(%i3) vertex_distance(0, 7, d);
(%o3)                                 4
(%i4) shortest_path(0, 7, d);
(%o4)                         [0, 1, 19, 13, 7]

Función: vertex_eccentricity (v, gr) ¶

Devuelve la excentricidad del vértice v del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g:cycle_graph(7)$
(%i3) vertex_eccentricity(0, g);
(%o3)                           3

Función: vertex_in_degree (v, gr) ¶

Devuelve el grado de entrada del vértice v del grafo orientado gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p5 : path_digraph(5)$
(%i3) print_graph(p5)$
Digraph on 5 vertices with 4 arcs.
Adjacencies:
  4 :
  3 :  4
  2 :  3
  1 :  2
  0 :  1
(%i4) vertex_in_degree(4, p5);
(%o4)                                 1
(%i5) in_neighbors(4, p5);
(%o5)                                [3]

Función: vertex_out_degree (v, gr) ¶

Devuelve el grado de salida del vértice v del grafo orientado gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) t : random_tournament(10)$
(%i3) vertex_out_degree(0, t);
(%o3)                           2
(%i4) out_neighbors(0, t);
(%o4)                        [7, 1]

Función: vertices (gr) ¶

Devuelve la lista de vértices del grafo gr.

Example

(%i1) load ("graphs")$
(%i2) vertices(complete_graph(4));
(%o2)                           [3, 2, 1, 0]

Función: vertex_coloring (gr) ¶

Devuelve un coloreado óptimo de los vértices del grafo gr.

La función devuelve el número cromático y una lista representando el coloreado de los vértices de gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p:petersen_graph()$
(%i3) vertex_coloring(p);
(%o3) [3, [[0, 2], [1, 3], [2, 2], [3, 3], [4, 1], [5, 3], 
                                 [6, 1], [7, 1], [8, 2], [9, 2]]]

Función: wiener_index (gr) ¶

Devuelve el índice de Wiener del grafo gr.

Ejemplo:

(%i1) wiener_index(dodecahedron_graph());
(%o1)                          500

55.2.3 Modificación de grafos

Función: add_edge (e, gr) ¶

Añade la arista e al grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p : path_graph(4)$
(%i3) neighbors(0, p);
(%o3)                                [1]
(%i4) add_edge([0,3], p);
(%o4)                               done
(%i5) neighbors(0, p);
(%o5)                              [3, 1]

Función: add_edges (e_list, gr) ¶

Añade las aristas de la lista e_list al grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : empty_graph(3)$
(%i3) add_edges([[0,1],[1,2]], g)$
(%i4) print_graph(g)$
Graph on 3 vertices with 2 edges.
Adjacencies:
  2 :  1
  1 :  2  0
  0 :  1

Función: add_vertex (v, gr) ¶

Añade el vértice v al grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : path_graph(2)$
(%i3) add_vertex(2, g)$
(%i4) print_graph(g)$
Graph on 3 vertices with 1 edges.
Adjacencies:
  2 :
  1 :  0
  0 :  1

Función: add_vertices (v_list, gr) ¶

Añade los vértices de la lista v_list al grafo gr.

Función: connect_vertices (v_list, u_list, gr) ¶

Conecta todos los vértices de la lista v_list con los vértices de la lista u_list del grafo gr.

v_list y u_list pueden ser vértices aislados o una lista de vértices.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g : empty_graph(4)$
(%i3) connect_vertices(0, [1,2,3], g)$
(%i4) print_graph(g)$
Graph on 4 vertices with 3 edges.
Adjacencies:
  3 :  0
  2 :  0
  1 :  0
  0 :  3  2  1

Función: contract_edge (e, gr) ¶

Contrae la arista e del gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) g: create_graph(
       8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
(%i3) print_graph(g)$
Graph on 8 vertices with 7 edges.
Adjacencies:
  7 :  4
  6 :  4
  5 :  4
  4 :  7  6  5  3
  3 :  4  2  1  0
  2 :  3
  1 :  3
  0 :  3
(%i4) contract_edge([3,4], g)$
(%i5) print_graph(g)$
Graph on 7 vertices with 6 edges.
Adjacencies:
  7 :  3
  6 :  3
  5 :  3
  3 :  5  6  7  2  1  0
  2 :  3
  1 :  3
  0 :  3

Función: remove_edge (e, gr) ¶

Elimina la arista e del grafo gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) c3 : cycle_graph(3)$
(%i3) remove_edge([0,1], c3)$
(%i4) print_graph(c3)$
Graph on 3 vertices with 2 edges.
Adjacencies:
  2 :  0  1
  1 :  2
  0 :  2

Función: remove_vertex (v, gr) ¶

Elimina el vértice v del grafo gr.

Función: vertex_coloring (gr) ¶

Devuelve un coloreado óptimo de los vértice del grafo gr.

La función devuelve el número cromático y una lista representando el coloreado de los vértices de gr.

Ejemplo:

(%i1) load ("graphs")$
(%i2) p:petersen_graph()$
(%i3) vertex_coloring(p);
(%o3) [3, [[0, 2], [1, 3], [2, 2], [3, 3], [4, 1], [5, 3], 
                                [6, 1], [7, 1], [8, 2], [9, 2]]]

55.2.4 Lectura y escritura de ficheros

Función: dimacs_export (gr, fl) ¶

Función: dimacs_export (gr, fl, comment1, ..., commentn) ¶

Exporta el grafo al fichero fl en formato DIMACS. Los comentarios adicionales se anãdirán al comienzo del fichero.

Función: dimacs_import (fl) ¶

Lee el grafo almacenado en el fichero fl en formato DIMACS.

Función: graph6_decode (str) ¶

Devuelve el grafo codificado en formato graph6 en la cadena str.

Función: graph6_encode (gr) ¶

Devuelve una cadena codificando el grafo gr en formato graph6.

Función: graph6_export (gr_list, fl) ¶

Exporta los grafos de la lista gr_list al fichero fl en formato graph6.

Función: graph6_import (fl) ¶

Lee la lista de grafos almacenados en el fichero fl en formato graph6.

Función: sparse6_decode (str) ¶

Devuelve el grafo codificado en formato sparse6 en la cadena str.

Función: sparse6_encode (gr) ¶

Devuelve una cadena codificando el grafo gr en formato sparse6.

Función: sparse6_export (gr_list, fl) ¶

Exporta los grafos de la lista gr_list al fichero fl en formato sparse6.

Función: sparse6_import (fl) ¶

Lee la lista de grafos almacenados en el fichero fl en formato sparse6.

55.2.5 Visualización

Función: draw_graph (graph) ¶

Función: draw_graph (graph, option1, ..., optionk) ¶

Dibuja el grafo utilizando el paquete draw.

El algoritmo utilizado para posicionar los vértices se especifica con el argumento opcional program, cuyo valor por defecto es program=spring_embedding. draw_graph también puede utilizar los programas de graphviz para posicionar los vértices, para lo cual deberá instalarse separadamente el programa graphviz.

Ejemplo 1:

(%i1) load ("graphs")$
(%i2) g:grid_graph(10,10)$
(%i3) m:max_matching(g)$
(%i4) draw_graph(g,
   spring_embedding_depth=100,
   show_edges=m, edge_type=dots,
   vertex_size=0)$

Ejemplo 2:

(%i1) load ("graphs")$
(%i2) g:create_graph(16,
    [
     [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
     [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
     [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
     [10,14],[15,14],[13,14]
    ])$
(%i3) t:minimum_spanning_tree(g)$
(%i4) draw_graph(
    g,
    show_edges=edges(t),
    show_edge_width=4,
    show_edge_color=green,
    vertex_type=filled_square,
    vertex_size=2
    )$

Ejemplo 3:

(%i1) load ("graphs")$
(%i2) mi : max_independent_set(g)$
(%i3) draw_graph(
    g,
    show_vertices=mi,
    show_vertex_type=filled_up_triangle,
    show_vertex_size=2,
    edge_color=cyan,
    edge_width=3,
    =true,
    text_color=brown
    )$

Ejemplo 4:

(%i1) load ("graphs")$
(%i2) net : create_graph(
    [0,1,2,3,4,5],
    [
     [[0,1], 3], [[0,2], 2],
     [[1,3], 1], [[1,4], 3],
     [[2,3], 2], [[2,4], 2],
     [[4,5], 2], [[3,5], 2]
    ],
    directed=true
    )$
(%i3) draw_graph(
    net,
    show_weight=true,
    vertex_size=0,
    show_vertices=[0,5],
    show_vertex_type=filled_square,
    head_length=0.2,
    head_angle=10,
    edge_color="dark-green",
    text_color=blue
    )$

Ejemplo 5:

(%i1) load("graphs")$
(%i2) g: petersen_graph(20, 2);
(%o2)                         GRAPH
(%i3) draw_graph(g, redraw=true, program=planar_embedding);
(%o3)                         done

Ejemplo 6:

(%i1) load("graphs")$
(%i2) t: tutte_graph();
(%o2)                         GRAPH
(%i3) draw_graph(t, redraw=true, 
                    fixed_vertices=[1,2,3,4,5,6,7,8,9]);
(%o3)                         done

Variable opcional: draw_graph_program ¶

Valor por defecto: spring_embedding

Programa a utilizar por defecto para posicionar los vértices en la función draw_graph.

Opción de draw_graph: show_id ¶

Valor por defecto: false

Si show_id vale true entonces se muestran los números identificadores de los vértices.

Opción de draw_graph: show_label ¶

Valor por defecto: false

Si show_label vale true entonces se muestran las etiquetas de los vértices.

Opción de draw_graph: label_alignment ¶

Valor por defecto: center

Indica cómo se deben alinear las etiquetas o números identificadores de los vértices. Puede ser: left, center or right.

Opción de draw_graph: show_weight ¶

Valor por defecto: false

si show_weight vale true entonces se mostrarán los pesos de las aristas.

Opción de draw_graph: vertex_type ¶

Valor por defecto: circle

Establece cómo se mostrarán los vértices. Véase la opción point_type del paquete draw.

Opción de draw_graph: vertex_size ¶

Tamanõ de los vértices.

Opción de draw_graph: vertex_color ¶

Color a utilizar en los vértices.

Opción de draw_graph: show_vertices ¶

Valor por defecto: []

Dibuja los vértices seleccionados en la lista con colores diferentes.

Opción de draw_graph: show_vertex_type ¶

Establece cómo se mostrarán los vértices de show_vertices. Véase la opción point_type del paquete draw.

Opción de draw_graph: show_vertex_size ¶

Tamanõs de los vértices de show_vertices.

Opción de draw_graph: show_vertex_color ¶

Color a utilizar en los vértices de la lista show_vertices.

Opción de draw_graph: vertex_partition ¶

Valor por defecto: []

Una partición [[v1,v2,...],...,[vk,...,vn]] de los vértices del grafo. Los vértices de cada lista se dibujarán de diferente color.

Opción de draw_graph: vertex_coloring ¶

Colores de los vértices. Los colores col deben especificarse en el mismo formato que el devuelto por vertex_coloring.

Opción de draw_graph: edge_color ¶

Color a utilizar en las aristas.

Opción de draw_graph: edge_width ¶

Ancho de las aristas.

Opción de draw_graph: edge_type ¶

Establece cómo se dibujarán las aristas. Véase la opción line_type del paquete draw.

Opción de draw_graph: show_edges ¶

Dibuja las aristas de la lista e_list con colores diferentes.

Opción de draw_graph: show_edge_color ¶

Color a utilizar en las aristas de la lista show_edges.

Opción de draw_graph: show_edge_width ¶

Anchos de las aristas de show_edges.

Opción de draw_graph: show_edge_type ¶

Establece cómo se dibujarán las aristas de show_edges. Véase la opción line_type del paquete draw.

Opción de draw_graph: edge_partition ¶

Una partición [[e1,e2,...],...,[ek,...,em]] de las aristas del grafo. Las aristas de cada lista se dibujarán de diferente color.

Opción de draw_graph: edge_coloring ¶

Colores de las aristas. Los colores col deben especificarse en el mismo formato que el devuelto por edge_coloring.

Opción de draw_graph: redraw ¶

Valor por defecto: false

Si redraw vale true, las posiciones de los vértices se recalculan incluso si las posiciones están almacenadas de un dibujo previo del grafo.

Opción de draw_graph: head_angle ¶

Valor por defecto: 15

Ángulo de las flechas de los arcos en los grafos orientados.

Opción de draw_graph: head_length ¶

Valor por defecto: 0.1

Longitud de las flechas de los arcos en los grafos orientados.

Opción de draw_graph: spring_embedding_depth ¶

Valor por defecto: 50

Número de iteraciones del algoritmo de dibujo de grafos.

Opción de draw_graph: terminal ¶

Terminal utilizado para ver el gráfo. Véase la opción terminal del paquete draw.

Opción de draw_graph: file_name ¶

Nombre del fichero cuando el terminal especificado no es la pantalla.

Opción de draw_graph: program ¶

establece el programa para posicionado de vértices del grafo. Puede ser cualquiera de los programas graphviz (dot, neato, twopi, circ, fdp), circular o spring_embedding o planar_embedding; planar_embedding sĺo está disponible para grafos planares 2-conectados. Si program=spring_embedding, se puede especificar un conjunto de vértices de posición fija con la opción fixed_vertices.

Opción de draw_graph: fixed_vertices ¶

Especifica una lista de vértices con posiciones fijas en un polígono regular. Se puede utilizar cuando program=spring_embedding.

Función: vertices_to_path (v_list) ¶

Convierte una lista v_list de vértices en la lista de aristas del camino definido por la propia v_list.

Función: vertices_to_cycle (v_list) ¶

Convierte una lista v_list de vértices en la lista de aristas del ciclo definido por la propia v_list.