Ââåäåíèå â ïàêåò graphs
=======================

Ïàêåò graphs ïðåäîñòàâëÿåò ñòðóêòóðû äëÿ ïðåäñòàâëåíèÿ ãðàôîâ è îðèåíòèðîâàííûõ ãðàôîâ â Maxima. Ãðàôû è îðèåíòèðîâàííûå ãðàôû ÿâëÿþòñÿ ïðîñòûìè, ò.å. íå èìåþò êðàòíûõ ðåáåð è ïåòåëü, íî îðèåíòèðîâàííûå ãðàôû ìîãóò èìåòü îðèåíòèðîâàííîå ðåáðî èç U â V è îðèåíòèðîâàííîå ðåáðî èç V â U.

Âíóòðåííå ãðàôû ïðåäñòàâëÿþòñÿ êàê ñïèñêè ñìåæíîñòè è ðåàëèçîâàíû â âèäå Lisp ñòðóêòóð. Âåðøèíû îáîçíà÷àþòñÿ ñâîèìè èäåíòèôèêàòîðàìè id (id -- åñòü öåëîå ÷èñëî). Ðåáðà/äóãè ïðåäñòàâëåíû ñïèñêàìè äëèíû 2. Âåðøèíàì ãðàôîâ è îðèåíòèðîâàííûõ ãðàôîâ ìîãóò áûòü ïðèñâîåíû ìåòêè à ðåáðàì/äóãàì ìîæíî ïðèñâîèòü âåñà.

Ôóíêöèÿ draw_graph ïðåäíàçíà÷åíà äëÿ ðèñîâàíèÿ ãðàôîâ. Ãðàôû èçîáðàæàþòñÿ ñ èñïîëüçîâàíèåì ìåòîäà âçàèìîäåéñòâèÿ ñèë. Ôóíêöèÿ draw_graph ìîæåò òàêæå èñïîëüçîâàòü ïðîãðàììó graphviz, äîñòóïíóþ ïî ññûëêå http://www.graphviz.org. Ôóíêöèÿ draw_graph îñíîâàíà íà ïàêåòå draw.

×òîáû èñïîëüçîâàòü ïàêåò graphs, åãî ñíà÷àëà ñëåäóåò çàãðóçèòü êîìàíäîé load(graphs).

Ôóíêöèè è ïåðåìåííûå ïàêåòà graphs
==================================

Ïîñòðîåíèå ãðàôîâ
-----------------

 -- Ôóíêöèÿ: create_graph (V_LIST, E_LIST)
 -- Ôóíêöèÿ: create_graph (N, E_LIST)
 -- Ôóíêöèÿ: create_graph (V_LIST, E_LIST, DIRECTED)
     Ñîçäàåò íîâûé ãðàô ñ ìíîæåñòâîì âåðøèí V_LIST è ðåáðàìè E_LIST.

     V_LIST -- ñïèñîê âåðøèí ([v1, v2,..., vn]) èëè âåðøèí âìåñòå ñ ìåòêàìè ([[v1,l1], [v2,l2],..., [vn,ln]]).

     Åñëè N -- ÷èñëî âåðøèí, òî îíè áóäóò îáîçíà÷àòüñÿ öåëûìè ÷èñëàìè îò 0 äî n-1.

     E_LIST -- ñïèñîê ðåáåð âèäà ([e1, e2,..., em]) èëè ñïèñîê ðåáåð âìåñòå ñ âåñàìè ([[e1, w1], ..., [em, wm]]).

     Åñëè DIRECTED îòëè÷íî îò false, òî âîçâðàùàåòñÿ îðèåíòèðîâàííûé ãðàô.

     Ïðèìåð 1: öèêë ñ òðåìÿ âåðøèíàìè:

          (%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

     Ïðèìåð 2: öèêë ñ òðåìÿ âåðøèíàìè è âåñàìè ðåáåð:

          (%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

     Ïðèìåð 3: îðèåíòèðîâàííûé ãðàô:

          (%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

 -- Ôóíêöèÿ: copy_graph (G)
     Âîçâðàùàåò êîïèþ ãðàôà G.

 -- Ôóíêöèÿ: circulant_graph (N, D)
     Âîçâðàùàåò öèðêóëÿíòíûé ãðàô ãðàô ñ ïàðàìåòðàìè N è D.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: clebsch_graph ()
     Âîçâðàùàåò ãðàô Êëåáøà (Clebsch graph).

 -- Ôóíêöèÿ: complement_graph (G)
     Âîçâðàùàåò ãðàô, äîïîëíèòåëüíûé ãðàôó G.

 -- Ôóíêöèÿ: complete_bipartite_graph (N, M)
     Âîçâðàùàåò ïîëíûé äâóäîëüíûé ãðàô ñ N+M âåðøèíàìè.

 -- Ôóíêöèÿ: complete_graph (N)
     Âîçâðàùàåò ïîëíûé ãðàô ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: cycle_digraph (N)
     Âîçâðàùàåò îðèåíòèðîâàííûé öèêëè÷åñêèé ãðàô ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: cycle_graph (N)
     Âîçâðàùàåò öèêëè÷åñêèé ãðàô ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: cube_graph (N)
     Âîçâðàùàåò N-ìåðíûé êóá.

 -- Ôóíêöèÿ: dodecahedron_graph ()
     Âîçâðàùàåò ãðàô äîäåêàýäðà.

 -- Ôóíêöèÿ: empty_graph (N)
     Âîçâðàùàåò ïóñòîé ãðàô ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: flower_snark (N)
     Âîçâðàùàåò öâåòî÷íûé ãðàô (flower graph) ñ 4N âåðøèíàìè.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: from_adjacency_matrix (A)
     Âîçâðàùàåò ãðàô ñ ìàòðèöåé ñìåæíîñòè A.

 -- Ôóíêöèÿ: frucht_graph ()
     Âîçâðàùàåò ãðàô Ôðó÷òà (Frucht graph).

 -- Ôóíêöèÿ: graph_product (G1, G1)
     Âîçâðàùàåò ïðÿìîå ïðîèçâåäåíèå ãðàôîâ G1 è G2.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_union (G1, G1)
     Âîçâðàùàåò îáúåäèíåíèå (ñóììó) ãðàôîâ G1 è G2.

 -- Ôóíêöèÿ: grid_graph (N, M)
     Âîçâðàùàåò ðåøåòêó N X M.

 -- Ôóíêöèÿ: grotzch_graph ()
     Âîçâðàùàåò ãðàô Ãðîò÷à (Grotzch graph).

 -- Ôóíêöèÿ: heawood_graph ()
     Âîçâðàùàåò ãðàô Õåéâóäà (Heawood graph).

 -- Ôóíêöèÿ: icosahedron_graph ()
     Âîçâðàùàåò ãðàô èêîñàýäðà.

 -- Ôóíêöèÿ: induced_subgraph (V, G)
     Âîçâðàùàåò ãðàô, ñîñòîÿùèé èç ïîäìíîæåñòâà âåðøèí V ãðàôà G.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: line_graph (G)
     Âîçâðàùàåò ãðàô äâîéñòâåííûé (line graph) ãðàôó G.

 -- Ôóíêöèÿ: make_graph (VRT, F)
 -- Ôóíêöèÿ: make_graph (VRT, F, ORIENTED)
     Ñîçäàåò ãðàô, èñïîëüçóÿ ôóíêöèþ ïðåäèêàò F.

     VRT -- åñòü ñïèñîê/ìíîæåñòâî âêðøèí èëè öåëîå ÷èñëî. Åñëè VRT åñòü öåëîå ÷èñëî, òî âåðøèíû ãðàôà áóäóò öåëûìè îò 1 äî VRT.

     F -- ôóíêöèÿ ïðåäèêàò.  Âåðøèíû A è B áóäóò ñîåäèíåíû, åñëè f(a,b)=true.

     Åñëè DIRECTED íå ðàâíî FALSE, òî ãðàô áóäåò îðèåíòèðîâàííûì.

     Ïðèìåð 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}

     Ïðèìåð 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]

 -- Ôóíêöèÿ: mycielski_graph (G)
     Âîçâðàùàåò ãðàô Ìèöåëüñêîãî (mycielskian graph) ãðàôà G.

 -- Ôóíêöèÿ: new_graph ()
     Âîçâðàùàåò ãðàô áåç âåðøèí è ðåáåð.

 -- Ôóíêöèÿ: path_digraph (N)
     Âîçâðàùàåò îðèåíòèðîâàííûé ïóòü ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: path_graph (N)
     Âîçâðàùàåò ïóòü ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: petersen_graph ()
 -- Ôóíêöèÿ: petersen_graph (N, D)
     Âîçâðàùàåò ãðàô Ïåòåðñåíà P_{N,D}. Çíà÷åíèÿ ïî óìîë÷àíèþ äëÿ N è D åñòü n=5 è d=2.

 -- Ôóíêöèÿ: random_bipartite_graph (A, B, P)
     Âîçâðàùàåò ñëó÷àéíûé äâóäîëüíûé ãðàô ñ a+b âåðøèíàìè. Êàæäàÿ âåðøèíà ïðèñóòñòâóåò ñ âåðîÿòíîñòüþ P.

 -- Ôóíêöèÿ: random_digraph (N, P)
     Âîçâðàùàåò ñëó÷àéíûé îðèåíòèðîâàííûé ãðàô ñ N âåðøèíàìè. Êàæäîå ðåáðî ïðèñóòñòâóåò ñ âåðîÿòíîñòüþ P.

 -- Ôóíêöèÿ: random_regular_graph (N)
 -- Ôóíêöèÿ: random_regular_graph (N, D)
     Âîçâðàùàåò ñëó÷àéíûé D-ðåãóëÿðíûé ãðàô ñ N âåðøèíàìè. Çíà÷åíèå ïî óìîë÷àíèþ äëÿ D åñòü d=3.

 -- Ôóíêöèÿ: random_graph (N, P)
     Âîçâðàùàåò ñëó÷àéíûé ãðàô ñ N âåðøèíàìè. Êàæäîå ðåáðî ïðèñóòñòâóåò ñ âåðîÿòíîñòüþ P.

 -- Ôóíêöèÿ: random_graph1 (N, M)
     Âîçâðàùàåò ñëó÷àéíûé ãðàô ñ N âåðøèíàìè è M ñëó÷àéíûìè ðåáðàìè.

 -- Ôóíêöèÿ: random_network (N, P, W)
     Âîçâðàùàåò ñëó÷àéíóþ ñåòü íà N âåðøèíàõ. Êàæäîå ðåáðî ïðèñóòñòâóåò ñ âåðîÿòíîñòüþ P è èìååò âåñ â èíòåðâàëå [0,w]. Ýòà ôóíêöèÿ âîçâðàùàåò ñïèñîê [network, source, sink].

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: random_tournament (N)
     Âîçâðàùàåò ñëó÷àéíûé ïîëíûé îðèåíòèðîâàííûé ãðàô (tournament) ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: random_tree (N)
     Âîçâðàùàåò ñëó÷àéíîå äåðåâî ñ N âåðøèíàìè.

 -- Ôóíêöèÿ: tutte_graph ()
     Âîçâðàùàåò ãðàô Òàòòà (Tutte).

 -- Ôóíêöèÿ: underlying_graph (G)
     Âîçâðàùàåò íåîðèåíòèðîâàííûé ãðàô, ïîëó÷àåìûé çàìåíîé ðåáåð îðèåíòèðîâàííîãî ãðàôà G íà íåîðèåíòèðîâàííûå.

 -- Ôóíêöèÿ: wheel_graph (N)
     Âîçâðàùàåò êîëåñíûé ãðàô (wheel graph) ñ N+1 âåðøèíàìè.

Ñâîéñòâà ãðàôîâ
---------------

 -- Ôóíêöèÿ: adjacency_matrix (GR)
     Âîçâðàùàåò ìàòðèöó ñìåæíîñòè ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: average_degree (GR)
     Âîçâðàùàåò ñðåäíþþ ñòåïåíü âåðøèí ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: biconected_components (GR)
     Âîçâðàùàåò (íàáîðû âåðøèí) 2-ñâÿçíûõ êîìïîíåíò ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: bipartition (GR)
     Âîçâðàùàåò äâóäîëüíîå ðàçëîæåíèå ãðàôà GR èëè ïóñòîé ñïèñîê, åñëè GR íå ÿâëÿåòñÿ äâóäîëüíûì.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: chromatic_index (GR)
     Âîçâðàùàåò õðîìàòè÷åñêèé èíäåêñ ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: chromatic_number (GR)
     Âîçâðàùàåò õðîìàòè÷åñêîå ÷èñëî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: clear_edge_weight (E, GR)
     Óäàëÿåò âåñ ðåáðà E â ãðàôå GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: clear_vertex_label (V, GR)
     Óäàëÿåò ìåòêó âåðøèíû V â ãðàôå GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: connected_components (GR)
     Âîçâðàùàåò (íàáîðû âåðøèí) êîìïîíåíòû ñâÿçíîñòè ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: diameter (GR)
     Âîçâðàùàåò äèàìåòð ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: edge_coloring (GR)
     Âîçâðàùàåò îïòèìàëüíóþ ðàñêðàñêó ðåáåð ãðàôà GR.

     Ýòà ôóíêöèÿ âîçâðàùàåò õðîìàòè÷åñêèé èíäåêñ è ñïèñîê, ïðåäñòàâëÿþùèé ðàñêðàñêó ðåáåð ãðàôà GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: degree_sequence (GR)
     Âîçâðàùàåò ñïèñîê ñòåïåíåé âåðøèí ãðàôà GR.

     Ïðèìåð:

          (%i1) load (graphs)$
          (%i2) degree_sequence(random_graph(10, 0.4));
          (%o2)            [3, 3, 3, 4, 4, 4, 5, 5, 6, 7]

 -- Ôóíêöèÿ: edges (GR)
     Âîçâðàùàåò ñïèñîê ðåáåð/äóã îðèåíòèðîâàííîãî èëè íåîðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: get_edge_weight (E, GR)
 -- Ôóíêöèÿ: get_edge_weight (E, GR, IFNOT)
     Âîçâðàùàåò âåñ ðåáðà E ãðàôà GR.

     Åñëè âåñ íå ïðèñâîåí ðåáðó, òî âîçâðàùàåòñÿ 1. Åñëè ðåáðî â ãðàôå îòñóòñòâóåò, òî âûäàåòñÿ îøèáêà èëè âîçâðàùàåò íåîáÿçàòåëüíûé àðãóìåíò IFNOT.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: get_vertex_label (V, GR)
     Âîçâðàùàåò ìåòêó âåðøèíû V ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_charpoly (GR, X)
     Âîçâðàùàåò õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí (îò ïåðåìåííîé X) ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_center (GR)
     Âîçâðàùàåò öåíòð ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_eigenvalues (GR)
     Âîçâðàùàåò ñîáñòâåííûå çíà÷åíèÿ ãðàôà GR. Çíà÷åíèå âîçâðàùàþòñÿ â òîì æå ôîðìàòå, ÷òî âîçâðàùàåò Maxima ôóíêöèÿ eigenvalue.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_periphery (GR)
     Âîçâðàùàåò ïåðèôåðèþ ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_size (GR)
     Âîçâðàùàåò ÷èñëî âåðøèí â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: graph_order (GR)
     Âîçâðàùàåò ÷èñëî ðåáåð â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: girth (GR)
     Âîçâðàùàåò äëèíó íàèêðàò÷àéøåãî öèêëà â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: hamilton_cycle (GR)
     Âîçâðàùàåò ãàìèëüòîíîâ öèêë ãðàôà GR èëè ïóñòîé ñïèñîê, åñëè ãðàô GR íå ÿâëÿåòñÿ ãàìèëüòîíîâûì.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: hamilton_path (GR)
     Âîçâðàùàåò ãàìèëüòîíîâ ïóòü ãðàôà GR èëè ïóñòîé ñïèñîê, åñëè ãðàô GR íå èìååò ãàìèëüòîíîâà ïóòè.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: isomorphism (GR1, GR2)

     Âîçâðàùàåò õýø-òàáëèöó èçîìîðôèçìà ìåæäó (îðèåíòèðîâàííûìè) ãðàôàìè GR1 è GR2. Åñëè GR1 è GR2 íå èçîìîðôíû, òî âîçâðàùàåòñÿ false.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: in_neighbors (V, GR)
     Âîçâðàùàåò ñïèñîê âõîäÿùèõ ñîñåäåé (in-neighbors) âåðøèíû V îðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_biconnected (GR)
     Âîçâðàùàåò true, åñëè ãðàô GR 2-ñâÿçíûé, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_bipartite (GR)
     Âîçâðàùàåò true, åñëè ãðàô GR äâóäîëüíûé, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_connected (GR)
     Âîçâðàùàåò true, åñëè ãðàô GR ñâÿçíûé, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_digraph (GR)
     Âîçâðàùàåò true, åñëè GR ÿâëÿåòñÿ îðèåíòèðîâàííûì ãðàôîì, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_edge_in_graph (E, GR)
     Âîçâðàùàåò true, åñëè E åñòü ðåáðî (îðèåíòèðîâàííîãî) ãðàôà G, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: is_graph (GR)
     Âîçâðàùàåò true, åñëè GR ÿâëÿåòñÿ ãðàôîì, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_graph_or_digraph (GR)
     Âîçâðàùàåò true, åñëè GR ÿâëÿåòñÿ ãðàôîì èëè îðèåíòèðîâàííûì ãðàôîì, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_isomorphic (GR1, GR2)

     Âîçâðàùàåò true, åñëè (îðèåíòèðîâàííûå) ãðàôû GR1 è GR2 èçîìîðôíû, è false â ïðîòèâíîì ñëó÷àå.

     Ñì. òàêæå isomorphism.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_planar (GR)

     Âîçâðàùàåò true, åñëè GR ÿâëÿåòñÿ ïëàíàðíûì ãðàôîì, è false â ïðîòèâíîì ñëó÷àå.

     Èñïîëüçóåòñÿ àëãîðèòì Äåìóêðîíà, êîòîðûé ÿâëÿåòñÿ êâàäðàòè÷íûì ïî âðåìåíè.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: is_sconnected (GR)
     Âîçâðàùàåò true, åñëè îðèåíòèðîâàííûé ãðàô GR ÿâëÿåòñÿ ñèëüíî ñâÿçíûì, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: is_vertex_in_graph (V, GR)
     Âîçâðàùàåò true, åñëè V åñòü âåðøèíà â ãðàôå G, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: is_tree (GR)
     Âîçâðàùàåò true, åñëè ãðàô GR ÿâëÿåòñÿ äåðåâîì, è false â ïðîòèâíîì ñëó÷àå.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: laplacian_matrix (GR)
     Âîçâðàùàåò ìàòðèöó Ëàïëàñà ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: max_clique (GR)
     Âîçâðàùàåò ìàêñèìàëüíóþ êëèêó ãðàôà GR.

     Ïðèìåð:

          (%i1) load (graphs)$
          (%i2) g : random_graph(100, 0.5)$
          (%i3) max_clique(g);
          (%o3)          [2, 6, 13, 17, 21, 23, 31, 62, 65]

 -- Ôóíêöèÿ: max_degree (GR)
     Âîçâðàùàåò ìàêñèìàëüíóþ ñòåïåíü âåðøèíû ãðàôà GR è ñàìó âåðøèíó ñ ìàêñèìàëüíîé ñòåïåíüþ.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: max_flow (NET, S, T)
     Âîçâðàùàåò ìàêñèìàëüíûé ïîòîê ÷åðåç ñåòü NET ñ èñòîêîì S è ñòîêîì T.

     Ôóíêöèÿ âîçâðàùàåò çíà÷åíèå ìàêñèìàëüíîãî ïîòîêà è ñïèñîê âåñîâ ðåáåð îïòèìàëüíîãî ïîòîêà.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: max_independent_set (GR)
     Âîçâðàùàåò ìàêñèìàëüíîå íåçàâèñèìîå ìíîæåñòâî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: max_matching (GR)
     Âîçâðàùàåò ìàêñèìàëüíûé íàáîð ðåáåð, íå èìåþùèõ îáùèõ âåðøèí (maximal matching), äëÿ ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: min_degree (GR)
     Âîçâðàùàåò ìèíèìàëüíóþ ñòåïåíü âåðøèíû ãðàôà GR è ñàìó âåðøèíó ñ ìèíèìàëüíîé ñòåïåíüþ.

     Ïðèìåð:

          (%i1) load (graphs)$
          (%i2) g : random_graph(100, 0.1)$
          (%i3) min_degree(g);
          (%o3)                        [4, 83]
          (%i4) vertex_degree(21, g);
          (%o4)                          12

 -- Ôóíêöèÿ: min_vertex_cover (GR)

     Âîçâðàùàåò ìèíèìàëüíîå âåðøèííîå ïîêðûòèå ãðàôà GR.

 -- Ôóíêöèÿ: minimum_spanning_tree (GR)
     Âîçâðàùàåò ìèíèìàëüíûé êàðêàñ (ìèíèìàëüíîå îñòîâíîå äåðåâî) ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: neighbors (V, GR)
     Âîçâðàùàåò ñïèñîê ñîñåäåé âåðøèíû V â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: odd_girth (GR)
     Âîçâðàùàåò äëèíó íàèêðàò÷àéøåãî íå÷åòíîãî öèêëà â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: out_neighbors (V, GR)
     Âîçâðàùàåò ñïèñîê èñõîäÿùèõ ñîñåäåé (out-neighbors) âåðøèíû V îðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: planar_embedding (GR)

     Âîçâðàùàåò ñïèñîê ïîâåðõíîñòíûõ ìàðøðóòîâ (facial walks) â ïëîñêîé óêëàäêå ãðàôà GR, è false, åñëè ãðàô GR íå ÿâëÿåòñÿ ïëàíàðíûì.

     Ãðàô GR äîëæåí áûòü áèñâÿçíûì.

     Èñïîëüçóåòñÿ àëãîðèòì Äåìóêðîíà, êîòîðûé ÿâëÿåòñÿ êâàäðàòè÷íûì ïî âðåìåíè.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: print_graph (GR)
     Âûâîäèò íåêîòîðóþ èíôîðìàöèþ î ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: radius (GR)
     Âîçâðàùàåò ðàäèóñ ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: set_edge_weight (E, W, GR)
     Ïðèñâàèâàåò âåñ W ðåáðó E ãðàôà GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: set_vertex_label (V, L, GR)
     Ïðèñâàèâàåò ìåòêó L âåðøèíå V ãðàôà GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: shortest_path (U, V, GR)
     Âîçâðàùàåò êðàò÷àéøèé ïóòü èç âåðøèíû U â âåðøèíó V â ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: strong_components (GR)
     Âîçâðàùàåò ñèëüíóþ êîìïîíåíòó îðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: topological_sort (DAG)

     Âîçâðàùàåò òîïîëîãè÷åñêóþ ñîðòèðîâêó âåðøèí îðèåíòèðîâàííîãî ãðàôà DAG, èëè ïóñòîé ñïèñîê, åñëè DAG íå ÿâëÿåòñÿ îðèåíòèðîâàííûì àöèêëè÷åñêèì ãðàôîì.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: vertex_degree (V, GR)
     Âîçâðàùàåò ñòåïåíü âåðøèíû V â ãðàôå GR.

 -- Ôóíêöèÿ: vertex_distance (U, V, GR)
     Âîçâðàùàåò äëèíó êðàò÷àéøåãî ïóòè ìåæäó âåðøèíàìè U è V â (îðèåíòèðîâàííîì) ãðàôå GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: vertex_eccentricity (V, GR)

     Âîçâðàùàåò ýêñöåíòðèñèòåò âåðøèíû V ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: vertex_in_degree (V, GR)
     Âîçâðàùàåò âõîäÿùóþ ñòåïåíü âåðøèíû V îðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: vertex_out_degree (V, GR)
     Âîçâðàùàåò èñõîäÿùóþ ñòåïåíü âåðøèíû V îðèåíòèðîâàííîãî ãðàôà GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: vertices (GR)
     Âîçâðàùàåò ñïèñîê âåðøèí ãðàôà  GR.

     Ïðèìåð:

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

Èçìåíåíèå ãðàôîâ
----------------

 -- Ôóíêöèÿ: add_edge (E, GR)
     Äîáàâëÿåò ðåáðî E ê ãðàôó GR.

     Ïðèìåð:

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

 -- Ôóíêöèÿ: add_edges (E_LIST, GR)
     Äîáàâëÿåò ðåáðà èç ñïèñêà E_LIST ê ãðàôó GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: add_vertex (V, GR)
     Äîáàâëÿåò âåðøèíó V ê ãðàôó GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: add_vertices (V_LIST, GR)
     Äîáàâëÿåò âñå âåðøèíû èç ñïèñêà V_LIST ê ãðàôó GR.

 -- Ôóíêöèÿ: connect_vertices (V_LIST, U_LIST, GR)
     Ñîåäèíÿåò âñå âåðøèíû èç ñïèñêà V_LIST ñ âåðøèíàìè èç ñïèñêà U_LIST â ãðàôå GR.

     V_LIST è U_LIST ìîãóò áûòü îòäåëüíûìè âåðøèíàìè èëè ñïèñêàìè âåðøèí.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: contract_edge (E, GR)
     Ñòÿãèâàåò ðåáðî E â ãðàôå GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: remove_edge (E, GR)
     Óäàëÿåò ðåáðî E èç ãðàôà GR.

     Ïðèìåð:

          (%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

 -- Ôóíêöèÿ: remove_vertex (V, GR)
     Óäàëÿåò âåðøèíó V èç ãðàôà GR.

 -- Ôóíêöèÿ: vertex_coloring (GR)
     Âîçâðàùàåò îïòèìàëüíóþ ðàñêðàñêó âåðøèí ãðàôà GR.

     Ôóíêöèÿ âîçâðàùàåò õðîìàòè÷åñêîå ÷èñëî è ñïèñîê, îïèñûâàþùèé ðàñêðàñêó âåðøèí ãðàôà G.

     Ïðèìåð:

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

×òåíèå è çàïèñü ôàéëîâ
----------------------

 -- Ôóíêöèÿ: dimacs_export (GR, FL)
 -- Ôóíêöèÿ: dimacs_export (GR, FL, COMMENT1, ..., COMMENTN)

     Ýêñïîðòèðóåò ãðàô â ôàéë FL â ôîðìàòå DIMACS. Íåîáÿçàòåëüíûé êîììåíòàðèé áóäåò äîáàâëåí ê íà÷àëó ôàéëà.

 -- Ôóíêöèÿ: dimacs_import (FL)

     Âîçâðàùàåò ãðàô èç ôàéëà FL, â êîòîðîì îí çàïèñàí â ôîðìàòå DIMACS.

 -- Ôóíêöèÿ: graph6_decode (STR)

     Âîçâðàùàåò ãðàô, çàêîäèðîâàííûé â ôîðìàòå graph6 â ñòðîêå STR.

 -- Ôóíêöèÿ: graph6_encode (GR)

     Âîçâðàùàåò ñòðîêó -- çàêîäèðîâàííîå ïðåäñòàâëåíèå ãðàôà GR â ôîðìàòå graph6.

 -- Ôóíêöèÿ: graph6_export (GR_LIST, FL)

     Ýêñïîðòèðóåò ãðàôû èç ñïèñêà GR_LIST â ôàéë FL â ôîðìàòå graph6.

 -- Ôóíêöèÿ: graph6_import (FL)

     Âîçâðàùàåò ñïèñîê ãðàôîâ èç ôàéëà FL, ãäå îíè çàêîäèðîâàíû â ôîðìàòå graph6.

 -- Ôóíêöèÿ: sparse6_decode (STR)

     Âîçâðàùàåò ãðàô, çàêîäèðîâàííûé â ôîðìàòå sparse6 â ñòðîêå STR.

 -- Ôóíêöèÿ: sparse6_encode (GR)

     Âîçâðàùàåò ñòðîêó -- çàêîäèðîâàííîå ïðåäñòàâëåíèå ãðàôà GR â ôîðìàòå sparse6.

 -- Ôóíêöèÿ: sparse6_export (GR_LIST, FL)

     Ýêñïîðòèðóåò ãðàôû èç ñïèñêà GR_LIST â ôàéë FL â ôîðìàòå sparse6.

 -- Ôóíêöèÿ: sparse6_import (FL)

     Âîçâðàùàåò ñïèñîê ãðàôîâ èç ôàéëà FL, ãäå îíè çàêîäèðîâàíû â ôîðìàòå sparse6.

Âèçóàëèçàöèÿ
------------

 -- Ôóíêöèÿ: draw_graph (GRAPH)
 -- Ôóíêöèÿ: draw_graph (GRAPH, OPTION1, ..., OPTIONK)
     Èçîáðàæàåò ãðàô ñ ïîìîùüþ ïàêåòà draw.

     Àëãîðèòì, èñïîëüçóåìûé äëÿ ðàçìåùåíèÿ âåðøèí, îïðåäåëÿåòñÿ íåîáÿçàòåëüíîé ïåðåìåííîé PROGRAM. Çíà÷åíèå ïî óìîë÷àíèþ program=spring_embedding. Ìîæåò òàêæå èñïîëüçîâàòüñÿ ïðîãðàììà graphviz, íî îíà äîëæíà áûòü óñòàíîâëåíà îòäåëüíî.

     Íåîáÿçàòåëüíûå àðãóìåíòû DRAW_GRAPH ìîãóò áûòü:

       * show_id=show: åñëè SHOW ðàâíî TRUE, òî èçîáðàæàþòñÿ èäåíòèôèêàòîðû (id) âåðøèí.

       * show_label=show: åñëè SHOW ðàâíî TRUE, òî èçîáðàæàþòñÿ ìåòêè âåðøèí.

       * label_alignment=pos: êàê ðàçìåñòèòü ìåòêó èëè èäåíòèôèêàòîð âåðøèíû. Ìîæåò áûòü left, center èëè  right. Ïî óìîë÷àíèþ left.

       * show_weight=show: åñëè SHOW ðàâíî TRUE, òî èçîáðàæàþòñÿ âåñà ðåáåð.

       * vertex_type=type: îïðåäåëÿåò, êàê èçîáðàæàþòñÿ âåðøèíû. Ñì. îïöèþ POINT_TYPE ïàêåòà draw.

       * vertex_size=size: ðàçìåð âåðøèí.

       * vertex_color=c: öâåò âåðøèí.

       * show_vertices=v_list: èçîáðàçèòü âåðøèíû èç ñïèñêà V_LIST äðóãèì öâåòîì.

       * show_vertex_type=type: îïðåäåëÿåò, êàê èçîáðàæàþòñÿ âåðøèíû èç ñïèñêà SHOW_VERTICES. Ñì. îïöèþ POINT_TYPE ïàêåòà draw.

       * show_vertex_size=size: ðàçìåð âåðøèí â ñïèñêå SHOW_VERTICES.

       * show_vertex_color=c: öâåò âåðøèí â ñïèñêå SHOW_VERTICES.

       * vertex_partition=part: ðàçáèåíèå [[v1,v2,...],...,[vk,...,vn]] âåðøèí ãðàôà. Âåðøèíû â êàæäîì ñïèñêà áóäóò èçîáðàæàòüñÿ ðàçíûìè öâåòàìè.

       * vertex_coloring=col: ðàñêðàñêà âåðøèí. Ðàñêðàñêà COL äîëæíà áûòü çàäàíà â ôîðìàòå, âîçâðàùàåìîì VERTEX_COLORING.

       * edge_color=c: öâåò, èñïîëüçóåìûé äëÿ èçîáðàæåíèÿ ðåáåð.

       * edge_width=width: òîëùèíà ðåáåð.

       * edge_type=type: îïðåäåëÿåò ñïîñîá èçîáðàæåíèÿ ðåáåð. Ñì. îïöèþ LINE_TYPE ïàêåòà draw.

       * show_edges=e_list: èçîáðàæàòü ðåáðà èç ñïèñêà E_LIST äðóãèì öâåòîì.

       * show_edge_color=c: öâåò, èñïîëüçóåìûé äëÿ èçîáðàæåíèÿ ðåáåð èç ñïèñêà SHOW_EDGES.

       * show_edge_width=width: øèðèíà ðåáåð SHOW_EDGES.

       * show_edge_type=type: îïðåäåëÿåò, êàê èçîáðàæàþòñÿ ðåáðà èç ñïèñêà SHOW_EDGES. Ñì. îïöèþ LINE_TYPE ïàêåòà draw.

       * edge_partition=partition: ðàçáèåíèå [[e1,e2,...],...,[ek,...,em]] ðåáåð ãðàôà. Ðåáðà â êàæäîì ñïèñêå áóäóò èçîáðàæàòüñÿ ðàçíûìè öâåòàìè.

       * edge_coloring=col: ðàñêðàñêà ðåáåð. Ðàñêðàñêà COL äîëæíà áûòü çàäàíà â ôîðìàòå, âîçâðàùàåìîì ôóíêöèåé EDGE_COLORING.

       * redraw=r: åñëè REDRAW ðàâíî true, òî ïîëîæåíèå âåðøèí âû÷èñëÿåòñÿ ñíîâà, äàæå åñëè îíî áûëî ñîõðàíåíî ñ ïðåäûäóùåãî èçîáðàæåíèÿ ãðàôà.

       * head_angle=angle: óãîë íàêîíå÷íèêîâ ñòðåëîê, èçîáðàæàåìûõ íà ðåáðàõ îðèåíòèðîâàííûõ ãðàôîâ. Çíà÷åíèå ïî óìîë÷àíèþ: 15.

       * head_length=len: äëèíà íàêîíå÷íèêîâ ñòðåëîê, èçîáðàæàåìûõ íà ðåáðàõ îðèåíòèðîâàííûõ ãðàôîâ. Çíà÷åíèå ïî óìîë÷àíèþ: 0.1.

       * spring_embedding_depth=depth: ÷èñëî èòåðàöèé â àëãîðèòìå ïðóæèí (ìåòîä âçàèìîäåéñòâèÿ ñèë). Çíà÷åíèå ïî óìîë÷àíèþ: 50.

       * terminal=term: òåðìèíàë, èñïîëüçóåìûé äëÿ èçîáðàæåíèÿ (ñì. îïöèþ TERMINAL ïàêåòà draw).

       * file_name=file: èìÿ ôàéëà èçîáðàæåíèÿ, åñëè òåðìèíàë íå ÿâëÿåòñÿ äèñïëååì.

       * program=prg: îïðåäåëÿåò ïðîãðàììó, èñïîëüçóåìóþ äëÿ ðàñïîëîæåíèÿ âåðøèí ãðàôà. Ìîæåò áûòü îäíîé èç îïöèé ïðîãðàììû graphviz (dot, neato, twopi, circ, fdp), CIRCULAR, SPRING_EMBEDDING èëè PLANAR_EMBEDDING. PLANAR_EMBEDDING ïðèìåìåíèìî òîëüêî 2-ñâÿçíûì ïëàíàðíûì ãðàôàì. Êîãäà program=spring_embedding, òî íàáîð âåðøèí ñ ôèêñèðîâàííûì ðàñïîëîæåíèåì ìîæåò áûòü çàäàí ñ ïîìîùüþ îïöèè FIXED_VERTICES.

       * fixed_vertices=[]: çàäàåò ñïèñîê âåðøèí, êîòîðûå áóäóò ðàñïîëîæåíû â ôèêñîðîâàííûõ ïîçèöèÿõ ïî ïðàâèëüíîìó ìíîãîãðàííèêó. Ìîæåò èñïîëüçîâàòüñÿ ñîâìåñòíî ñ program=spring_embedding.

     Ïðèìåð 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)$

     Ïðèìåð 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
              )$

     Ïðèìåð 3:

          (%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) mi : max_independent_set(g)$
          (%i4) draw_graph(
              g,
              show_vertices=mi,
              show_vertex_type=filled_up_triangle,
              show_vertex_size=2,
              edge_color=cyan,
              edge_width=3,
              show_id=true,
              text_color=brown
              )$

     Ïðèìåð 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
              )$

 -- Óïðàâëÿþùàÿ ïåðåìåííàÿ: draw_graph_program
     Çíà÷åíèå ïî óìîë÷àíèþ: SPRING_EMBEDDING.

     Çíà÷åíèå ïî óìîë÷àíèþ, êîòîðîå èñïîëüçóåòñÿ äëÿ ðàñïîëîæåíèÿ âåðøèí â ïðîãðàììå draw_graph.

 -- Ôóíêöèÿ: vertices_to_path (V_LIST)
     Ïðåîáðàçóåò ñïèñîê âåðøèí V_LIST â ñïèñîê ðåáåð ïóòè, îïðåäåëÿåìîãî ñïèñêîì V_LIST.

 -- Ôóíêöèÿ: vertices_to_cycle (V_LIST)
     Ïðåîáðàçóåò ñïèñîê âåðøèí V_LIST â ñïèñîê ðåáåð öèêëà, îïðåäåëÿåìîãî ñïèñêîì V_LIST.