1
@c english version 1.14
3
* Introducci@'on a graphs::
4
* Funciones y variables para graphs::
7
@node Introducci@'on a graphs, Funciones y variables para graphs, graphs, graphs
8
@section Introducci@'on a graphs
10
El paquete @code{graphs} permite trabajar con estructuras de grafos y digrafos en
11
Maxima. Tanto los grafos como los digrafos son de estructura simples (no
12
tienen ni aristas múltiples ni bucles), pero los digrafos pueden tener
13
una arista dirigida desde @var{u} hasta @var{v} y otra desde @var{v}
16
Los grafos se representan internamente como listas de adyacencia y se
17
implementan como estructuras de lisp. Los v@'ertices se identifican
18
por sus n@'umeros de identificaci@'n (siempre enteros). Las aristas/arcos
19
se representan por listas de longitud 2. Se pueden asignar etiquetas a los
20
v@'ertices de los grafos/digrafos y pesos a sus aristas/arcos.
22
La funci@'on @code{draw_graph} dibuja grafos siguiendo un criterio r@'{@dotless{i}}gido
23
de posicionamiento de los v@'ertices. Tambi@'en puede hacer uso del programa graphviz
24
disponible en @url{http://www.graphviz.org}. La funci@'n @code{draw_graph} utiliza el paquete
25
@code{draw} de Maxima.
27
Para hacer uso de este paquete, ejec@'utese primero @code{load(graphs)}.
30
@node Funciones y variables para graphs, , Introducci@'on a graphs, graphs
31
@section Funciones y variables para graphs
33
@subsection Construyendo grafos
35
@deffn {Funci@'on} create_graph (@var{v_list}, @var{e_list})
36
@deffnx {Funci@'on} create_graph (@var{n}, @var{e_list})
37
@deffnx {Funci@'on} create_graph (@var{v_list}, @var{e_list}, @var{directed})
39
Crea un nuevo grafo sobre el conjunto de v@'ertices @var{v_list} con aristas
42
@var{v_list} es una lista de v@'ertices (@code{[v1, v2,..., vn]}) o una lista de
43
v@'ertices junto con sus respectivas etiquetas (@code{[[v1,l1], [v2,l2],..., [vn,ln]]}).
45
@var{n} es el n@'umero de v@'ertices, los cuales se identificar@'an desde
48
@var{e_list} es una lista de aristas (@code{[e1, e2,..., em]}) o una lista de
49
aristas con sus respectivas ponderaciones (@code{[[e1, w1], ..., [em, wm]]}).
51
Si @var{directed} is not @code{false}, se devolver@'a un grafo orientado.
55
Crea un ciclo de 3 v@'ertices.
59
@c g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
64
(%i2) g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
66
Graph on 3 vertices with 3 edges.
73
Crea un ciclo de 3 v@'ertices y aristas ponderadas:
77
@c g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
83
(%i2) g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
86
Graph on 3 vertices with 3 edges.
93
Crea un grafo orientado:
103
@c 'directed = true)$
108
(%i2) d : create_graph(
115
(%i3) print_graph(d)$
116
Digraph on 4 vertices with 4 arcs.
127
@deffn {Funci@'on} copy_graph (@var{g})
128
Devuelve una copia del grafo @var{g}.
131
@deffn {Funci@'on} circulant_graph (@var{n}, @var{d})
132
Devuelve un grafo cirlulante de par@'ametros @var{n} y @var{d}.
138
@c g : circulant_graph(10, [1,3])$
143
(%i2) g : circulant_graph(10, [1,3])$
144
(%i3) print_graph(g)$
145
Graph on 10 vertices with 20 edges.
160
@deffn {Funci@'on} clebsch_graph ()
161
Devuelve el grafo de Clebsch.
164
@deffn {Funci@'on} complement_graph (@var{g})
165
Devuelve el complemento del grafo @var{g}.
168
@deffn {Funci@'on} complete_bipartite_graph (@var{n}, @var{m})
169
Devuelve el grafo bipartido completo de @var{n+m} v@'ertices.
172
@deffn {Funci@'on} complete_graph (@var{n})
173
Devuelve el grafo completo de @var{n} v@'ertices.
176
@deffn {Funci@'on} cycle_digraph (@var{n})
177
Devuelve el ciclo dirigido de @var{n} v@'ertices.
180
@deffn {Funci@'on} cycle_graph (@var{n})
181
Devuelve el ciclo de @var{n} v@'ertices.
184
@deffn {Funci@'on} cube_graph (@var{n})
185
Devuelve el cubo de @var{n} dimensiones.
188
@deffn {Funci@'on} dodecahedron_graph ()
189
Devuelve el grafo del dodecaedro.
192
@deffn {Funci@'on} empty_graph (@var{n})
193
Devuelve el grafo vac@'{@dotless{i}}o de @var{n} v@'ertices.
196
@deffn {Funci@'on} flower_snark (@var{n})
197
Devuelve el grafo de flor de @var{4n} v@'ertices.
203
@c f5 : flower_snark(5)$
204
@c chromatic_index(f5);
208
(%i2) f5 : flower_snark(5)$
209
(%i3) chromatic_index(f5);
214
@deffn {Funci@'on} from_adjacency_matrix (@var{A})
215
Devuelve el grafo definido por la matriz de adyacencia @var{A}.
218
@deffn {Funci@'on} frucht_graph ()
219
Devuelve el grafo de Frucht.
222
@deffn {Funci@'on} graph_product (@var{g1}, @var{g1})
223
Devuelve el producto dirigido de los grafos @var{g1} y @var{g2}.
229
@c grid : graph_product(path_graph(3), path_graph(4))$
234
(%i2) grid : graph_product(path_graph(3), path_graph(4))$
235
(%i3) draw_graph(grid)$
240
@image{../figures/graphs01,6cm}
243
@deffn {Funci@'on} graph_union (@var{g1}, @var{g1})
244
Devuelve la uni@'on (suma) de los grafos @var{g1} y @var{g2}.
247
@deffn {Funci@'on} grid_graph (@var{n}, @var{m})
248
Devuelve la rejilla @var{n x m}.
251
@deffn {Funci@'on} grotzch_graph ()
252
Devuelve el grafo de Grotzch.
255
@deffn {Funci@'on} heawood_graph ()
256
Devuelve el grafo de Heawood.
259
@deffn {Funci@'on} icosahedron_graph ()
260
Devuelve el grafo del icosaedro.
263
@deffn {Funci@'on} induced_subgraph (@var{V}, @var{g})
264
Devuelve el grafo inducido por el subconjunto @var{V} de v@'ertices del grafo @var{g}.
270
@c p : petersen_graph()$
272
@c g : induced_subgraph(V, p)$
277
(%i2) p : petersen_graph()$
278
(%i3) V : [0,1,2,3,4]$
279
(%i4) g : induced_subgraph(V, p)$
280
(%i5) print_graph(g)$
281
Graph on 5 vertices with 5 edges.
291
@deffn {Funci@'on} line_graph (@var{g})
292
Devuelve el grafo de l@'{@dotless{i}}nea del grafo @var{g}.
296
@deffn {Funci@'on} make_graph (@var{vrt}, @var{f})
297
@deffnx {Funci@'on} make_graph (@var{vrt}, @var{f}, @var{oriented})
298
Crea un grafo por medio de la funci@'on de predicado @var{f}.
300
@var{vrt} es una lista o conjunto de v@'ertices o un simplemente un n@'umero entero.
301
Si @var{vrt} es un n@'umero entero, entonces los v@'ertices del grafo ser@'an los
302
enteros desde 1 hasta @var{vrt}.
304
@var{f} es una funci@'on de predicado. Dos v@'ertices @var{a} y @var{b} se conectar@'an
305
si @code{f(a,b)=true}.
307
Si @var{directed} no es @var{false}, entonces en grafo ser@'a dirigido.
312
@c g : make_graph(powerset({1,2,3,4,5}, 2), disjointp)$
313
@c is_isomorphic(g, petersen_graph());
314
@c get_vertex_label(1, g);
318
(%i2) g : make_graph(powerset(@{1,2,3,4,5@}, 2), disjointp)$
319
(%i3) is_isomorphic(g, petersen_graph());
321
(%i4) get_vertex_label(1, g);
328
@c f(i, j) := is (mod(j, i)=0)$
329
@c g : make_graph(20, f, directed=true)$
330
@c out_neighbors(4, g);
331
@c in_neighbors(18, g);
335
(%i2) f(i, j) := is (mod(j, i)=0)$
336
(%i3) g : make_graph(20, f, directed=true)$
337
(%i4) out_neighbors(4, g);
338
(%o4) [8, 12, 16, 20]
339
(%i5) in_neighbors(18, g);
340
(%o5) [1, 2, 3, 6, 9]
345
@deffn {Funci@'on} mycielski_graph (@var{g})
346
Devuelve el grafo de Mycielski del grafo @var{g}.
349
@deffn {Funci@'on} new_graph ()
350
Devuelve el grafo sin v@'ertices ni aristas.
353
@deffn {Funci@'on} path_digraph (@var{n})
354
Devuelve el camino dirigido de @var{n} v@'ertices.
357
@deffn {Funci@'on} path_graph (@var{n})
358
Devuelve el camino de @var{n} v@'ertices.
361
@deffn {Funci@'on} petersen_graph ()
362
@deffnx {Funci@'on} petersen_graph (@var{n}, @var{d})
363
Devuelve el grafo de Petersen @var{P_@{n,d@}}. Los valores por
364
defecto para @var{n} y @var{d} son @code{n=5} y @code{d=2}.
367
@deffn {Funci@'on} random_bipartite_graph (@var{a}, @var{b}, @var{p})
368
Devuelve un grafo aleatorio bipartido a partir de los v@'ertices @code{a+b}. Cada
369
arista se genera con probabilidad @var{p}.
372
@deffn {Funci@'on} random_digraph (@var{n}, @var{p})
373
Devuelve un grafo aleatorio dirigido de @var{n} v@'ertices. Cada arco se presenta
374
con una probabilidad @var{p}.
377
@deffn {Funci@'on} random_regular_graph (@var{n})
378
@deffnx {Funci@'on} random_regular_graph (@var{n}, @var{d})
379
Devuelve un grafo aleatorio @var{d}-regular de @var{n} v@'ertices. El valor
380
por defecto para @var{d} es @code{d=3}.
383
@deffn {Funci@'on} random_graph (@var{n}, @var{p})
384
Devuelve un grafo aleatorio de @var{n} v@'ertices. Cada arco se presenta
385
con una probabilidad @var{p}.
388
@deffn {Funci@'on} random_graph1 (@var{n}, @var{m})
389
Devuelve un grafo aleatorio de @var{n} v@'ertices y @var{m} arcos aleatorios.
392
@deffn {Funci@'on} random_network (@var{n}, @var{p}, @var{w})
393
Devuelve una red aleatoria de @var{n} v@'ertices. Cada arco se presenta
394
con probabilidad @var{p} y tiene un peso dentro del rango @code{[0,w]}.
395
La funci@'on devuelve una lista @code{[network, source, sink]}.
401
@c [net, s, t] : random_network(50, 0.2, 10.0);
402
@c max_flow(net, s, t)$
407
(%i2) [net, s, t] : random_network(50, 0.2, 10.0);
408
(%o2) [DIGRAPH, 50, 51]
409
(%i3) max_flow(net, s, t)$
411
(%o4) 27.65981397932507
415
@deffn {Funci@'on} random_tournament (@var{n})
416
Devuelve un torneo aleatorio de @var{n} v@'ertices.
419
@deffn {Funci@'on} random_tree (@var{n})
420
Devuelve un @'arbol aleatorio de @var{n} v@'ertices.
423
@deffn {Funci@'on} tutte_graph ()
424
Devuelve el grafo de Tutte.
427
@deffn {Funci@'on} underlying_graph (@var{g})
428
Devuelve el grafo asociado al grafo orientado @var{g}.
431
@deffn {Funci@'on} wheel_graph (@var{n})
432
Devuelve el grafo de rueda de @var{n+1} v@'ertices.
435
@subsection Propiedades de los grafos
437
@deffn {Funci@'on} adjacency_matrix (@var{gr})
438
Devuelve la matriz de adyacencia del grafo @var{gr}.
444
@c c5 : cycle_graph(4)$
445
@c adjacency_matrix(c5);
449
(%i2) c5 : cycle_graph(4)$
450
(%i3) adjacency_matrix(c5);
461
@deffn {Funci@'on} average_degree (@var{gr})
462
Devuelve el grado medio de los v@'ertices del garfo @var{gr}.
468
@c average_degree(grotzch_graph());
472
(%i2) average_degree(grotzch_graph());
479
@deffn {Funci@'on} biconected_components (@var{gr})
480
Devuelve los subconjuntos de v@'ertices biconectados del grafo @var{gr}.
489
@c [1,2],[2,3],[2,4],[3,4],
490
@c [4,5],[5,6],[4,6],[6,7]
492
@c biconnected_components(g);
496
(%i2) g : create_graph(
499
[1,2],[2,3],[2,4],[3,4],
500
[4,5],[5,6],[4,6],[6,7]
502
(%i3) biconnected_components(g);
503
(%o3) [[6, 7], [4, 5, 6], [1, 2], [2, 3, 4]]
507
@image{../figures/graphs13,6cm}
511
@deffn {Funci@'on} bipartition (@var{gr})
512
Devuelve una bipartici@'on de los v@'ertices del grafo @var{gr}, o una
513
lista vac@'{@dotless{i}}a si @var{gr} no es bipartido.
519
@c h : heawood_graph()$
520
@c [A,B]:bipartition(h);
521
@c draw_graph(h, show_vertices=A, program=circular)$
525
(%i2) h : heawood_graph()$
526
(%i3) [A,B]:bipartition(h);
527
(%o3) [[8, 12, 6, 10, 0, 2, 4], [13, 5, 11, 7, 9, 1, 3]]
528
(%i4) draw_graph(h, show_vertices=A, program=circular)$
533
@image{../figures/graphs02,6cm}
536
@deffn {Funci@'on} chromatic_index (@var{gr})
537
Devuelve el @'{@dotless{i}}ndice crom@'atico del grafo @var{gr}.
543
@c p : petersen_graph()$
544
@c chromatic_index(p);
548
(%i2) p : petersen_graph()$
549
(%i3) chromatic_index(p);
554
@deffn {Funci@'on} chromatic_number (@var{gr})
555
Devuelve el n@'umero crom@'atico del grafo @var{gr}.
561
@c chromatic_number(cycle_graph(5));
562
@c chromatic_number(cycle_graph(6));
566
(%i2) chromatic_number(cycle_graph(5));
568
(%i3) chromatic_number(cycle_graph(6));
573
@deffn {Funci@'on} clear_edge_weight (@var{e}, @var{gr})
574
Elimina el peso del arco @var{e} del grafo @var{gr}.
580
@c g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
581
@c get_edge_weight([0,1], g);
582
@c clear_edge_weight([0,1], g)$
583
@c get_edge_weight([0,1], g);
587
(%i2) g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
588
(%i3) get_edge_weight([0,1], g);
590
(%i4) clear_edge_weight([0,1], g)$
591
(%i5) get_edge_weight([0,1], g);
596
@deffn {Funci@'on} clear_vertex_label (@var{v}, @var{gr})
597
Elimina la etiqueta del v@'ertice @var{v} del grafo @var{gr}.
603
@c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
604
@c get_vertex_label(0, g);
605
@c clear_vertex_label(0, g);
606
@c get_vertex_label(0, g);
610
(%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
611
(%i3) get_vertex_label(0, g);
613
(%i4) clear_vertex_label(0, g);
615
(%i5) get_vertex_label(0, g);
620
@deffn {Funci@'on} connected_components (@var{gr})
621
Devuelve las componentes conexas del grafo @var{gr}.
627
@c g: graph_union(cycle_graph(5), path_graph(4))$
628
@c connected_components(g);
632
(%i2) g: graph_union(cycle_graph(5), path_graph(4))$
633
(%i3) connected_components(g);
634
(%o3) [[1, 2, 3, 4, 0], [8, 7, 6, 5]]
638
@deffn {Funci@'on} diameter (@var{gr})
639
Devuelve el di@'ametro del grafo @var{gr}.
645
@c diameter(dodecahedron_graph());
649
(%i2) diameter(dodecahedron_graph());
654
@deffn {Funci@'on} edge_coloring (@var{gr})
655
Devuelve una coloraci@'on @'optima de los arcos del grafo @var{gr}.
657
La funci@'on devuelve el @'{@dotless{i}}ndice crom@'atico y una lista
658
que representa el coloreado de los arcos de @var{gr}.
664
@c p : petersen_graph()$
665
@c [ch_index, col] : edge_coloring(p);
666
@c assoc([0,1], col);
667
@c assoc([0,5], col);
671
(%i2) p : petersen_graph()$
672
(%i3) [ch_index, col] : edge_coloring(p);
673
(%o3) [4, [[[0, 5], 3], [[5, 7], 1], [[0, 1], 1], [[1, 6], 2],
674
[[6, 8], 1], [[1, 2], 3], [[2, 7], 4], [[7, 9], 2], [[2, 3], 2],
675
[[3, 8], 3], [[5, 8], 2], [[3, 4], 1], [[4, 9], 4], [[6, 9], 3],
677
(%i4) assoc([0,1], col);
679
(%i5) assoc([0,5], col);
684
@deffn {Funci@'on} degree_sequence (@var{gr})
685
Devuelve una lista con los grados de los v@'ertices del grafo @var{gr}.
691
@c degree_sequence(random_graph(10, 0.4));
695
(%i2) degree_sequence(random_graph(10, 0.4));
696
(%o2) [2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
700
@deffn {Funci@'on} edge_connectivity (@var{gr})
701
Devuelve la conectividad de las aristas del grafo @var{gr}.
703
V@'ease tambi@'en @code{min_edge_cut}.
706
@deffn {Funci@'on} edges (@var{gr})
707
Devuelve la lista de las aristas (arcos) del grafo (dirigido) @var{gr}.
713
@c edges(complete_graph(4));
717
(%i2) edges(complete_graph(4));
718
(%o2) [[2, 3], [1, 3], [1, 2], [0, 3], [0, 2], [0, 1]]
722
@deffn {Funci@'on} get_edge_weight (@var{e}, @var{gr})
723
@deffnx {Funci@'on} get_edge_weight (@var{e}, @var{gr}, @var{ifnot})
724
Devuelve el peso de la arista @var{e} del grafo @var{gr}.
726
Si la arista no tiene peso, la funci@'on devuelve 1. Si la arista no
727
pertenece al grafo, la funci@'on emite un mensaje de error o devuelve
728
el argumento opcional @var{ifnot}.
734
@c c5 : cycle_graph(5)$
735
@c get_edge_weight([1,2], c5);
736
@c set_edge_weight([1,2], 2.0, c5);
737
@c get_edge_weight([1,2], c5);
741
(%i2) c5 : cycle_graph(5)$
742
(%i3) get_edge_weight([1,2], c5);
744
(%i4) set_edge_weight([1,2], 2.0, c5);
746
(%i5) get_edge_weight([1,2], c5);
751
@deffn {Funci@'on} get_vertex_label (@var{v}, @var{gr})
752
Devuelve la etiqueta del v@'ertice @var{v} del grafo @var{gr}.
758
@c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
759
@c get_vertex_label(0, g);
763
(%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
764
(%i3) get_vertex_label(0, g);
769
@deffn {Funci@'on} graph_charpoly (@var{gr}, @var{x})
770
Devuelve el polinomio caracter@'{@dotless{i}}stico (de variable @var{x})
777
@c p : petersen_graph()$
778
@c graph_charpoly(p, x), factor;
782
(%i2) p : petersen_graph()$
783
(%i3) graph_charpoly(p, x), factor;
785
(%o3) (x - 3) (x - 1) (x + 2)
789
@deffn {Funci@'on} graph_center (@var{gr})
790
Devuelve el centro del grafo @var{gr}.
796
@c g : grid_graph(5,5)$
801
(%i2) g : grid_graph(5,5)$
802
(%i3) graph_center(g);
807
@deffn {Funci@'on} graph_eigenvalues (@var{gr})
808
Devuelve los valores propios del grafo @var{gr}. La funci@'on
809
devuelve los valores propios en el mismo formato en el que lo
810
hace la funci@'on @code{eigenvalue}.
816
@c p : petersen_graph()$
817
@c graph_eigenvalues(p);
821
(%i2) p : petersen_graph()$
822
(%i3) graph_eigenvalues(p);
823
(%o3) [[3, - 2, 1], [1, 4, 5]]
827
@deffn {Funci@'on} graph_periphery (@var{gr})
828
Devuelve la periferia del grafo @var{gr}.
834
@c g : grid_graph(5,5)$
835
@c graph_periphery(g);
839
(%i2) g : grid_graph(5,5)$
840
(%i3) graph_periphery(g);
845
@deffn {Funci@'on} graph_size (@var{gr})
846
Devuelve el n@'umero de aristas del grafo @var{gr}.
852
@c p : petersen_graph()$
857
(%i2) p : petersen_graph()$
863
@deffn {Funci@'on} graph_order (@var{gr})
864
Devuelve el n@'umero de v@'ertices del grafo @var{gr}.
870
@c p : petersen_graph()$
875
(%i2) p : petersen_graph()$
876
(%i3) graph_order(p);
881
@deffn {Funci@'on} girth (@var{gr})
882
Devuelve la longitud del ciclo m@'as corto del grafo @var{gr}.
888
@c g : heawood_graph()$
893
(%i2) g : heawood_graph()$
899
@deffn {Funci@'on} hamilton_cycle (@var{gr})
900
Devuelve el ciclo de Hamilton del grafo @var{gr} o una lista vac@'{@dotless{i}}a
901
si @var{gr} no es hamiltoniano.
907
@c c : cube_graph(3)$
908
@c hc : hamilton_cycle(c);
909
@c draw_graph(c, show_edges=vertices_to_cycle(hc))$
913
(%i2) c : cube_graph(3)$
914
(%i3) hc : hamilton_cycle(c);
915
(%o3) [7, 3, 2, 6, 4, 0, 1, 5, 7]
916
(%i4) draw_graph(c, show_edges=vertices_to_cycle(hc))$
921
@image{../figures/graphs03,6cm}
924
@deffn {Funci@'on} hamilton_path (@var{gr})
925
Devuelve el camino de Hamilton del grafo @var{gr} o una lista vac@'{@dotless{i}}a
926
si @var{gr} no los tiene.
932
@c p : petersen_graph()$
933
@c hp : hamilton_path(p);
934
@c draw_graph(p, show_edges=vertices_to_path(hp))$
938
(%i2) p : petersen_graph()$
939
(%i3) hp : hamilton_path(p);
940
(%o3) [0, 5, 7, 2, 1, 6, 8, 3, 4, 9]
941
(%i4) draw_graph(p, show_edges=vertices_to_path(hp))$
946
@image{../figures/graphs04,6cm}
949
@deffn {Funci@'on} isomorphism (@var{gr1}, @var{gr2})
950
Devuelve un isomorfismo entre los grafos/digrafos @var{gr1} y @var{gr2}.
951
Si @var{gr1} y @var{gr2} no son isomorfos, devuelve una lista vac@'{@dotless{i}}a.
957
@c clk5:complement_graph(line_graph(complete_graph(5)))$
958
@c isomorphism(clk5, petersen_graph());
962
(%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
963
(%i3) isomorphism(clk5, petersen_graph());
964
(%o3) [9 -> 0, 2 -> 1, 6 -> 2, 5 -> 3, 0 -> 4, 1 -> 5, 3 -> 6,
965
4 -> 7, 7 -> 8, 8 -> 9]
969
@deffn {Funci@'on} in_neighbors (@var{v}, @var{gr})
970
Devuelve la lista de los nodos hijos del v@'ertice @var{v}
971
del grafo orientado @var{gr}.
977
@c p : path_digraph(3)$
978
@c in_neighbors(2, p);
979
@c out_neighbors(2, p);
983
(%i2) p : path_digraph(3)$
984
(%i3) in_neighbors(2, p);
986
(%i4) out_neighbors(2, p);
991
@deffn {Funci@'on} is_biconnected (@var{gr})
992
Devuelve @code{true} si @var{gr} est@'a biconectado y @code{false}
1000
@c is_biconnected(cycle_graph(5));
1001
@c is_biconnected(path_graph(5));
1004
(%i1) load (graphs)$
1005
(%i2) is_biconnected(cycle_graph(5));
1007
(%i3) is_biconnected(path_graph(5));
1012
@deffn {Funci@'on} is_bipartite (@var{gr})
1013
Devuelve @code{true} si @var{gr} es bipartido (2-coloreable) y @code{false}
1020
@c is_bipartite(petersen_graph());
1021
@c is_bipartite(heawood_graph());
1024
(%i1) load (graphs)$
1025
(%i2) is_bipartite(petersen_graph());
1027
(%i3) is_bipartite(heawood_graph());
1032
@deffn {Funci@'on} is_connected (@var{gr})
1033
Devuelve @code{true} si el grafo @var{gr} es conexo y @code{false}
1040
@c is_connected(graph_union(cycle_graph(4), path_graph(3)));
1043
(%i1) load (graphs)$
1044
(%i2) is_connected(graph_union(cycle_graph(4), path_graph(3)));
1049
@deffn {Funci@'on} is_digraph (@var{gr})
1050
Devuelve @code{true} si @var{gr} es un grafo orientado (digrafo) y
1051
@code{false} en caso contrario.
1057
@c is_digraph(path_graph(5));
1058
@c is_digraph(path_digraph(5));
1061
(%i1) load (graphs)$
1062
(%i2) is_digraph(path_graph(5));
1064
(%i3) is_digraph(path_digraph(5));
1069
@deffn {Funci@'on} is_edge_in_graph (@var{e}, @var{gr})
1070
Devuelve @code{true} si @var{e} es una arista (arco) del
1071
grafo (digrafo) @var{g} y @code{false} en caso contrario.
1077
@c c4 : cycle_graph(4)$
1078
@c is_edge_in_graph([2,3], c4);
1079
@c is_edge_in_graph([3,2], c4);
1080
@c is_edge_in_graph([2,4], c4);
1081
@c is_edge_in_graph([3,2], cycle_digraph(4));
1084
(%i1) load (graphs)$
1085
(%i2) c4 : cycle_graph(4)$
1086
(%i3) is_edge_in_graph([2,3], c4);
1088
(%i4) is_edge_in_graph([3,2], c4);
1090
(%i5) is_edge_in_graph([2,4], c4);
1092
(%i6) is_edge_in_graph([3,2], cycle_digraph(4));
1097
@deffn {Funci@'on} is_graph (@var{gr})
1098
Devuelve @code{true} si @var{gr} es un grafo y @code{false} en caso contrario.
1104
@c is_graph(path_graph(5));
1105
@c is_graph(path_digraph(5));
1108
(%i1) load (graphs)$
1109
(%i2) is_graph(path_graph(5));
1111
(%i3) is_graph(path_digraph(5));
1116
@deffn {Funci@'on} is_graph_or_digraph (@var{gr})
1117
Devuelve @code{true} si @var{gr} es una grafo, orientado o no,
1118
y @code{false} en caso contrario.
1124
@c is_graph_or_digraph(path_graph(5));
1125
@c is_graph_or_digraph(path_digraph(5));
1128
(%i1) load (graphs)$
1129
(%i2) is_graph_or_digraph(path_graph(5));
1131
(%i3) is_graph_or_digraph(path_digraph(5));
1136
@deffn {Funci@'on} is_isomorphic (@var{gr1}, @var{gr2})
1137
Devuelve @code{true} si los grafos/digrafos @var{gr1} y @var{gr2} son
1138
isomorfos y @code{false} en caso contrario.
1140
V@'ease tambi@'en @code{isomorphism}.
1146
@c clk5:complement_graph(line_graph(complete_graph(5)))$
1147
@c is_isomorphic(clk5, petersen_graph());
1150
(%i1) load (graphs)$
1151
(%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
1152
(%i3) is_isomorphic(clk5, petersen_graph());
1157
@deffn {Funci@'on} is_planar (@var{gr})
1158
Devuelve @code{true} si @var{gr} es un grafo planar y @code{false} en caso contrario.
1160
El algoritmo utilizado es el de Demoucron, que es de tiempo cuadr@'atico.
1166
@c is_planar(dodecahedron_graph());
1167
@c is_planar(petersen_graph());
1168
@c is_planar(petersen_graph(10,2));
1171
(%i1) load (graphs)$
1172
(%i2) is_planar(dodecahedron_graph());
1174
(%i3) is_planar(petersen_graph());
1176
(%i4) is_planar(petersen_graph(10,2));
1181
@deffn {Funci@'on} is_sconnected (@var{gr})
1182
Devuelve @code{true} si el grafo orientado @var{gr} es fuertemente conexo,
1183
devolviendo @code{false} en caso contrario.
1189
@c is_sconnected(cycle_digraph(5));
1190
@c is_sconnected(path_digraph(5));
1193
(%i1) load (graphs)$
1194
(%i2) is_sconnected(cycle_digraph(5));
1196
(%i3) is_sconnected(path_digraph(5));
1201
@deffn {Funci@'on} is_vertex_in_graph (@var{v}, @var{gr})
1202
Devuelve @code{true} si @var{v} es un v@'ertice del grafo @var{g}
1203
y @code{false} en caso contrario.
1209
@c c4 : cycle_graph(4)$
1210
@c is_vertex_in_graph(0, c4);
1211
@c is_vertex_in_graph(6, c4);
1214
(%i1) load (graphs)$
1215
(%i2) c4 : cycle_graph(4)$
1216
(%i3) is_vertex_in_graph(0, c4);
1218
(%i4) is_vertex_in_graph(6, c4);
1223
@deffn {Funci@'on} is_tree (@var{gr})
1224
Devuelve @code{true} si @var{gr} es un @'arbol y @code{false} en caso contrario.
1230
@c is_tree(random_tree(4));
1231
@c is_tree(graph_union(random_tree(4), random_tree(5)));
1234
(%i1) load (graphs)$
1235
(%i2) is_tree(random_tree(4));
1237
(%i3) is_tree(graph_union(random_tree(4), random_tree(5)));
1242
@deffn {Funci@'on} laplacian_matrix (@var{gr})
1243
Devuelve el laplaciano de la matriz del grafo @var{gr}.
1249
@c laplacian_matrix(cycle_graph(5));
1252
(%i1) load (graphs)$
1253
(%i2) laplacian_matrix(cycle_graph(5));
1258
(%o2) [ 0 - 1 2 - 1 0 ]
1266
@deffn {Funci@'on} max_clique (@var{gr})
1267
Devuelve el clique m@'aximo del grafo @var{gr}.
1273
@c g : random_graph(100, 0.5)$
1277
(%i1) load (graphs)$
1278
(%i2) g : random_graph(100, 0.5)$
1279
(%i3) max_clique(g);
1280
(%o3) [6, 12, 31, 36, 52, 59, 62, 63, 80]
1284
@deffn {Funci@'on} max_degree (@var{gr})
1285
Devuelve el grado m@'aximo de los v@'ertices del grafo @var{gr} y un
1286
v@'ertice de grado m@'aximo.
1292
@c g : random_graph(100, 0.02)$
1294
@c vertex_degree(95, g);
1297
(%i1) load (graphs)$
1298
(%i2) g : random_graph(100, 0.02)$
1299
(%i3) max_degree(g);
1301
(%i4) vertex_degree(95, g);
1306
@deffn {Funci@'on} max_flow (@var{net}, @var{s}, @var{t})
1307
Devuelve el flujo maximal de la red @var{net} con origen en
1308
@var{s} y final en @var{t}.
1310
La funci@'on devuelve el valor del flujo maximal y una lista con los
1311
pesos de los arcos del flujo @'optimo.
1318
@c net : create_graph(
1329
@c [flow_value, flow] : max_flow(net, 1, 6);
1331
@c for u in out_neighbors(1, net)
1332
@c do fl : fl + assoc([1, u], flow)$
1336
(%i1) load (graphs)$
1337
(%i2) net : create_graph(
1348
(%i3) [flow_value, flow] : max_flow(net, 1, 6);
1349
(%o3) [0.7, [[[1, 2], 0.5], [[1, 3], 0.2], [[2, 4], 0.2],
1350
[[2, 5], 0.3], [[3, 4], 0.1], [[3, 5], 0.1], [[4, 6], 0.3],
1353
(%i5) for u in out_neighbors(1, net)
1354
do fl : fl + assoc([1, u], flow)$
1360
@deffn {Funci@'on} max_independent_set (@var{gr})
1361
Devuelve un conjunto maximal independiente de v@'ertices del grafo @var{gr}.
1367
@c d : dodecahedron_graph()$
1368
@c mi : max_independent_set(d);
1369
@c draw_graph(d, show_vertices=mi)$
1372
(%i1) load (graphs)$
1373
(%i2) d : dodecahedron_graph()$
1374
(%i3) mi : max_independent_set(d);
1375
(%o3) [0, 3, 5, 9, 10, 11, 18, 19]
1376
(%i4) draw_graph(d, show_vertices=mi)$
1381
@image{../figures/graphs05,6cm}
1384
@deffn {Funci@'on} max_matching (@var{gr})
1385
Devuelve un conjunto maximal independiente de aristas del grafo @var{gr}.
1391
@c d : dodecahedron_graph()$
1392
@c m : max_matching(d);
1393
@c draw_graph(d, show_edges=m)$
1396
(%i1) load (graphs)$
1397
(%i2) d : dodecahedron_graph()$
1398
(%i3) m : max_matching(d);
1399
(%o3) [[5, 7], [8, 9], [6, 10], [14, 19], [13, 18], [12, 17],
1400
[11, 16], [0, 15], [3, 4], [1, 2]]
1401
(%i4) draw_graph(d, show_edges=m)$
1406
@image{../figures/graphs06,6cm}
1409
@deffn {Funci@'on} min_degree (@var{gr})
1410
Devuelve el grado m@'{@dotless{i}}nimo de los v@'ertices del grafo @var{gr} y un
1411
v@'ertice de grado m@'{@dotless{i}}nimo.
1417
@c g : random_graph(100, 0.1)$
1419
@c vertex_degree(21, g);
1422
(%i1) load (graphs)$
1423
(%i2) g : random_graph(100, 0.1)$
1424
(%i3) min_degree(g);
1426
(%i4) vertex_degree(21, g);
1431
@deffn {Funci@'on} min_edge_cut (@var{gr})
1432
Devuelve el m@'{@dotless{i}}nimo @i{edge cut} del grafo @var{gr}. Un @i{edge cut} es
1433
un conjunto de aristas cuya eliminaci@'on aumenta el n@'umero de componentes del grafo.
1435
V@'ease tambi@'en @code{edge_connectivity}.
1438
@deffn {Funci@'on} min_vertex_cover (@var{gr})
1439
Devuelve el m@'{@dotless{i}}nimo nodo @i{covering} del grafo @var{gr}.
1440
@c Esta traduccion esta tomada de la wikipedia. Habra que revisarla.
1443
@deffn {Funci@'on} min_vertex_cut (@var{gr})
1444
Devuelve el m@'{@dotless{i}}nimo @i{vertex cut} del grafo @var{gr}.
1446
V@'ease tambi@'en @code{vertex_connectivity}.
1450
@deffn {Funci@'on} minimum_spanning_tree (@var{gr})
1451
Devuelve el grafo de expansi@'on m@'{@dotless{i}}nimo del grafo @var{gr}.
1457
@c g : graph_product(path_graph(10), path_graph(10))$
1458
@c t : minimum_spanning_tree(g)$
1459
@c draw_graph(g, show_edges=edges(t))$
1462
(%i1) load (graphs)$
1463
(%i2) g : graph_product(path_graph(10), path_graph(10))$
1464
(%i3) t : minimum_spanning_tree(g)$
1465
(%i4) draw_graph(g, show_edges=edges(t))$
1470
@image{../figures/graphs07,6cm}
1473
@deffn {Funci@'on} neighbors (@var{v}, @var{gr})
1474
Devuelve la lista de los vecinos del v@'ertice @var{v} del grafo @var{gr}.
1480
@c p : petersen_graph()$
1484
(%i1) load (graphs)$
1485
(%i2) p : petersen_graph()$
1486
(%i3) neighbors(3, p);
1491
@deffn {Funci@'on} odd_girth (@var{gr})
1492
Devuelve la longitud del ciclo impar m@'as corto del grafo @var{gr}.
1498
@c g : graph_product(cycle_graph(4), cycle_graph(7))$
1503
(%i1) load (graphs)$
1504
(%i2) g : graph_product(cycle_graph(4), cycle_graph(7))$
1512
@deffn {Funci@'on} out_neighbors (@var{v}, @var{gr})
1513
Devuelve la lista de los nodos padres del v@'ertice @var{v} del grafo
1520
@c p : path_digraph(3)$
1521
@c in_neighbors(2, p);
1522
@c out_neighbors(2, p);
1525
(%i1) load (graphs)$
1526
(%i2) p : path_digraph(3)$
1527
(%i3) in_neighbors(2, p);
1529
(%i4) out_neighbors(2, p);
1534
@deffn {Funci@'on} planar_embedding (@var{gr})
1535
Devuelve la lista de caminos faciales en una proyecci@'on planar de @var{gr},
1536
o @code{false} si @var{gr} no es un grafo planar.
1538
El grafo @var{gr} debe estar biconectado.
1540
El algoritmo utilizado es el de Demoucron, que es de tiempo cuadr@'atico.
1546
@c planar_embedding(grid_graph(3,3));
1549
(%i1) load (graphs)$
1550
(%i2) planar_embedding(grid_graph(3,3));
1551
(%o2) [[3, 6, 7, 8, 5, 2, 1, 0], [4, 3, 0, 1], [3, 4, 7, 6],
1552
[8, 7, 4, 5], [1, 2, 5, 4]]
1556
@deffn {Funci@'on} print_graph (@var{gr})
1557
Muestra alguna informaci@'on sobre el grafo @var{gr}.
1563
@c c5 : cycle_graph(5)$
1565
@c dc5 : cycle_digraph(5)$
1566
@c print_graph(dc5)$
1567
@c out_neighbors(0, dc5);
1570
(%i1) load (graphs)$
1571
(%i2) c5 : cycle_graph(5)$
1572
(%i3) print_graph(c5)$
1573
Graph on 5 vertices with 5 edges.
1580
(%i4) dc5 : cycle_digraph(5)$
1581
(%i5) print_graph(dc5)$
1582
Digraph on 5 vertices with 5 arcs.
1589
(%i6) out_neighbors(0, dc5);
1594
@deffn {Funci@'on} radius (@var{gr})
1595
Devuelve el radio del grafo @var{gr}.
1601
@c radius(dodecahedron_graph());
1604
(%i1) load (graphs)$
1605
(%i2) radius(dodecahedron_graph());
1610
@deffn {Funci@'on} set_edge_weight (@var{e}, @var{w}, @var{gr})
1611
Asigna el peso @var{w} a la arista @var{e} del grafo @var{gr}.
1617
@c g : create_graph([1, 2], [[[1,2], 1.2]])$
1618
@c get_edge_weight([1,2], g);
1619
@c set_edge_weight([1,2], 2.1, g);
1620
@c get_edge_weight([1,2], g);
1623
(%i1) load (graphs)$
1624
(%i2) g : create_graph([1, 2], [[[1,2], 1.2]])$
1625
(%i3) get_edge_weight([1,2], g);
1627
(%i4) set_edge_weight([1,2], 2.1, g);
1629
(%i5) get_edge_weight([1,2], g);
1634
@deffn {Funci@'on} set_vertex_label (@var{v}, @var{l}, @var{gr})
1635
Asigna la etiqueta @var{l} al v@'ertice @var{v} del grafo @var{gr}.
1641
@c g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
1642
@c get_vertex_label(1, g);
1643
@c set_vertex_label(1, "oNE", g);
1644
@c get_vertex_label(1, g);
1647
(%i1) load (graphs)$
1648
(%i2) g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
1649
(%i3) get_vertex_label(1, g);
1651
(%i4) set_vertex_label(1, "oNE", g);
1653
(%i5) get_vertex_label(1, g);
1658
@deffn {Funci@'on} shortest_path (@var{u}, @var{v}, @var{gr})
1659
Devuelve el camino m@'as corto desde @var{u} hasta @var{v} del grafo @var{gr}.
1665
@c d : dodecahedron_graph()$
1666
@c path : shortest_path(0, 7, d);
1667
@c draw_graph(d, show_edges=vertices_to_path(path))$
1670
(%i1) load (graphs)$
1671
(%i2) d : dodecahedron_graph()$
1672
(%i3) path : shortest_path(0, 7, d);
1673
(%o3) [0, 1, 19, 13, 7]
1674
(%i4) draw_graph(d, show_edges=vertices_to_path(path))$
1679
@image{../figures/graphs08,6cm}
1683
@deffn {Funci@'on} shortest_weighted_path (@var{u}, @var{v}, @var{gr})
1684
Devuelve la longitud del camino m@'as corto ponderado y el propio camino
1685
m@'as corto ponderado desde @var{u} hasta @var{v} en el grafo @var{gr}.
1687
La longitud del camino ponderado es la suma de los pesos de las aristas
1688
del camino. Si una arista no tiene peso asignado, su valor por defecto
1695
@c g: petersen_graph(20, 2)$
1696
@c for e in edges(g) do set_edge_weight(e, random(1.0), g)$
1697
@c shortest_weighted_path(0, 10, g);
1700
(%i1) load (graphs)$
1701
(%i2) g: petersen_graph(20, 2)$
1702
(%i3) for e in edges(g) do set_edge_weight(e, random(1.0), g)$
1703
(%i4) shortest_weighted_path(0, 10, g);
1704
(%o4) [2.575143920268482, [0, 20, 38, 36, 34, 32, 30, 10]]
1710
@deffn {Funci@'on} strong_components (@var{gr})
1711
Devuelve las componentes fuertes del grafo orientado @var{gr}.
1717
@c t : random_tournament(4)$
1718
@c strong_components(t);
1719
@c vertex_out_degree(3, t);
1722
(%i1) load (graphs)$
1723
(%i2) t : random_tournament(4)$
1724
(%i3) strong_components(t);
1725
(%o3) [[1], [0], [2], [3]]
1726
(%i4) vertex_out_degree(3, t);
1731
@deffn {Funci@'on} topological_sort (@var{dag})
1732
Devuelve el orden topol@'ogico de los v@'ertices del grafo orientado @var{dag}
1733
o una lista vac@'{@dotless{i}}a si @var{dag} no es un grafo orientado
1734
ac@'{@dotless{i}}clico.
1743
@c [1,2], [2,5], [5,3],
1744
@c [5,4], [3,4], [1,3]
1747
@c topological_sort(g);
1750
(%i1) load (graphs)$
1751
(%i2) g:create_graph(
1754
[1,2], [2,5], [5,3],
1758
(%i3) topological_sort(g);
1759
(%o3) [1, 2, 5, 3, 4]
1763
@deffn {Funci@'on} vertex_connectivity (@var{g})
1764
Devuelve la conectividad de los v@'ertices del grafo @var{g}.
1766
V@'ease tambi@'en @code{min_vertex_cut}.
1769
@deffn {Funci@'on} vertex_degree (@var{v}, @var{gr})
1770
Devuelve el grado del v@'ertice @var{v} del grafo @var{gr}.
1773
@deffn {Funci@'on} vertex_distance (@var{u}, @var{v}, @var{gr})
1774
Devuelve la longitud del camino m@'as corto entre @var{u} y @var{v}
1775
del grafo o digrafo @var{gr}.
1781
@c d : dodecahedron_graph()$
1782
@c vertex_distance(0, 7, d);
1783
@c shortest_path(0, 7, d);
1786
(%i1) load (graphs)$
1787
(%i2) d : dodecahedron_graph()$
1788
(%i3) vertex_distance(0, 7, d);
1790
(%i4) shortest_path(0, 7, d);
1791
(%o4) [0, 1, 19, 13, 7]
1795
@deffn {Funci@'on} vertex_eccentricity (@var{v}, @var{gr})
1796
Devuelve la excentricidad del v@'ertice @var{v} del grafo @var{gr}.
1802
@c g:cycle_graph(7)$
1803
@c vertex_eccentricity(0, g);
1806
(%i1) load (graphs)$
1807
(%i2) g:cycle_graph(7)$
1808
(%i3) vertex_eccentricity(0, g);
1813
@deffn {Funci@'on} vertex_in_degree (@var{v}, @var{gr})
1814
Devuelve el grado de entrada del v@'ertice @var{v} del grafo
1821
@c p5 : path_digraph(5)$
1823
@c vertex_in_degree(4, p5);
1824
@c in_neighbors(4, p5);
1827
(%i1) load (graphs)$
1828
(%i2) p5 : path_digraph(5)$
1829
(%i3) print_graph(p5)$
1830
Digraph on 5 vertices with 4 arcs.
1837
(%i4) vertex_in_degree(4, p5);
1839
(%i5) in_neighbors(4, p5);
1844
@deffn {Funci@'on} vertex_out_degree (@var{v}, @var{gr})
1845
Devuelve el grado de salida del v@'ertice @var{v} del grafo
1852
@c t : random_tournament(10)$
1853
@c vertex_out_degree(0, t);
1854
@c out_neighbors(0, t);
1857
(%i1) load (graphs)$
1858
(%i2) t : random_tournament(10)$
1859
(%i3) vertex_out_degree(0, t);
1861
(%i4) out_neighbors(0, t);
1866
@deffn {Funci@'on} vertices (@var{gr})
1867
Devuelve la lista de v@'ertices del grafo @var{gr}.
1873
@c vertices(complete_graph(4));
1876
(%i1) load (graphs)$
1877
(%i2) vertices(complete_graph(4));
1882
@subsection Modificaci@'on de grafos
1885
@deffn {Funci@'on} add_edge (@var{e}, @var{gr})
1886
A@~nade la arista @var{e} al grafo @var{gr}.
1892
@c p : path_graph(4)$
1894
@c add_edge([0,3], p);
1898
(%i1) load (graphs)$
1899
(%i2) p : path_graph(4)$
1900
(%i3) neighbors(0, p);
1902
(%i4) add_edge([0,3], p);
1904
(%i5) neighbors(0, p);
1909
@deffn {Funci@'on} add_edges (@var{e_list}, @var{gr})
1910
A@~nade las aristas de la lista @var{e_list} al grafo @var{gr}.
1916
@c g : empty_graph(3)$
1917
@c add_edges([[0,1],[1,2]], g)$
1921
(%i1) load (graphs)$
1922
(%i2) g : empty_graph(3)$
1923
(%i3) add_edges([[0,1],[1,2]], g)$
1924
(%i4) print_graph(g)$
1925
Graph on 3 vertices with 2 edges.
1933
@deffn {Funci@'on} add_vertex (@var{v}, @var{gr})
1934
A@~nade el v@'ertice @var{v} al grafo @var{gr}.
1940
@c g : path_graph(2)$
1941
@c add_vertex(2, g)$
1945
(%i1) load (graphs)$
1946
(%i2) g : path_graph(2)$
1947
(%i3) add_vertex(2, g)$
1948
(%i4) print_graph(g)$
1949
Graph on 3 vertices with 1 edges.
1957
@deffn {Funci@'on} add_vertices (@var{v_list}, @var{gr})
1958
A@~nade los v@'ertices de la lista @var{v_list} al grafo @var{gr}.
1961
@deffn {Funci@'on} connect_vertices (@var{v_list}, @var{u_list}, @var{gr})
1962
Conecta todos los v@'ertices de la lista @var{v_list} con los v@'ertices
1963
de la lista @var{u_list} del grafo @var{gr}.
1965
@var{v_list} y @var{u_list} pueden ser v@'ertices aislados o una lista de
1972
@c g : empty_graph(4)$
1973
@c connect_vertices(0, [1,2,3], g)$
1977
(%i1) load (graphs)$
1978
(%i2) g : empty_graph(4)$
1979
(%i3) connect_vertices(0, [1,2,3], g)$
1980
(%i4) print_graph(g)$
1981
Graph on 4 vertices with 3 edges.
1990
@deffn {Funci@'on} contract_edge (@var{e}, @var{gr})
1991
Contrae la arista @var{e} del @var{gr}.
1998
@c 8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2000
@c contract_edge([3,4], g)$
2004
(%i1) load (graphs)$
2005
(%i2) g: create_graph(
2006
8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2007
(%i3) print_graph(g)$
2008
Graph on 8 vertices with 7 edges.
2018
(%i4) contract_edge([3,4], g)$
2019
(%i5) print_graph(g)$
2020
Graph on 7 vertices with 6 edges.
2032
@deffn {Funci@'on} remove_edge (@var{e}, @var{gr})
2033
Elimina la arista @var{e} del grafo @var{gr}.
2039
@c c3 : cycle_graph(3)$
2040
@c remove_edge([0,1], c3)$
2044
(%i1) load (graphs)$
2045
(%i2) c3 : cycle_graph(3)$
2046
(%i3) remove_edge([0,1], c3)$
2047
(%i4) print_graph(c3)$
2048
Graph on 3 vertices with 2 edges.
2056
@deffn {Funci@'on} remove_vertex (@var{v}, @var{gr})
2057
Elimina el v@'ertice @var{v} del grafo @var{gr}.
2060
@deffn {Funci@'on} vertex_coloring (@var{gr})
2061
Devuelve un coloreado @'optimo de los v@'ertice del grafo @var{gr}.
2063
La funci@'on devuelve el n@'umero crom@'atico y una lista representando
2064
el coloreado de los v@'ertices de @var{gr}.
2070
@c p:petersen_graph()$
2071
@c vertex_coloring(p);
2074
(%i1) load (graphs)$
2075
(%i2) p:petersen_graph()$
2076
(%i3) vertex_coloring(p);
2077
(%o3) [3, [[0, 2], [1, 3], [2, 2], [3, 3], [4, 1], [5, 3],
2078
[6, 1], [7, 1], [8, 2], [9, 2]]]
2083
@subsection Lectura y escritura de ficheros
2085
@deffn {Funci@'on} dimacs_export (@var{gr}, @var{fl})
2086
@deffnx {Funci@'on} dimacs_export (@var{gr}, @var{fl}, @var{comment1}, ..., @var{commentn})
2087
Exporta el grafo al fichero @var{fl} en formato DIMACS. Los comentarios
2088
adicionales se an@~adir@'an al comienzo del fichero.
2091
@deffn {Funci@'on} dimacs_import (@var{fl})
2092
Lee el grafo almacenado en el fichero @var{fl} en formato DIMACS.
2095
@deffn {Funci@'on} graph6_decode (@var{str})
2096
Devuelve el grafo codificado en formato graph6 en la cadena @var{str}.
2099
@deffn {Funci@'on} graph6_encode (@var{gr})
2100
Devuelve una cadena codificando el grafo @var{gr} en formato graph6.
2103
@deffn {Funci@'on} graph6_export (@var{gr_list}, @var{fl})
2104
Exporta los grafos de la lista @var{gr_list} al fichero @var{fl} en formato graph6.
2107
@deffn {Funci@'on} graph6_import (@var{fl})
2108
Lee la lista de grafos almacenados en el fichero @var{fl} en formato graph6.
2111
@deffn {Funci@'on} sparse6_decode (@var{str})
2112
Devuelve el grafo codificado en formato sparse6 en la cadena @var{str}.
2115
@deffn {Funci@'on} sparse6_encode (@var{gr})
2116
Devuelve una cadena codificando el grafo @var{gr} en formato sparse6.
2119
@deffn {Funci@'on} sparse6_export (@var{gr_list}, @var{fl})
2120
Exporta los grafos de la lista @var{gr_list} al fichero @var{fl} en formato sparse6.
2123
@deffn {Funci@'on} sparse6_import (@var{fl})
2124
Lee la lista de grafos almacenados en el fichero @var{fl} en formato sparse6.
2127
@subsection Visualizaci@'on
2129
@deffn {Funci@'on} draw_graph (@var{graph})
2130
@deffnx {Funci@'on} draw_graph (@var{graph}, @var{option1}, ..., @var{optionk})
2131
Dibuja el grafo utilizando el paquete @code{draw}.
2133
El algoritmo utilizado para posicionar los v@'ertices se especifica con el argumento
2134
opcional @var{program}, cuyo valor por defecto es @code{program=spring_embedding}.
2135
@var{draw_graph} tambi@'en puede utilizar los programas de graphviz para
2136
posicionar los v@'ertices, para lo cual deber@'a instalarse separadamente el programa graphviz.
2138
Los argumentos opcionales de la funci@'on @var{draw_graph} son:
2142
@dfn{show_id=show}: si @var{show} vale @var{true} entonces se muestran los
2143
n@'umeros identificadores de los v@'ertices.
2145
@dfn{show_label=show}: si @var{show} vale @var{true} entonces se muestran las
2146
etiquetas de los v@'ertices.
2148
@dfn{label_alignment=pos}: indica c@'omo se deben alinear las etiquetas o n@'umeros
2149
identificadores de los v@'ertices. Puede ser: @code{left}, @code{center} or @code{right}.
2150
El valor por defecto es @code{left}.
2152
@dfn{show_weight=show}: si @var{show} vale @var{true} entonces se mostrar@'an
2153
los pesos de las aristas.
2155
@dfn{vertex_type=type}: establece c@'omo se mostrar@'an los v@'ertices. V@'ease la
2156
opci@'on @var{point_type} del paquete @code{draw}.
2158
@dfn{vertex_size=size}: taman@~o de los v@'ertices.
2160
@dfn{vertex_color=c}: color a utilizar en los v@'ertices.
2162
@dfn{show_vertices=v_list}: dibuja los v@'ertices de la lista @var{v_list}
2163
con colores diferentes.
2165
@dfn{show_vertex_type=type}: establece c@'omo se mostrar@'an los v@'ertices de
2166
@var{show_vertices}. V@'ease la opci@'on @var{point_type} del paquete @code{draw}.
2168
@dfn{show_vertex_size=size}: taman@~os de los v@'ertices de @var{show_vertices}.
2170
@dfn{show_vertex_color=c}: color a utilizar en los v@'ertices de la lista @var{show_vertices}.
2172
@dfn{vertex_partition=part}: una partici@'on
2173
@code{[[v1,v2,...],...,[vk,...,vn]]} de los v@'ertices del grafo. Los
2174
v@'ertices de cada lista se dibujar@'an de diferente color.
2176
@dfn{vertex_coloring=col}: colores de los v@'ertices. Los colores @var{col} deben
2177
especificarse en el mismo formato que el devuelto por @var{vertex_coloring}.
2179
@dfn{edge_color=c}: color a utilizar en las aristas.
2181
@dfn{edge_width=width}: ancho de las aristas.
2183
@dfn{edge_type=type}: establece c@'omo se dibujar@'an las aristas. V@'ease la opci@'on
2184
@var{line_type} del paquete @code{draw}.
2186
@dfn{show_edges=e_list}: dibuja las aristas de la lista @var{e_list} con colores diferentes.
2188
@dfn{show_edge_color=c}: color a utilizar en las aristas de la lista @var{show_edges}.
2190
@dfn{show_edge_width=width}: anchos de las aristas de @var{show_edges}.
2192
@dfn{show_edge_type=type}: establece c@'omo se dibujar@'an las aristas de @var{show_edges}.
2193
V@'ease la opci@'on @var{line_type} del paquete @code{draw}.
2195
@dfn{edge_partition=partition}: una partici@'on
2196
@code{[[e1,e2,...],...,[ek,...,em]]} de las aristas del grafo. Las aristas
2197
de cada lista se dibujar@'an de diferente color.
2199
@dfn{edge_coloring=col}: colores de las aristas. Los colores @var{col} deben
2200
especificarse en el mismo formato que el devuelto por @var{edge_coloring}.
2202
@dfn{redraw=r}: si @var{redraw} vale @code{true}, las posiciones de los v@'ertices se recalculan
2203
incluso si las posiciones est@'an almacenadas de un dibujo previo del grafo.
2205
@dfn{head_angle=angle}: @'angulo de las flechas de los arcos en los grafos orientados.
2206
Valor por defecto: 15.
2208
@dfn{head_length=len}: longitud de las flechas de los arcos en los grafos orientados.
2209
Valor por defecto: 0.1.
2211
@dfn{spring_embedding_depth=depth}: n@'umero de iteraciones del algoritmo de dibujo de grafos.
2212
Valor por defecto: 50.
2214
@dfn{terminal=term}: terminal utilizado para ver el gr@'afo. V@'ease la opci@'on @var{terminal}
2215
del paquete @code{draw}.
2217
@dfn{file_name=file}: nombre del fichero cuando el terminal especificado no es la pantalla.
2219
@dfn{program=prg}: establece el programa para posicionado de v@'ertices del grafo. Puede ser
2220
cualquiera de los programas graphviz (dot, neato, twopi, circ, fdp), @var{circular} o
2221
@var{spring_embedding} o @var{planar_embedding}; @var{planar_embedding} s@'lo est@'a
2222
disponible para grafos planares 2-conectados. Si @code{program=spring_embedding},
2223
se puede especificar un conjunto de v@'ertices de posici@'on fija con la opci@'on
2224
@var{fixed_vertices}.
2226
@dfn{fixed_vertices=[]}: especifica una lista de v@'ertices con posiciones fijas en
2227
un pol@'{@dotless{i}}gono regular. Se puede utilizar cuando @code{program=spring_embedding}.
2234
@c g:grid_graph(10,10)$
2235
@c m:max_matching(g)$
2237
@c spring_embedding_depth=100,
2238
@c show_edges=m, edge_type=dots,
2242
(%i1) load (graphs)$
2243
(%i2) g:grid_graph(10,10)$
2244
(%i3) m:max_matching(g)$
2246
spring_embedding_depth=100,
2247
show_edges=m, edge_type=dots,
2252
@image{../figures/graphs09,6cm}
2259
@c g:create_graph(16,
2261
@c [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2262
@c [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2263
@c [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2264
@c [10,14],[15,14],[13,14]
2266
@c t:minimum_spanning_tree(g)$
2269
@c show_edges=edges(t),
2270
@c show_edge_width=4,
2271
@c show_edge_color=green,
2272
@c vertex_type=filled_square,
2277
(%i1) load (graphs)$
2278
(%i2) g:create_graph(16,
2280
[0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2281
[5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2282
[8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2283
[10,14],[15,14],[13,14]
2285
(%i3) t:minimum_spanning_tree(g)$
2288
show_edges=edges(t),
2290
show_edge_color=green,
2291
vertex_type=filled_square,
2297
@image{../figures/graphs10,6cm}
2304
@c mi : max_independent_set(g)$
2307
@c show_vertices=mi,
2308
@c show_vertex_type=filled_up_triangle,
2309
@c show_vertex_size=2,
2317
(%i1) load (graphs)$
2318
(%i2) mi : max_independent_set(g)$
2322
show_vertex_type=filled_up_triangle,
2332
@image{../figures/graphs11,6cm}
2339
@c net : create_graph(
2342
@c [[0,1], 3], [[0,2], 2],
2343
@c [[1,3], 1], [[1,4], 3],
2344
@c [[2,3], 2], [[2,4], 2],
2345
@c [[4,5], 2], [[3,5], 2]
2351
@c show_weight=true,
2353
@c show_vertices=[0,5],
2354
@c show_vertex_type=filled_square,
2357
@c edge_color="dark-green",
2362
(%i1) load (graphs)$
2363
(%i2) net : create_graph(
2366
[[0,1], 3], [[0,2], 2],
2367
[[1,3], 1], [[1,4], 3],
2368
[[2,3], 2], [[2,4], 2],
2369
[[4,5], 2], [[3,5], 2]
2377
show_vertices=[0,5],
2378
show_vertex_type=filled_square,
2381
edge_color="dark-green",
2387
@image{../figures/graphs12,6cm}
2394
@c g: petersen_graph(20, 2);
2395
@c draw_graph(g, redraw=true, program=planar_embedding);
2399
(%i2) g: petersen_graph(20, 2);
2401
(%i3) draw_graph(g, redraw=true, program=planar_embedding);
2406
@image{../figures/graphs14,6cm}
2413
@c t: tutte_graph();
2414
@c draw_graph(t, redraw=true, fixed_vertices=[1,2,3,4,5,6,7,8,9]);
2418
(%i2) t: tutte_graph();
2420
(%i3) draw_graph(t, redraw=true, fixed_vertices=[1,2,3,4,5,6,7,8,9]);
2425
@image{../figures/graphs15,6cm}
2431
@defvr {Variable opcional} draw_graph_program
2432
Valor por defecto: @var{spring_embedding}.
2434
Programa a utilizar por defecto para posicionar los v@'ertices en la funci@'on @code{draw_graph}.
2437
@deffn {Funci@'on} vertices_to_path (@var{v_list})
2438
Convierte una lista @var{v_list} de v@'ertices en la lista de aristas del camino
2439
definido por la propia @var{v_list}.
2442
@deffn {Funci@'on} vertices_to_cycle (@var{v_list})
2443
Convierte una lista @var{v_list} de v@'ertices en la lista de aristas del ciclo
2444
definido por la propia @var{v_list}.
added
removed
doc/info/es/graphs.texi
