[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

55. graphs


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

55.1 Introducción a graphs

El paquete graphs permite trabajar con estructuras de grafos y digrafos en Maxima. Tanto los grafos como los digrafos son de estructura simples (no tienen ni aristas múltiples ni bucles), pero los digrafos pueden tener una arista dirigida desde u hasta v y otra desde v hasta u.

Los grafos se representan internamente como listas de adyacencia y se implementan como estructuras de lisp. Los vértices se identifican por sus números de identificacin' (siempre enteros). Las aristas/arcos se representan por listas de longitud 2. Se pueden asignar etiquetas a los vértices de los grafos/digrafos y pesos a sus aristas/arcos.

La función draw_graph dibuja grafos siguiendo un criterio rígido de posicionamiento de los vértices. También puede hacer uso del programa graphviz disponible en http://www.graphviz.org. La función draw_graph utiliza el paquete draw de Maxima.

Para hacer uso de este paquete, ejecútese primero load(graphs).


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

55.2 Funciones y variables para graphs


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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)$

../figures/graphs01

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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]]

../figures/graphs13

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)$

../figures/graphs02

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))$

../figures/graphs03

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))$

../figures/graphs04

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)$

../figures/graphs05

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)$

../figures/graphs06

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))$

../figures/graphs07

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))$

../figures/graphs08

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

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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]]]

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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)$

../figures/graphs09

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
    )$

../figures/graphs10

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
    )$

../figures/graphs11

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
    )$

../figures/graphs12

Ejemplo 5:

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

../figures/graphs14

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

../figures/graphs15

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 sl'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.


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Jaime Villate on octubre, 13 2014 using texi2html 1.76.