doc/info/ja/graphs.texi

   1 @menu
   2 * Introduction to graphs::
   3 * Functions and Variables for graphs::
   4 @end menu
   5
   6 @node Introduction to graphs, Functions and Variables for graphs, graphs, graphs
   7 @section Introduction to graphs
   8
   9 @code{graphs}パッケージはMaximaにグラフと有向グラフデータ構造を提供します。
  10 有向グラフは@var{u}から@var{v}への有向辺と@var{v}から@var{u}への有向辺を持つことができますが、グラフや有向グラフは単純です(多重辺もループも持ちません)。
  11
  12 内部的にはグラフは隣接リストで表現され、
  13 lisp構造として実装されます。
  14 頂点はそれらのid(idは整数)で識別されます。
  15 辺/弧は長さ2のリストで表現されます。
  16 グラフ/有向グラフの頂点にラベルを割り当てることができ、
  17 グラフ/有向グラフの辺/弧に重みを割り当てることができます。
  18
  19 グラフを描画するためのの@code{draw_graph}関数があります。
  20 グラフはforce based 頂点配置アルゴリズムを使って描画されます。
  21 @code{draw_graph}は
  22 @url{http://www.graphviz.org}から利用可能なgraphvizプログラムを使うこともできます。
  23 @code{draw_graph}はMaxima @code{draw}パッケージに基づいています。
  24
  25 @code{graphs}パッケージを使うには、
  26 最初に@code{load("graphs")}でロードしてください。
  27
  28 @opencatbox
  29 @category{Share packages}
  30 @category{Package graphs}
  31 @closecatbox
  32
  33 @node Functions and Variables for graphs, , Introduction to graphs, graphs
  34 @section Functions and Variables for graphs
  35
  36 @subsection Building graphs
  37
  38 @deffn {関数} create_graph (@var{v_list}, @var{e_list})
  39 @deffnx {関数} create_graph (@var{n}, @var{e_list})
  40 @deffnx {関数} create_graph (@var{v_list}, @var{e_list}, @var{directed})
  41 頂点の集合@var{v_list}上に辺@var{e_list}を使って新しいグラフを生成します。
  42
  43 @var{v_list}は頂点のリスト(@code{[v1, v2,..., vn]})もしくは
  44 頂点ラベルを持つ頂点のリスト(@code{[[v1,l1], [v2,l2],..., [vn,ln]]})です。
  45
  46 @var{n}は頂点の数です。
  47 頂点は0からn-1までの整数で識別されます。
  48 (訳注: 1から始まるMaximaのリストの添字の慣例とは異なることに注意してください。)
  49
  50 @var{e_list}は辺のリスト(@code{[e1, e2,..., em]})もしくは
  51 辺の重みを持つ辺のリスト(@code{[[e1, w1], ..., [em, wm]]})です。
  52
  53 もし@var{directed}が@code{false}でないなら、
  54 有向グラフが返されます。
  55
  56 例1: 頂点3つの循環を生成する。
  57 @c ===beg===
  58 @c load ("graphs")$
  59 @c g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
  60 @c print_graph(g)$
  61 @c ===end===
  62 @example
  63 (%i1) load ("graphs")$
  64 (%i2) g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
  65 (%i3) print_graph(g)$
  66 Graph on 3 vertices with 3 edges.
  67 Adjacencies:
  68   3 :  1  2
  69   2 :  3  1
  70   1 :  3  2
  71 @end example
  72
  73 例2: 辺の重みを持つ頂点3つの循環を生成する。
  74 @c ===beg===
  75 @c load ("graphs")$
  76 @c g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
  77 @c                           [[1,3], 3.0]])$
  78 @c print_graph(g)$
  79 @c ===end===
  80 @example
  81 (%i1) load ("graphs")$
  82 (%i2) g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
  83                           [[1,3], 3.0]])$
  84 (%i3) print_graph(g)$
  85 Graph on 3 vertices with 3 edges.
  86 Adjacencies:
  87   3 :  1  2
  88   2 :  3  1
  89   1 :  3  2
  90 @end example
  91
  92 例3: 有向グラフを生成する:
  93 @c ===beg===
  94 @c load ("graphs")$
  95 @c d : create_graph(
  96 @c         [1,2,3,4],
  97 @c         [
  98 @c          [1,3], [1,4],
  99 @c          [2,3], [2,4]
 100 @c         ],
 101 @c         'directed = true)$
 102 @c print_graph(d)$
 103 @c ===end===
 104 @example
 105 (%i1) load ("graphs")$
 106 (%i2) d : create_graph(
 107         [1,2,3,4],
 108         [
 109          [1,3], [1,4],
 110          [2,3], [2,4]
 111         ],
 112         'directed = true)$
 113 (%i3) print_graph(d)$
 114 Digraph on 4 vertices with 4 arcs.
 115 Adjacencies:
 116   4 :
 117   3 :
 118   2 :  4  3
 119   1 :  4  3
 120 @end example
 121
 122 @opencatbox
 123 @category{Package graphs}
 124 @closecatbox
 125 @end deffn
 126
 127 @deffn {関数} copy_graph (@var{g})
 128 グラフ@var{g}のコピーを返します。
 129
 130 @opencatbox
 131 @category{Package graphs}
 132 @category{Package graphs - constructions}
 133 @closecatbox
 134 @end deffn
 135
 136 @deffn {関数} circulant_graph (@var{n}, @var{d})
 137 パラメータ @var{n}と @var{d}を持つ巡回グラフを返します。
 138
 139 例:
 140 @c ===beg===
 141 @c load ("graphs")$
 142 @c g : circulant_graph(10, [1,3])$
 143 @c print_graph(g)$
 144 @c ===end===
 145 @example
 146 (%i1) load ("graphs")$
 147 (%i2) g : circulant_graph(10, [1,3])$
 148 (%i3) print_graph(g)$
 149 Graph on 10 vertices with 20 edges.
 150 Adjacencies:
 151   9 :  2  6  0  8
 152   8 :  1  5  9  7
 153   7 :  0  4  8  6
 154   6 :  9  3  7  5
 155   5 :  8  2  6  4
 156   4 :  7  1  5  3
 157   3 :  6  0  4  2
 158   2 :  9  5  3  1
 159   1 :  8  4  2  0
 160   0 :  7  3  9  1
 161 @end example
 162
 163 @opencatbox
 164 @category{Package graphs}
 165 @category{Package graphs - constructions}
 166 @closecatbox
 167 @end deffn
 168
 169 @deffn {関数} clebsch_graph ()
 170 Clebschグラフを返します。
 171
 172 @opencatbox
 173 @category{Package graphs}
 174 @category{Package graphs - constructions}
 175 @closecatbox
 176 @end deffn
 177
 178 @deffn {関数} complement_graph (@var{g})
 179 グラフ @var{g}の補グラフを返します。
 180
 181 @opencatbox
 182 @category{Package graphs}
 183 @category{Package graphs - constructions}
 184 @closecatbox
 185 @end deffn
 186
 187 @deffn {関数} complete_bipartite_graph (@var{n}, @var{m})
 188 @var{n+m}この頂点上の完全2部グラフを返します。
 189
 190 @opencatbox
 191 @category{Package graphs}
 192 @category{Package graphs - constructions}
 193 @closecatbox
 194 @end deffn
 195
 196 @deffn {関数} complete_graph (@var{n})
 197 @var{n}この頂点上の完全グラフを返します。
 198
 199 @opencatbox
 200 @category{Package graphs}
 201 @category{Package graphs - constructions}
 202 @closecatbox
 203 @end deffn
 204
 205 @deffn {関数} cycle_digraph (@var{n})
 206 @var{n}個の頂点上の有向グラフを返します。
 207
 208 @opencatbox
 209 @category{Package graphs}
 210 @category{Package graphs - constructions}
 211 @closecatbox
 212 @end deffn
 213
 214 @deffn {関数} cycle_graph (@var{n})
 215 @var{n}この頂点上の閉路を返します。
 216
 217 @opencatbox
 218 @category{Package graphs}
 219 @category{Package graphs - constructions}
 220 @closecatbox
 221 @end deffn
 222
 223 @deffn {関数} cuboctahedron_graph (@var{n})
 224 立方八面体グラフを返します。
 225
 226 @opencatbox
 227 @category{Package graphs}
 228 @category{Package graphs - constructions}
 229 @closecatbox
 230 @end deffn
 231
 232 @deffn {関数} cube_graph (@var{n})
 233 @var{n}次元立方体を返します。
 234
 235 @opencatbox
 236 @category{Package graphs}
 237 @category{Package graphs - constructions}
 238 @closecatbox
 239 @end deffn
 240
 241 @deffn {関数} dodecahedron_graph ()
 242 十二面体グラフを返します。
 243
 244 @opencatbox
 245 @category{Package graphs}
 246 @category{Package graphs - constructions}
 247 @closecatbox
 248 @end deffn
 249
 250 @deffn {関数} empty_graph (@var{n})
 251 @var{n}個の頂点上の空グラフを返します。
 252
 253 @opencatbox
 254 @category{Package graphs}
 255 @category{Package graphs - constructions}
 256 @closecatbox
 257 @end deffn
 258
 259 @deffn {関数} flower_snark (@var{n})
 260 @var{4n}個の頂点上の花グラフを返します。
 261
 262 例:
 263 @c ===beg===
 264 @c load ("graphs")$
 265 @c f5 : flower_snark(5)$
 266 @c chromatic_index(f5);
 267 @c ===end===
 268 @example
 269 (%i1) load ("graphs")$
 270 (%i2) f5 : flower_snark(5)$
 271 (%i3) chromatic_index(f5);
 272 (%o3)                           4
 273 @end example
 274
 275 @opencatbox
 276 @category{Package graphs}
 277 @category{Package graphs - constructions}
 278 @closecatbox
 279 @end deffn
 280
 281 @deffn {関数} from_adjacency_matrix (@var{A})
 282 隣接行列 @var{A}で表現されるグラフを返します。
 283
 284 @opencatbox
 285 @category{Package graphs}
 286 @category{Package graphs - constructions}
 287 @closecatbox
 288 @end deffn
 289
 290 @deffn {関数} frucht_graph ()
 291 Fruchtグラフを返します。
 292
 293 @opencatbox
 294 @category{Package graphs}
 295 @category{Package graphs - constructions}
 296 @closecatbox
 297 @end deffn
 298
 299 @deffn {関数} graph_product (@var{g1}, @var{g1})
 300 グラフ @var{g1}と @var{g2}の直積を返します。
 301
 302 例:
 303 @c ===beg===
 304 @c load ("graphs")$
 305 @c grid : graph_product(path_graph(3), path_graph(4))$
 306 @c draw_graph(grid)$
 307 @c ===end===
 308 @example
 309 (%i1) load ("graphs")$
 310 (%i2) grid : graph_product(path_graph(3), path_graph(4))$
 311 (%i3) draw_graph(grid)$
 312 @end example
 313
 314 @opencatbox
 315 @category{Package graphs}
 316 @category{Package graphs - constructions}
 317 @closecatbox
 318 @end deffn
 319
 320 @ifhtml
 321 @image{@value{figuresfolder}/graphs01,6cm}
 322 @end ifhtml
 323
 324 @deffn {関数} graph_union (@var{g1}, @var{g1})
 325 グラフ@var{g1}と @var{g2}の和を返します。
 326
 327 @opencatbox
 328 @category{Package graphs}
 329 @category{Package graphs - constructions}
 330 @closecatbox
 331 @end deffn
 332
 333 @deffn {関数} grid_graph (@var{n}, @var{m})
 334 @var{n x m}グリッドを返します。
 335
 336 @opencatbox
 337 @category{Package graphs}
 338 @category{Package graphs - constructions}
 339 @closecatbox
 340 @end deffn
 341
 342 @deffn {関数} great_rhombicosidodecahedron_graph ()
 343 大菱形二十・十二面体グラフを返します。
 344
 345 @opencatbox
 346 @category{Package graphs}
 347 @category{Package graphs - constructions}
 348 @closecatbox
 349 @end deffn
 350
 351 @deffn {関数} great_rhombicuboctahedron_graph ()
 352 大斜方立方八面体グラフを返します。
 353
 354 @opencatbox
 355 @category{Package graphs}
 356 @category{Package graphs - constructions}
 357 @closecatbox
 358 @end deffn
 359
 360 @deffn {関数} grotzch_graph ()
 361 Grotzchグラフを返します。
 362
 363 @opencatbox
 364 @category{Package graphs}
 365 @category{Package graphs - constructions}
 366 @closecatbox
 367 @end deffn
 368
 369 @deffn {関数} heawood_graph ()
 370 Heawoodグラフを返します。
 371
 372 @opencatbox
 373 @category{Package graphs}
 374 @category{Package graphs - constructions}
 375 @closecatbox
 376 @end deffn
 377
 378 @deffn {関数} icosahedron_graph ()
 379 二十面体グラフを返します。
 380
 381 @opencatbox
 382 @category{Package graphs}
 383 @category{Package graphs - constructions}
 384 @closecatbox
 385 @end deffn
 386
 387 @deffn {関数} icosidodecahedron_graph ()
 388 二十・十二面体グラフを返します。
 389
 390 @opencatbox
 391 @category{Package graphs}
 392 @category{Package graphs - constructions}
 393 @closecatbox
 394 @end deffn
 395
 396 @deffn {関数} induced_subgraph (@var{V}, @var{g})
 397 グラフ @var{g}の頂点の部分集合 @var{V}上の誘導部分グラフを返します。
 398
 399 例:
 400 @c ===beg===
 401 @c load ("graphs")$
 402 @c p : petersen_graph()$
 403 @c V : [0,1,2,3,4]$
 404 @c g : induced_subgraph(V, p)$
 405 @c print_graph(g)$
 406 @c ===end===
 407 @example
 408 (%i1) load ("graphs")$
 409 (%i2) p : petersen_graph()$
 410 (%i3) V : [0,1,2,3,4]$
 411 (%i4) g : induced_subgraph(V, p)$
 412 (%i5) print_graph(g)$
 413 Graph on 5 vertices with 5 edges.
 414 Adjacencies:
 415   4 :  3  0
 416   3 :  2  4
 417   2 :  1  3
 418   1 :  0  2
 419   0 :  1  4
 420 @end example
 421
 422 @opencatbox
 423 @category{Package graphs}
 424 @category{Package graphs - constructions}
 425 @closecatbox
 426 @end deffn
 427
 428 @deffn {関数} line_graph (@var{g})
 429 グラフ @var{g}の折れ線グラフを返します。
 430
 431 @opencatbox
 432 @category{Package graphs}
 433 @category{Package graphs - constructions}
 434 @closecatbox
 435 @end deffn
 436
 437 @deffn {関数} make_graph (@var{vrt}, @var{f})
 438 @deffnx {関数} make_graph (@var{vrt}, @var{f}, @var{oriented})
 439 述語論理関数 @var{f}を使ってグラフを生成します。
 440
 441 @var{vrt}は頂点か整数のリスト/集合です。
 442 もし @var{vrt}が整数なら、
 443 グラフの頂点は1から @var{vrt}までの整数です。
 444
 445 @var{f}は述語論理関数です。
 446 2つの頂点 @var{a}と @var{b}は
 447 もし @code{f(a,b)=true}なら結合されます。
 448
 449 もし @var{directed}が @var{false}でないなら、
 450 グラフは有向です。
 451
 452 例 1:
 453 @c ===beg===
 454 @c load("graphs")$
 455 @c g : make_graph(powerset({1,2,3,4,5}, 2), disjointp)$
 456 @c is_isomorphic(g, petersen_graph());
 457 @c get_vertex_label(1, g);
 458 @c ===end===
 459 @example
 460 (%i1) load("graphs")$
 461 (%i2) g : make_graph(powerset(@{1,2,3,4,5@}, 2), disjointp)$
 462 (%i3) is_isomorphic(g, petersen_graph());
 463 (%o3)                         true
 464 (%i4) get_vertex_label(1, g);
 465 (%o4)                        @{1, 2@}
 466 @end example
 467
 468 例 2:
 469 @c ===beg===
 470 @c load("graphs")$
 471 @c f(i, j) := is (mod(j, i)=0)$
 472 @c g : make_graph(20, f, directed=true)$
 473 @c out_neighbors(4, g);
 474 @c in_neighbors(18, g);
 475 @c ===end===
 476 @example
 477 (%i1) load("graphs")$
 478 (%i2) f(i, j) := is (mod(j, i)=0)$
 479 (%i3) g : make_graph(20, f, directed=true)$
 480 (%i4) out_neighbors(4, g);
 481 (%o4)                    [8, 12, 16, 20]
 482 (%i5) in_neighbors(18, g);
 483 (%o5)                    [1, 2, 3, 6, 9]
 484 @end example
 485
 486 @opencatbox
 487 @category{Package graphs}
 488 @category{Package graphs - constructions}
 489 @closecatbox
 490 @end deffn
 491
 492 @deffn {関数} mycielski_graph (@var{g})
 493 グラフ @var{g}のMycielskiグラフを返します。
 494
 495 @opencatbox
 496 @category{Package graphs}
 497 @category{Package graphs - constructions}
 498 @closecatbox
 499 @end deffn
 500
 501 @deffn {関数} new_graph ()
 502 頂点も辺も持たないグラフを返します。
 503
 504 @opencatbox
 505 @category{Package graphs}
 506 @category{Package graphs - constructions}
 507 @closecatbox
 508 @end deffn
 509
 510 @deffn {関数} path_digraph (@var{n})
 511 @var{n}個の頂点上の有向道を返します。
 512
 513 @opencatbox
 514 @category{Package graphs}
 515 @category{Package graphs - constructions}
 516 @closecatbox
 517 @end deffn
 518
 519 @deffn {関数} path_graph (@var{n})
 520 @var{n}個の頂点上の道を返します。
 521
 522 @opencatbox
 523 @category{Package graphs}
 524 @category{Package graphs - constructions}
 525 @closecatbox
 526 @end deffn
 527
 528 @deffn {関数} petersen_graph ()
 529 @deffnx {関数} petersen_graph (@var{n}, @var{d})
 530 Petersenグラフ @var{P_@{n,d@}}を返します。
 531 @var{n}と @var{d}のデフォルト値は
 532 @code{n=5}と @code{d=2}です。
 533
 534 @opencatbox
 535 @category{Package graphs}
 536 @category{Package graphs - constructions}
 537 @closecatbox
 538 @end deffn
 539
 540 @deffn {関数} random_bipartite_graph (@var{a}, @var{b}, @var{p})
 541 @code{a+b}個の頂点上のランダムな2部グラフを返します。
 542 辺それぞれは確率 @var{p}で存在します。
 543
 544 @opencatbox
 545 @category{Package graphs}
 546 @category{Package graphs - constructions}
 547 @closecatbox
 548 @end deffn
 549
 550 @deffn {関数} random_digraph (@var{n}, @var{p})
 551 @code{n}個の頂点上のランダムな有向グラフを返します。
 552 弧それぞれは確率 @var{p}で存在します。
 553
 554 @opencatbox
 555 @category{Package graphs}
 556 @category{Package graphs - constructions}
 557 @closecatbox
 558 @end deffn
 559
 560 @deffn {関数} random_regular_graph (@var{n})
 561 @deffnx {関数} random_regular_graph (@var{n}, @var{d})
 562 @var{n}個の頂点上の
 563 ランダムな@var{d}正則グラフを返します。
 564 @var{d}のデフォルト値は @code{d=3}です。
 565
 566 @opencatbox
 567 @category{Package graphs}
 568 @category{Package graphs - constructions}
 569 @closecatbox
 570 @end deffn
 571
 572 @deffn {関数} random_graph (@var{n}, @var{p})
 573 @var{n}個の頂点上のランダムグラフを返します。
 574 辺それぞれは確率 @var{p}で存在します。
 575
 576 @opencatbox
 577 @category{Package graphs}
 578 @category{Package graphs - constructions}
 579 @closecatbox
 580 @end deffn
 581
 582 @deffn {関数} random_graph1 (@var{n}, @var{m})
 583 @var{n}個の頂点とランダムな @var{m}個の辺上のランダムグラフを返します。
 584
 585 @opencatbox
 586 @category{Package graphs}
 587 @category{Package graphs - constructions}
 588 @closecatbox
 589 @end deffn
 590
 591 @deffn {関数} random_network (@var{n}, @var{p}, @var{w})
 592 @var{n}個の頂点上のランダムネットワークを返します。
 593 弧それぞれは確率 @var{p}で存在し、
 594 範囲 @code{[0,w]}の中に重みを持ちます。
 595 関数はリスト @code{[network, source, sink]}を返します。
 596
 597 例:
 598 @c ===beg===
 599 @c load ("graphs")$
 600 @c [net, s, t] : random_network(50, 0.2, 10.0);
 601 @c max_flow(net, s, t)$
 602 @c first(%);
 603 @c ===end===
 604 @example
 605 (%i1) load ("graphs")$
 606 (%i2) [net, s, t] : random_network(50, 0.2, 10.0);
 607 (%o2)                   [DIGRAPH, 50, 51]
 608 (%i3) max_flow(net, s, t)$
 609 (%i4) first(%);
 610 (%o4)                   27.65981397932507
 611 @end example
 612
 613 @opencatbox
 614 @category{Package graphs}
 615 @category{Package graphs - constructions}
 616 @closecatbox
 617 @end deffn
 618
 619 @deffn {関数} random_tournament (@var{n})
 620 @var{n}個の頂点上のランダムなトーナメントを返します。
 621
 622 @opencatbox
 623 @category{Package graphs}
 624 @category{Package graphs - constructions}
 625 @closecatbox
 626 @end deffn
 627
 628 @deffn {関数} random_tree (@var{n})
 629 @var{n}個の頂点上のランダムな木を返します。
 630
 631 @opencatbox
 632 @category{Package graphs}
 633 @category{Package graphs - constructions}
 634 @closecatbox
 635 @end deffn
 636
 637 @deffn {関数} small_rhombicosidodecahedron_graph ()
 638 斜方二十・十二面体グラフを返します。
 639
 640 @opencatbox
 641 @category{Package graphs}
 642 @category{Package graphs - constructions}
 643 @closecatbox
 644 @end deffn
 645
 646 @deffn {関数} small_rhombicuboctahedron_graph ()
 647 斜方立方八面体グラフを返します。
 648
 649 @opencatbox
 650 @category{Package graphs}
 651 @category{Package graphs - constructions}
 652 @closecatbox
 653 @end deffn
 654
 655 @deffn {関数} snub_cube_graph ()
 656 変形立方体グラフを返します。
 657
 658 @opencatbox
 659 @category{Package graphs}
 660 @category{Package graphs - constructions}
 661 @closecatbox
 662 @end deffn
 663
 664 @deffn {関数} snub_dodecahedron_graph ()
 665 変形十二面体グラフを返します。
 666
 667 @opencatbox
 668 @category{Package graphs}
 669 @category{Package graphs - constructions}
 670 @closecatbox
 671 @end deffn
 672
 673 @deffn {関数} truncated_cube_graph ()
 674 切頂六面体グラフを返します。
 675
 676 @opencatbox
 677 @category{Package graphs}
 678 @category{Package graphs - constructions}
 679 @closecatbox
 680 @end deffn
 681
 682 @deffn {関数} truncated_dodecahedron_graph ()
 683 切頂十二面体グラフを返します。
 684
 685 @opencatbox
 686 @category{Package graphs}
 687 @category{Package graphs - constructions}
 688 @closecatbox
 689 @end deffn
 690
 691
 692 @deffn {関数} truncated_icosahedron_graph ()
 693 切頂二十面体グラフを返します。
 694
 695 @opencatbox
 696 @category{Package graphs}
 697 @category{Package graphs - constructions}
 698 @closecatbox
 699 @end deffn
 700
 701
 702 @deffn {関数} truncated_tetrahedron_graph ()
 703 切頂四面体グラフを返します。
 704
 705 @opencatbox
 706 @category{Package graphs}
 707 @category{Package graphs - constructions}
 708 @closecatbox
 709 @end deffn
 710
 711 @deffn {関数} tutte_graph ()
 712 Tutteグラフを返します。
 713
 714 @opencatbox
 715 @category{Package graphs}
 716 @category{Package graphs - constructions}
 717 @closecatbox
 718 @end deffn
 719
 720 @deffn {関数} underlying_graph (@var{g})
 721 有向グラフ @var{g}の台グラフを返します。
 722
 723 @opencatbox
 724 @category{Package graphs}
 725 @category{Package graphs - constructions}
 726 @closecatbox
 727 @end deffn
 728
 729 @deffn {関数} wheel_graph (@var{n})
 730 @var{n+1}個の頂点上の車輪グラフを返します。
 731
 732 @opencatbox
 733 @category{Package graphs}
 734 @category{Package graphs - constructions}
 735 @closecatbox
 736 @end deffn
 737
 738 @subsection Graph properties
 739
 740 @deffn {関数} adjacency_matrix (@var{gr})
 741 グラフ @var{gr}の隣接行列を返します。
 742
 743 例:
 744 @c ===beg===
 745 @c load ("graphs")$
 746 @c c5 : cycle_graph(4)$
 747 @c adjacency_matrix(c5);
 748 @c ===end===
 749 @example
 750 (%i1) load ("graphs")$
 751 (%i2) c5 : cycle_graph(4)$
 752 (%i3) adjacency_matrix(c5);
 753                          [ 0  1  0  1 ]
 754                          [            ]
 755                          [ 1  0  1  0 ]
 756 (%o3)                    [            ]
 757                          [ 0  1  0  1 ]
 758                          [            ]
 759                          [ 1  0  1  0 ]
 760 @end example
 761
 762 @opencatbox
 763 @category{Package graphs}
 764 @category{Package graphs - properties}
 765 @closecatbox
 766 @end deffn
 767
 768 @deffn {関数} average_degree (@var{gr})
 769 グラフ @var{gr}に関する平均次数を返します。
 770
 771 例:
 772 @c ===beg===
 773 @c load ("graphs")$
 774 @c average_degree(grotzch_graph());
 775 @c ===end===
 776 @example
 777 (%i1) load ("graphs")$
 778 (%i2) average_degree(grotzch_graph());
 779                                40
 780 (%o2)                          --
 781                                11
 782 @end example
 783
 784 @opencatbox
 785 @category{Package graphs}
 786 @category{Package graphs - properties}
 787 @closecatbox
 788 @end deffn
 789
 790 @deffn {関数} biconnected_components (@var{gr})
 791 グラフ @var{gr}の2連結成分(の頂点集合)を返します
 792
 793 例:
 794 @c ===beg===
 795 @c load ("graphs")$
 796 @c g : create_graph(
 797 @c             [1,2,3,4,5,6,7],
 798 @c             [
 799 @c              [1,2],[2,3],[2,4],[3,4],
 800 @c              [4,5],[5,6],[4,6],[6,7]
 801 @c             ])$
 802 @c biconnected_components(g);
 803 @c ===end===
 804 @example
 805 (%i1) load ("graphs")$
 806 (%i2) g : create_graph(
 807             [1,2,3,4,5,6,7],
 808             [
 809              [1,2],[2,3],[2,4],[3,4],
 810              [4,5],[5,6],[4,6],[6,7]
 811             ])$
 812 (%i3) biconnected_components(g);
 813 (%o3)        [[6, 7], [4, 5, 6], [1, 2], [2, 3, 4]]
 814 @end example
 815
 816 @ifhtml
 817 @image{@value{figuresfolder}/graphs13,6cm}
 818 @end ifhtml
 819
 820 @opencatbox
 821 @category{Package graphs}
 822 @category{Package graphs - properties}
 823 @closecatbox
 824 @end deffn
 825
 826 @deffn {関数} bipartition (@var{gr})
 827 グラフ @var{gr}の頂点の2分割か、もし @var{gr}が2部でないなら空のリストを返します。
 828
 829 例:
 830
 831 @c ===beg===
 832 @c load ("graphs")$
 833 @c h : heawood_graph()$
 834 @c [A,B]:bipartition(h);
 835 @c draw_graph(h, show_vertices=A, program=circular)$
 836 @c ===end===
 837 @example
 838 (%i1) load ("graphs")$
 839 (%i2) h : heawood_graph()$
 840 (%i3) [A,B]:bipartition(h);
 841 (%o3)  [[8, 12, 6, 10, 0, 2, 4], [13, 5, 11, 7, 9, 1, 3]]
 842 (%i4) draw_graph(h, show_vertices=A, program=circular)$
 843 @end example
 844
 845 @opencatbox
 846 @category{Package graphs}
 847 @category{Package graphs - properties}
 848 @closecatbox
 849 @end deffn
 850
 851 @ifhtml
 852 @image{@value{figuresfolder}/graphs02,6cm}
 853 @end ifhtml
 854
 855 @deffn {関数} chromatic_index (@var{gr})
 856 グラフ @var{gr}の彩色指数を返します。
 857
 858 例:
 859 @c ===beg===
 860 @c load ("graphs")$
 861 @c p : petersen_graph()$
 862 @c chromatic_index(p);
 863 @c ===end===
 864 @example
 865 (%i1) load ("graphs")$
 866 (%i2) p : petersen_graph()$
 867 (%i3) chromatic_index(p);
 868 (%o3)                           4
 869 @end example
 870
 871 @opencatbox
 872 @category{Package graphs}
 873 @category{Package graphs - properties}
 874 @closecatbox
 875 @end deffn
 876
 877 @deffn {関数} chromatic_number (@var{gr})
 878 グラフ @var{gr}の彩色数を返します。
 879
 880 例:
 881 @c ===beg===
 882 @c load ("graphs")$
 883 @c chromatic_number(cycle_graph(5));
 884 @c chromatic_number(cycle_graph(6));
 885 @c ===end===
 886 @example
 887 (%i1) load ("graphs")$
 888 (%i2) chromatic_number(cycle_graph(5));
 889 (%o2)                           3
 890 (%i3) chromatic_number(cycle_graph(6));
 891 (%o3)                           2
 892 @end example
 893
 894 @opencatbox
 895 @category{Package graphs}
 896 @category{Package graphs - properties}
 897 @closecatbox
 898 @end deffn
 899
 900 @deffn {関数} clear_edge_weight (@var{e}, @var{gr})
 901 グラフ @var{gr}の辺  @var{e}の重みを削除します。
 902
 903 例:
 904
 905 @c ===beg===
 906 @c load ("graphs")$
 907 @c g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
 908 @c get_edge_weight([0,1], g);
 909 @c clear_edge_weight([0,1], g)$
 910 @c get_edge_weight([0,1], g);
 911 @c ===end===
 912 @example
 913 (%i1) load ("graphs")$
 914 (%i2) g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
 915 (%i3) get_edge_weight([0,1], g);
 916 (%o3)                          1.5
 917 (%i4) clear_edge_weight([0,1], g)$
 918 (%i5) get_edge_weight([0,1], g);
 919 (%o5)                           1
 920 @end example
 921
 922 @opencatbox
 923 @category{Package graphs}
 924 @category{Package graphs - properties}
 925 @closecatbox
 926 @end deffn
 927
 928 @deffn {関数} clear_vertex_label (@var{v}, @var{gr})
 929 グラフ @var{gr}の頂点 @var{v}のラベルを削除します。
 930
 931 例:
 932 @c ===beg===
 933 @c load ("graphs")$
 934 @c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
 935 @c get_vertex_label(0, g);
 936 @c clear_vertex_label(0, g);
 937 @c get_vertex_label(0, g);
 938 @c ===end===
 939 @example
 940 (%i1) load ("graphs")$
 941 (%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
 942 (%i3) get_vertex_label(0, g);
 943 (%o3)                         Zero
 944 (%i4) clear_vertex_label(0, g);
 945 (%o4)                         done
 946 (%i5) get_vertex_label(0, g);
 947 (%o5)                         false
 948 @end example
 949
 950 @opencatbox
 951 @category{Package graphs}
 952 @category{Package graphs - properties}
 953 @closecatbox
 954 @end deffn
 955
 956 @deffn {関数} connected_components (@var{gr})
 957 グラフ @var{gr}の連携成分(の頂点集合)を返します。
 958
 959 例:
 960 @c ===beg===
 961 @c load ("graphs")$
 962 @c g: graph_union(cycle_graph(5), path_graph(4))$
 963 @c connected_components(g);
 964 @c ===end===
 965 @example
 966 (%i1) load ("graphs")$
 967 (%i2) g: graph_union(cycle_graph(5), path_graph(4))$
 968 (%i3) connected_components(g);
 969 (%o3)            [[1, 2, 3, 4, 0], [8, 7, 6, 5]]
 970 @end example
 971
 972 @opencatbox
 973 @category{Package graphs}
 974 @category{Package graphs - properties}
 975 @closecatbox
 976 @end deffn
 977
 978 @deffn {関数} diameter (@var{gr})
 979 グラフ @var{gr}の直径を返します。
 980
 981 例:
 982 @c ===beg===
 983 @c load ("graphs")$
 984 @c diameter(dodecahedron_graph());
 985 @c ===end===
 986 @example
 987 (%i1) load ("graphs")$
 988 (%i2) diameter(dodecahedron_graph());
 989 (%o2)                           5
 990 @end example
 991
 992 @opencatbox
 993 @category{Package graphs}
 994 @category{Package graphs - properties}
 995 @closecatbox
 996 @end deffn
 997
 998 @deffn {関数} edge_coloring (@var{gr})
 999 グラフ @var{gr}の辺の最適色づけを返します。
1000
1001 関数は彩色指数と@var{gr}の辺の色付けを表すリストを返します。
1002
1003
1004 例:
1005 @c ===beg===
1006 @c load ("graphs")$
1007 @c p : petersen_graph()$
1008 @c [ch_index, col] : edge_coloring(p);
1009 @c assoc([0,1], col);
1010 @c assoc([0,5], col);
1011 @c ===end===
1012 @example
1013 (%i1) load ("graphs")$
1014 (%i2) p : petersen_graph()$
1015 (%i3) [ch_index, col] : edge_coloring(p);
1016 (%o3) [4, [[[0, 5], 3], [[5, 7], 1], [[0, 1], 1], [[1, 6], 2],
1017 [[6, 8], 1], [[1, 2], 3], [[2, 7], 4], [[7, 9], 2], [[2, 3], 2],
1018 [[3, 8], 3], [[5, 8], 2], [[3, 4], 1], [[4, 9], 4], [[6, 9], 3],
1019 [[0, 4], 2]]]
1020 (%i4) assoc([0,1], col);
1021 (%o4)                           1
1022 (%i5) assoc([0,5], col);
1023 (%o5)                           3
1024 @end example
1025
1026 @opencatbox
1027 @category{Package graphs}
1028 @category{Package graphs - properties}
1029 @closecatbox
1030 @end deffn
1031
1032 @deffn {関数} degree_sequence (@var{gr})
1033 グラフ @var{gr}の頂点次数のリストを返します。
1034
1035 例:
1036 @c ===beg===
1037 @c load ("graphs")$
1038 @c degree_sequence(random_graph(10, 0.4));
1039 @c ===end===
1040 @example
1041 (%i1) load ("graphs")$
1042 (%i2) degree_sequence(random_graph(10, 0.4));
1043 (%o2)            [2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
1044 @end example
1045
1046 @opencatbox
1047 @category{Package graphs}
1048 @category{Package graphs - properties}
1049 @closecatbox
1050 @end deffn
1051
1052 @deffn {関数} edge_connectivity (@var{gr})
1053 グラフ @var{gr}の辺連結性を返します。
1054
1055 @code{min_edge_cut}も参照してください。
1056
1057 @opencatbox
1058 @category{Package graphs}
1059 @category{Package graphs - properties}
1060 @closecatbox
1061 @end deffn
1062
1063 @deffn {関数} edges (@var{gr})
1064 (有向)グラフ @var{gr}の辺(弧)のリストを返します。
1065
1066 例:
1067 @c ===beg===
1068 @c load ("graphs")$
1069 @c edges(complete_graph(4));
1070 @c ===end===
1071 @example
1072 (%i1) load ("graphs")$
1073 (%i2) edges(complete_graph(4));
1074 (%o2)   [[2, 3], [1, 3], [1, 2], [0, 3], [0, 2], [0, 1]]
1075 @end example
1076
1077 @opencatbox
1078 @category{Package graphs}
1079 @category{Package graphs - properties}
1080 @closecatbox
1081 @end deffn
1082
1083 @deffn {関数} get_edge_weight (@var{e}, @var{gr})
1084 @deffnx {関数} get_edge_weight (@var{e}, @var{gr}, @var{ifnot})
1085 グラフ @var{gr}の辺 @var{e}の重みを返します。
1086
1087 もし辺に割り当てられた重みがないなら、
1088 関数は1を返します。
1089 もし辺がグラフの中に存在しないなら、
1090 関数はエラーをシグナルするか、オプション引数 @var{ifnot}を返します。
1091
1092 例:
1093 @c ===beg===
1094 @c load ("graphs")$
1095 @c c5 : cycle_graph(5)$
1096 @c get_edge_weight([1,2], c5);
1097 @c set_edge_weight([1,2], 2.0, c5);
1098 @c get_edge_weight([1,2], c5);
1099 @c ===end===
1100 @example
1101 (%i1) load ("graphs")$
1102 (%i2) c5 : cycle_graph(5)$
1103 (%i3) get_edge_weight([1,2], c5);
1104 (%o3)                           1
1105 (%i4) set_edge_weight([1,2], 2.0, c5);
1106 (%o4)                         done
1107 (%i5) get_edge_weight([1,2], c5);
1108 (%o5)                          2.0
1109 @end example
1110
1111 @opencatbox
1112 @category{Package graphs}
1113 @category{Package graphs - properties}
1114 @closecatbox
1115 @end deffn
1116
1117 @deffn {関数} get_vertex_label (@var{v}, @var{gr})
1118 グラフ @var{gr}の頂点 @var{v}のラベルを返します。
1119
1120 例:
1121 @c ===beg===
1122 @c load ("graphs")$
1123 @c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
1124 @c get_vertex_label(0, g);
1125 @c ===end===
1126 @example
1127 (%i1) load ("graphs")$
1128 (%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
1129 (%i3) get_vertex_label(0, g);
1130 (%o3)                         Zero
1131 @end example
1132
1133 @opencatbox
1134 @category{Package graphs}
1135 @category{Package graphs - properties}
1136 @closecatbox
1137 @end deffn
1138
1139 @deffn {関数} graph_charpoly (@var{gr}, @var{x})
1140 グラフ @var{gr}の(変数 @var{x}に関する)特性多項式を返します。
1141
1142 例:
1143 @c ===beg===
1144 @c load ("graphs")$
1145 @c p : petersen_graph()$
1146 @c graph_charpoly(p, x), factor;
1147 @c ===end===
1148 @example
1149 (%i1) load ("graphs")$
1150 (%i2) p : petersen_graph()$
1151 (%i3) graph_charpoly(p, x), factor;
1152                                    5        4
1153 (%o3)               (x - 3) (x - 1)  (x + 2)
1154 @end example
1155
1156 @opencatbox
1157 @category{Package graphs}
1158 @category{Package graphs - properties}
1159 @closecatbox
1160 @end deffn
1161
1162 @deffn {関数} graph_center (@var{gr})
1163 グラフ @var{gr}の中心を返します。
1164
1165 例:
1166 @c ===beg===
1167 @c load ("graphs")$
1168 @c g : grid_graph(5,5)$
1169 @c graph_center(g);
1170 @c ===end===
1171 @example
1172 (%i1) load ("graphs")$
1173 (%i2) g : grid_graph(5,5)$
1174 (%i3) graph_center(g);
1175 (%o3)                         [12]
1176 @end example
1177
1178 @opencatbox
1179 @category{Package graphs}
1180 @category{Package graphs - properties}
1181 @closecatbox
1182 @end deffn
1183
1184 @deffn {関数} graph_eigenvalues (@var{gr})
1185 グラフ @var{gr}の固有値を返します。
1186 関数は
1187 maxima @code{eigenvalue}関数と同じフォーマットで固有値を返します。
1188
1189 例:
1190 @c ===beg===
1191 @c load ("graphs")$
1192 @c p : petersen_graph()$
1193 @c graph_eigenvalues(p);
1194 @c ===end===
1195 @example
1196 (%i1) load ("graphs")$
1197 (%i2) p : petersen_graph()$
1198 (%i3) graph_eigenvalues(p);
1199 (%o3)               [[3, - 2, 1], [1, 4, 5]]
1200 @end example
1201
1202 @opencatbox
1203 @category{Package graphs}
1204 @category{Package graphs - properties}
1205 @closecatbox
1206 @end deffn
1207
1208 @deffn {関数} graph_periphery (@var{gr})
1209 グラフ @var{gr}の外周を返します。
1210
1211 例:
1212 @c ===beg===
1213 @c load ("graphs")$
1214 @c g : grid_graph(5,5)$
1215 @c graph_periphery(g);
1216 @c ===end===
1217 @example
1218 (%i1) load ("graphs")$
1219 (%i2) g : grid_graph(5,5)$
1220 (%i3) graph_periphery(g);
1221 (%o3)                    [24, 20, 4, 0]
1222 @end example
1223
1224 @opencatbox
1225 @category{Package graphs}
1226 @category{Package graphs - properties}
1227 @closecatbox
1228 @end deffn
1229
1230 @deffn {関数} graph_size (@var{gr})
1231 グラフ @var{gr}の辺の数を返します。
1232
1233 例:
1234 @c ===beg===
1235 @c load ("graphs")$
1236 @c p : petersen_graph()$
1237 @c graph_size(p);
1238 @c ===end===
1239 @example
1240 (%i1) load ("graphs")$
1241 (%i2) p : petersen_graph()$
1242 (%i3) graph_size(p);
1243 (%o3)                          15
1244 @end example
1245
1246 @opencatbox
1247 @category{Package graphs}
1248 @category{Package graphs - properties}
1249 @closecatbox
1250 @end deffn
1251
1252 @deffn {関数} graph_order (@var{gr})
1253 グラフ @var{gr}の頂点の数を返します。
1254
1255 例:
1256 @c ===beg===
1257 @c load ("graphs")$
1258 @c p : petersen_graph()$
1259 @c graph_order(p);
1260 @c ===end===
1261 @example
1262 (%i1) load ("graphs")$
1263 (%i2) p : petersen_graph()$
1264 (%i3) graph_order(p);
1265 (%o3)                          10
1266 @end example
1267
1268 @opencatbox
1269 @category{Package graphs}
1270 @category{Package graphs - properties}
1271 @closecatbox
1272 @end deffn
1273
1274 @deffn {関数} girth (@var{gr})
1275 @var{gr}の最短閉路の長さを返します。
1276
1277 例:
1278 @c ===beg===
1279 @c load ("graphs")$
1280 @c g : heawood_graph()$
1281 @c girth(g);
1282 @c ===end===
1283 @example
1284 (%i1) load ("graphs")$
1285 (%i2) g : heawood_graph()$
1286 (%i3) girth(g);
1287 (%o3)                           6
1288 @end example
1289
1290 @opencatbox
1291 @category{Package graphs}
1292 @category{Package graphs - properties}
1293 @closecatbox
1294 @end deffn
1295
1296 @deffn {関数} hamilton_cycle (@var{gr})
1297 グラフ @var{gr}のHamilton閉路を返します。
1298 もし @var{gr}がハミルトニアンでないなら、空のリストを返します。
1299
1300 例:
1301 @c ===beg===
1302 @c load ("graphs")$
1303 @c c : cube_graph(3)$
1304 @c hc : hamilton_cycle(c);
1305 @c draw_graph(c, show_edges=vertices_to_cycle(hc))$
1306 @c ===end===
1307 @example
1308 (%i1) load ("graphs")$
1309 (%i2) c : cube_graph(3)$
1310 (%i3) hc : hamilton_cycle(c);
1311 (%o3)              [7, 3, 2, 6, 4, 0, 1, 5, 7]
1312 (%i4) draw_graph(c, show_edges=vertices_to_cycle(hc))$
1313 @end example
1314
1315 @opencatbox
1316 @category{Package graphs}
1317 @category{Package graphs - properties}
1318 @closecatbox
1319 @end deffn
1320
1321 @ifhtml
1322 @image{@value{figuresfolder}/graphs03,6cm}
1323 @end ifhtml
1324
1325 @deffn {関数} hamilton_path (@var{gr})
1326 グラフ @var{gr}のHamilton経路を返します。
1327 もし @var{gr}がHamilton経路を持たないなら、空のリストを返します。
1328
1329 例:
1330 @c ===beg===
1331 @c load ("graphs")$
1332 @c p : petersen_graph()$
1333 @c hp : hamilton_path(p);
1334 @c draw_graph(p, show_edges=vertices_to_path(hp))$
1335 @c ===end===
1336 @example
1337 (%i1) load ("graphs")$
1338 (%i2) p : petersen_graph()$
1339 (%i3) hp : hamilton_path(p);
1340 (%o3)            [0, 5, 7, 2, 1, 6, 8, 3, 4, 9]
1341 (%i4) draw_graph(p, show_edges=vertices_to_path(hp))$
1342 @end example
1343
1344 @opencatbox
1345 @category{Package graphs}
1346 @category{Package graphs - properties}
1347 @closecatbox
1348 @end deffn
1349
1350 @ifhtml
1351 @image{@value{figuresfolder}/graphs04,6cm}
1352 @end ifhtml
1353
1354 @deffn {関数} isomorphism (@var{gr1}, @var{gr2})
1355
1356 グラフ/有向グラフ @var{gr1}と @var{gr2}の間の同型写像を返します。
1357 もし @var{gr1}と @var{gr2}が同型でないなら、空のリストを返します。
1358
1359 例:
1360 @c ===beg===
1361 @c load ("graphs")$
1362 @c clk5:complement_graph(line_graph(complete_graph(5)))$
1363 @c isomorphism(clk5, petersen_graph());
1364 @c ===end===
1365 @example
1366 (%i1) load ("graphs")$
1367 (%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
1368 (%i3) isomorphism(clk5, petersen_graph());
1369 (%o3) [9 -> 0, 2 -> 1, 6 -> 2, 5 -> 3, 0 -> 4, 1 -> 5, 3 -> 6,
1370                                           4 -> 7, 7 -> 8, 8 -> 9]
1371 @end example
1372
1373 @opencatbox
1374 @category{Package graphs}
1375 @category{Package graphs - properties}
1376 @closecatbox
1377 @end deffn
1378
1379 @deffn {関数} in_neighbors (@var{v}, @var{gr})
1380 有向グラフ @var{gr}の頂点 @var{v}の内隣接点のリストを返します。
1381
1382 例:
1383 @c ===beg===
1384 @c load ("graphs")$
1385 @c p : path_digraph(3)$
1386 @c in_neighbors(2, p);
1387 @c out_neighbors(2, p);
1388 @c ===end===
1389 @example
1390 (%i1) load ("graphs")$
1391 (%i2) p : path_digraph(3)$
1392 (%i3) in_neighbors(2, p);
1393 (%o3)                          [1]
1394 (%i4) out_neighbors(2, p);
1395 (%o4)                          []
1396 @end example
1397
1398 @opencatbox
1399 @category{Package graphs}
1400 @category{Package graphs - properties}
1401 @closecatbox
1402 @end deffn
1403
1404 @deffn {関数} is_biconnected (@var{gr})
1405 もし @var{gr}が2連結なら @code{true}を、
1406 そうでないなら、 @code{false}を返します。
1407
1408 例:
1409 @c ===beg===
1410 @c load ("graphs")$
1411 @c is_biconnected(cycle_graph(5));
1412 @c is_biconnected(path_graph(5));
1413 @c ===end===
1414 @example
1415 (%i1) load ("graphs")$
1416 (%i2) is_biconnected(cycle_graph(5));
1417 (%o2)                         true
1418 (%i3) is_biconnected(path_graph(5));
1419 (%o3)                         false
1420 @end example
1421
1422 @opencatbox
1423 @category{Package graphs}
1424 @category{Package graphs - properties}
1425 @closecatbox
1426 @end deffn
1427
1428 @deffn {関数} is_bipartite (@var{gr})
1429 もし @var{gr}が2部(2彩色)なら @code{true}を、
1430 そうでないなら、 @code{false}を返します。
1431
1432 例:
1433 @c ===beg===
1434 @c load ("graphs")$
1435 @c is_bipartite(petersen_graph());
1436 @c is_bipartite(heawood_graph());
1437 @c ===end===
1438 @example
1439 (%i1) load ("graphs")$
1440 (%i2) is_bipartite(petersen_graph());
1441 (%o2)                         false
1442 (%i3) is_bipartite(heawood_graph());
1443 (%o3)                         true
1444 @end example
1445
1446 @opencatbox
1447 @category{Package graphs}
1448 @category{Package graphs - properties}
1449 @closecatbox
1450 @end deffn
1451
1452 @deffn {関数} is_connected (@var{gr})
1453 もしグラフ @var{gr}が連結なら @code{true}を、
1454 そうでないなら @code{false}を返します。
1455
1456 例:
1457 @c ===beg===
1458 @c load ("graphs")$
1459 @c is_connected(graph_union(cycle_graph(4), path_graph(3)));
1460 @c ===end===
1461 @example
1462 (%i1) load ("graphs")$
1463 (%i2) is_connected(graph_union(cycle_graph(4), path_graph(3)));
1464 (%o2)                         false
1465 @end example
1466
1467 @opencatbox
1468 @category{Package graphs}
1469 @category{Package graphs - properties}
1470 @closecatbox
1471 @end deffn
1472
1473 @deffn {関数} is_digraph (@var{gr})
1474 もし @var{gr}が有向グラフなら @code{true}を、
1475 そうでないなら @code{false}を返します。
1476
1477 例:
1478 @c ===beg===
1479 @c load ("graphs")$
1480 @c is_digraph(path_graph(5));
1481 @c is_digraph(path_digraph(5));
1482 @c ===end===
1483 @example
1484 (%i1) load ("graphs")$
1485 (%i2) is_digraph(path_graph(5));
1486 (%o2)                         false
1487 (%i3) is_digraph(path_digraph(5));
1488 (%o3)                         true
1489 @end example
1490
1491 @opencatbox
1492 @category{Package graphs}
1493 @category{Package graphs - properties}
1494 @closecatbox
1495 @end deffn
1496
1497 @deffn {関数} is_edge_in_graph (@var{e}, @var{gr})
1498 もし @var{e}が(有向)グラフ @var{g}の辺(弧)なら @code{true}を、
1499 そうでないなら @code{false}を返します。
1500
1501 例:
1502 @c ===beg===
1503 @c load ("graphs")$
1504 @c c4 : cycle_graph(4)$
1505 @c is_edge_in_graph([2,3], c4);
1506 @c is_edge_in_graph([3,2], c4);
1507 @c is_edge_in_graph([2,4], c4);
1508 @c is_edge_in_graph([3,2], cycle_digraph(4));
1509 @c ===end===
1510 @example
1511 (%i1) load ("graphs")$
1512 (%i2) c4 : cycle_graph(4)$
1513 (%i3) is_edge_in_graph([2,3], c4);
1514 (%o3)                         true
1515 (%i4) is_edge_in_graph([3,2], c4);
1516 (%o4)                         true
1517 (%i5) is_edge_in_graph([2,4], c4);
1518 (%o5)                         false
1519 (%i6) is_edge_in_graph([3,2], cycle_digraph(4));
1520 (%o6)                         false
1521 @end example
1522
1523 @opencatbox
1524 @category{Package graphs}
1525 @category{Package graphs - properties}
1526 @closecatbox
1527 @end deffn
1528
1529 @deffn {関数} is_graph (@var{gr})
1530 もし @var{gr}がグラフなら @code{true}を、
1531 そうでないなら @code{false}を返します。
1532
1533 例:
1534 @c ===beg===
1535 @c load ("graphs")$
1536 @c is_graph(path_graph(5));
1537 @c is_graph(path_digraph(5));
1538 @c ===end===
1539 @example
1540 (%i1) load ("graphs")$
1541 (%i2) is_graph(path_graph(5));
1542 (%o2)                         true
1543 (%i3) is_graph(path_digraph(5));
1544 (%o3)                         false
1545 @end example
1546
1547 @opencatbox
1548 @category{Package graphs}
1549 @category{Package graphs - properties}
1550 @closecatbox
1551 @end deffn
1552
1553 @deffn {関数} is_graph_or_digraph (@var{gr})
1554 もし @var{gr}がグラフか有向グラフなら @code{true}を、
1555 そうでないなら @code{false}を返します。
1556
1557 例:
1558 @c ===beg===
1559 @c load ("graphs")$
1560 @c is_graph_or_digraph(path_graph(5));
1561 @c is_graph_or_digraph(path_digraph(5));
1562 @c ===end===
1563 @example
1564 (%i1) load ("graphs")$
1565 (%i2) is_graph_or_digraph(path_graph(5));
1566 (%o2)                         true
1567 (%i3) is_graph_or_digraph(path_digraph(5));
1568 (%o3)                         true
1569 @end example
1570
1571 @opencatbox
1572 @category{Package graphs}
1573 @category{Package graphs - properties}
1574 @closecatbox
1575 @end deffn
1576
1577 @deffn {関数} is_isomorphic (@var{gr1}, @var{gr2})
1578
1579 もし グラフ/有向グラフ @var{gr1}と @var{gr2}が同型なら @code{true}を、
1580 そうでないなら @code{false}を返します。
1581
1582 @code{isomorphism}も参照してください。
1583
1584 例:
1585 @c ===beg===
1586 @c load ("graphs")$
1587 @c clk5:complement_graph(line_graph(complete_graph(5)))$
1588 @c is_isomorphic(clk5, petersen_graph());
1589 @c ===end===
1590 @example
1591 (%i1) load ("graphs")$
1592 (%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
1593 (%i3) is_isomorphic(clk5, petersen_graph());
1594 (%o3)                         true
1595 @end example
1596
1597 @opencatbox
1598 @category{Package graphs}
1599 @category{Package graphs - properties}
1600 @closecatbox
1601 @end deffn
1602
1603 @deffn {関数} is_planar (@var{gr})
1604
1605 もし @var{gr}が平面グラフなら @code{true}を、
1606 そうでないなら @code{false}を返します。
1607
1608 使われているアルゴリズムはDemoucronのアルゴリズムです。
1609 これは二次時間アルゴリズムです。
1610
1611 例:
1612 @c ===beg===
1613 @c load ("graphs")$
1614 @c is_planar(dodecahedron_graph());
1615 @c is_planar(petersen_graph());
1616 @c is_planar(petersen_graph(10,2));
1617 @c ===end===
1618 @example
1619 (%i1) load ("graphs")$
1620 (%i2) is_planar(dodecahedron_graph());
1621 (%o2)                         true
1622 (%i3) is_planar(petersen_graph());
1623 (%o3)                         false
1624 (%i4) is_planar(petersen_graph(10,2));
1625 (%o4)                         true
1626 @end example
1627
1628 @opencatbox
1629 @category{Package graphs}
1630 @category{Package graphs - properties}
1631 @closecatbox
1632 @end deffn
1633
1634 @deffn {関数} is_sconnected (@var{gr})
1635 もし有向グラフ @var{gr}が強連結なら @code{true}を、
1636 そうでないなら @code{false}を返します。
1637
1638 例:
1639 @c ===beg===
1640 @c load ("graphs")$
1641 @c is_sconnected(cycle_digraph(5));
1642 @c is_sconnected(path_digraph(5));
1643 @c ===end===
1644 @example
1645 (%i1) load ("graphs")$
1646 (%i2) is_sconnected(cycle_digraph(5));
1647 (%o2)                         true
1648 (%i3) is_sconnected(path_digraph(5));
1649 (%o3)                         false
1650 @end example
1651
1652 @opencatbox
1653 @category{Package graphs}
1654 @category{Package graphs - properties}
1655 @closecatbox
1656 @end deffn
1657
1658 @deffn {関数} is_vertex_in_graph (@var{v}, @var{gr})
1659 もし @var{v}がグラフ @var{g}の頂点なら @code{true}を、
1660 そうでないなら @code{false}を返します。
1661
1662 例:
1663 @c ===beg===
1664 @c load ("graphs")$
1665 @c c4 : cycle_graph(4)$
1666 @c is_vertex_in_graph(0, c4);
1667 @c is_vertex_in_graph(6, c4);
1668 @c ===end===
1669 @example
1670 (%i1) load ("graphs")$
1671 (%i2) c4 : cycle_graph(4)$
1672 (%i3) is_vertex_in_graph(0, c4);
1673 (%o3)                         true
1674 (%i4) is_vertex_in_graph(6, c4);
1675 (%o4)                         false
1676 @end example
1677
1678 @opencatbox
1679 @category{Package graphs}
1680 @category{Package graphs - properties}
1681 @closecatbox
1682 @end deffn
1683
1684 @deffn {関数} is_tree (@var{gr})
1685 もし @var{gr}が木なら @code{true}を、
1686 そうでないなら @code{false}を返します。
1687
1688 例:
1689 @c ===beg===
1690 @c load ("graphs")$
1691 @c is_tree(random_tree(4));
1692 @c is_tree(graph_union(random_tree(4), random_tree(5)));
1693 @c ===end===
1694 @example
1695 (%i1) load ("graphs")$
1696 (%i2) is_tree(random_tree(4));
1697 (%o2)                         true
1698 (%i3) is_tree(graph_union(random_tree(4), random_tree(5)));
1699 (%o3)                         false
1700 @end example
1701
1702 @opencatbox
1703 @category{Package graphs}
1704 @category{Package graphs - properties}
1705 @closecatbox
1706 @end deffn
1707
1708 @deffn {関数} laplacian_matrix (@var{gr})
1709 グラフ @var{gr}のLaplace行列を返します。
1710
1711 例:
1712 @c ===beg===
1713 @c load ("graphs")$
1714 @c laplacian_matrix(cycle_graph(5));
1715 @c ===end===
1716 @example
1717 (%i1) load ("graphs")$
1718 (%i2) laplacian_matrix(cycle_graph(5));
1719                    [  2   - 1   0    0   - 1 ]
1720                    [                         ]
1721                    [ - 1   2   - 1   0    0  ]
1722                    [                         ]
1723 (%o2)              [  0   - 1   2   - 1   0  ]
1724                    [                         ]
1725                    [  0    0   - 1   2   - 1 ]
1726                    [                         ]
1727                    [ - 1   0    0   - 1   2  ]
1728 @end example
1729
1730 @opencatbox
1731 @category{Package graphs}
1732 @category{Package graphs - properties}
1733 @closecatbox
1734 @end deffn
1735
1736 @deffn {関数} max_clique (@var{gr})
1737 グラフ @var{gr}の最大クリークを返します。
1738
1739 例:
1740 @c ===beg===
1741 @c load ("graphs")$
1742 @c g : random_graph(100, 0.5)$
1743 @c max_clique(g);
1744 @c ===end===
1745 @example
1746 (%i1) load ("graphs")$
1747 (%i2) g : random_graph(100, 0.5)$
1748 (%i3) max_clique(g);
1749 (%o3)          [6, 12, 31, 36, 52, 59, 62, 63, 80]
1750 @end example
1751
1752 @opencatbox
1753 @category{Package graphs}
1754 @category{Package graphs - properties}
1755 @closecatbox
1756 @end deffn
1757
1758 @deffn {関数} max_degree (@var{gr})
1759 グラフ @var{gr}の頂点の最大次数と最大次数の頂点を返します。
1760
1761 例:
1762 @c ===beg===
1763 @c load ("graphs")$
1764 @c g : random_graph(100, 0.02)$
1765 @c max_degree(g);
1766 @c vertex_degree(95, g);
1767 @c ===end===
1768 @example
1769 (%i1) load ("graphs")$
1770 (%i2) g : random_graph(100, 0.02)$
1771 (%i3) max_degree(g);
1772 (%o3)                        [6, 79]
1773 (%i4) vertex_degree(95, g);
1774 (%o4)                           2
1775 @end example
1776
1777 @opencatbox
1778 @category{Package graphs}
1779 @category{Package graphs - properties}
1780 @closecatbox
1781 @end deffn
1782
1783 @deffn {関数} max_flow (@var{net}, @var{s}, @var{t})
1784 ソース @var{s}とシンク @var{t}を持ち
1785 ネットワーク @var{net}を通る最大フローを返します。
1786
1787 関数は最大フローの値と
1788 最適フローで弧の重みを表現するリストを返します。
1789
1790 例:
1791 @c ===beg===
1792 @c load ("graphs")$
1793 @c net : create_graph(
1794 @c   [1,2,3,4,5,6],
1795 @c   [[[1,2], 1.0],
1796 @c    [[1,3], 0.3],
1797 @c    [[2,4], 0.2],
1798 @c    [[2,5], 0.3],
1799 @c    [[3,4], 0.1],
1800 @c    [[3,5], 0.1],
1801 @c    [[4,6], 1.0],
1802 @c    [[5,6], 1.0]],
1803 @c   directed=true)$
1804 @c [flow_value, flow] : max_flow(net, 1, 6);
1805 @c fl : 0$
1806 @c for u in out_neighbors(1, net)
1807 @c      do fl : fl + assoc([1, u], flow)$
1808 @c fl;
1809 @c ===end===
1810 @example
1811 (%i1) load ("graphs")$
1812 (%i2) net : create_graph(
1813   [1,2,3,4,5,6],
1814   [[[1,2], 1.0],
1815    [[1,3], 0.3],
1816    [[2,4], 0.2],
1817    [[2,5], 0.3],
1818    [[3,4], 0.1],
1819    [[3,5], 0.1],
1820    [[4,6], 1.0],
1821    [[5,6], 1.0]],
1822   directed=true)$
1823 (%i3) [flow_value, flow] : max_flow(net, 1, 6);
1824 (%o3) [0.7, [[[1, 2], 0.5], [[1, 3], 0.2], [[2, 4], 0.2],
1825 [[2, 5], 0.3], [[3, 4], 0.1], [[3, 5], 0.1], [[4, 6], 0.3],
1826 [[5, 6], 0.4]]]
1827 (%i4) fl : 0$
1828 (%i5) for u in out_neighbors(1, net)
1829      do fl : fl + assoc([1, u], flow)$
1830 (%i6) fl;
1831 (%o6)                          0.7
1832 @end example
1833
1834 @opencatbox
1835 @category{Package graphs}
1836 @category{Package graphs - properties}
1837 @closecatbox
1838 @end deffn
1839
1840 @deffn {関数} max_independent_set (@var{gr})
1841 グラフ @var{gr}の最大独立集合を返します。
1842
1843 例:
1844 @c ===beg===
1845 @c load ("graphs")$
1846 @c d : dodecahedron_graph()$
1847 @c mi : max_independent_set(d);
1848 @c draw_graph(d, show_vertices=mi)$
1849 @c ===end===
1850 @example
1851 (%i1) load ("graphs")$
1852 (%i2) d : dodecahedron_graph()$
1853 (%i3) mi : max_independent_set(d);
1854 (%o3)             [0, 3, 5, 9, 10, 11, 18, 19]
1855 (%i4) draw_graph(d, show_vertices=mi)$
1856 @end example
1857
1858 @opencatbox
1859 @category{Package graphs}
1860 @category{Package graphs - properties}
1861 @closecatbox
1862 @end deffn
1863
1864 @ifhtml
1865 @image{@value{figuresfolder}/graphs05,6cm}
1866 @end ifhtml
1867
1868 @deffn {関数} max_matching (@var{gr})
1869 グラフ @var{gr}の最大マッチングを返します。
1870
1871 例:
1872 @c ===beg===
1873 @c load ("graphs")$
1874 @c d : dodecahedron_graph()$
1875 @c m : max_matching(d);
1876 @c draw_graph(d, show_edges=m)$
1877 @c ===end===
1878 @example
1879 (%i1) load ("graphs")$
1880 (%i2) d : dodecahedron_graph()$
1881 (%i3) m : max_matching(d);
1882 (%o3) [[5, 7], [8, 9], [6, 10], [14, 19], [13, 18], [12, 17],
1883                                [11, 16], [0, 15], [3, 4], [1, 2]]
1884 (%i4) draw_graph(d, show_edges=m)$
1885 @end example
1886
1887 @opencatbox
1888 @category{Package graphs}
1889 @category{Package graphs - properties}
1890 @closecatbox
1891 @end deffn
1892
1893 @ifhtml
1894 @image{@value{figuresfolder}/graphs06,6cm}
1895 @end ifhtml
1896
1897 @deffn {関数} min_degree (@var{gr})
1898 グラフ @var{gr}の頂点の最小次数と最小次数の頂点を返します。
1899
1900 例:
1901 @c ===beg===
1902 @c load ("graphs")$
1903 @c g : random_graph(100, 0.1)$
1904 @c min_degree(g);
1905 @c vertex_degree(21, g);
1906 @c ===end===
1907 @example
1908 (%i1) load ("graphs")$
1909 (%i2) g : random_graph(100, 0.1)$
1910 (%i3) min_degree(g);
1911 (%o3)                        [3, 49]
1912 (%i4) vertex_degree(21, g);
1913 (%o4)                           9
1914 @end example
1915
1916 @opencatbox
1917 @category{Package graphs}
1918 @category{Package graphs - properties}
1919 @closecatbox
1920 @end deffn
1921
1922 @deffn {関数} min_edge_cut (@var{gr})
1923 グラフ @var{gr}の最小切断辺を返します。
1924
1925 @code{edge_connectivity}も参照してください。
1926
1927 @opencatbox
1928 @category{Package graphs}
1929 @category{Package graphs - properties}
1930 @closecatbox
1931 @end deffn
1932
1933 @deffn {関数} min_vertex_cover (@var{gr})
1934 グラフ @var{gr}の最小頂点被覆を返します。
1935
1936 @opencatbox
1937 @category{Package graphs}
1938 @category{Package graphs - properties}
1939 @closecatbox
1940 @end deffn
1941
1942 @deffn {関数} min_vertex_cut (@var{gr})
1943 Returns the minimum vertex cut in the graph
1944 グラフ @var{gr}の最小頂点切断を返します。
1945
1946 @code{vertex_connectivity}も参照してください。
1947
1948 @opencatbox
1949 @category{Package graphs}
1950 @category{Package graphs - properties}
1951 @closecatbox
1952 @end deffn
1953
1954 @deffn {関数} minimum_spanning_tree (@var{gr})
1955 グラフ @var{gr}の最小全域木を返します。
1956
1957 例:
1958 @c ===beg===
1959 @c load ("graphs")$
1960 @c g : graph_product(path_graph(10), path_graph(10))$
1961 @c t : minimum_spanning_tree(g)$
1962 @c draw_graph(g, show_edges=edges(t))$
1963 @c ===end===
1964 @example
1965 (%i1) load ("graphs")$
1966 (%i2) g : graph_product(path_graph(10), path_graph(10))$
1967 (%i3) t : minimum_spanning_tree(g)$
1968 (%i4) draw_graph(g, show_edges=edges(t))$
1969 @end example
1970
1971 @opencatbox
1972 @category{Package graphs}
1973 @category{Package graphs - properties}
1974 @closecatbox
1975 @end deffn
1976
1977 @ifhtml
1978 @image{@value{figuresfolder}/graphs07,6cm}
1979 @end ifhtml
1980
1981 @deffn {関数} neighbors (@var{v}, @var{gr})
1982 グラフ @var{gr}の頂点 @var{v}の隣接点のリストを返します。
1983
1984 例:
1985 @c ===beg===
1986 @c load ("graphs")$
1987 @c p : petersen_graph()$
1988 @c neighbors(3, p);
1989 @c ===end===
1990 @example
1991 (%i1) load ("graphs")$
1992 (%i2) p : petersen_graph()$
1993 (%i3) neighbors(3, p);
1994 (%o3)                       [4, 8, 2]
1995 @end example
1996
1997 @opencatbox
1998 @category{Package graphs}
1999 @category{Package graphs - properties}
2000 @closecatbox
2001 @end deffn
2002
2003 @deffn {関数} odd_girth (@var{gr})
2004 グラフ @var{gr}の最短奇閉路の長さを返します。
2005
2006 例:
2007 @c ===beg===
2008 @c load ("graphs")$
2009 @c g : graph_product(cycle_graph(4), cycle_graph(7))$
2010 @c girth(g);
2011 @c odd_girth(g);
2012 @c ===end===
2013 @example
2014 (%i1) load ("graphs")$
2015 (%i2) g : graph_product(cycle_graph(4), cycle_graph(7))$
2016 (%i3) girth(g);
2017 (%o3)                           4
2018 (%i4) odd_girth(g);
2019 (%o4)                           7
2020 @end example
2021
2022 @opencatbox
2023 @category{Package graphs}
2024 @category{Package graphs - properties}
2025 @closecatbox
2026 @end deffn
2027
2028 @deffn {関数} out_neighbors (@var{v}, @var{gr})
2029 有向グラフ @var{gr}の頂点 @var{v}の外隣接点のリストを返します。
2030
2031 例:
2032 @c ===beg===
2033 @c load ("graphs")$
2034 @c p : path_digraph(3)$
2035 @c in_neighbors(2, p);
2036 @c out_neighbors(2, p);
2037 @c ===end===
2038 @example
2039 (%i1) load ("graphs")$
2040 (%i2) p : path_digraph(3)$
2041 (%i3) in_neighbors(2, p);
2042 (%o3)                          [1]
2043 (%i4) out_neighbors(2, p);
2044 (%o4)                          []
2045 @end example
2046
2047 @opencatbox
2048 @category{Package graphs}
2049 @category{Package graphs - properties}
2050 @closecatbox
2051 @end deffn
2052
2053 @deffn {関数} planar_embedding (@var{gr})
2054
2055 @var{gr}の平面埋め込みでのfacial walkのリストを返します。
2056 もし @var{gr}が平面グラフでないなら @code{false}を返します。
2057
2058 グラフ @var{gr}は2連結でなければいけません。
2059
2060 使われるアルゴリズムはDemoucronのアルゴリズムです。
2061 これは二次時間アルゴリズムです。
2062
2063 例:
2064 @c ===beg===
2065 @c load ("graphs")$
2066 @c planar_embedding(grid_graph(3,3));
2067 @c ===end===
2068 @example
2069 (%i1) load ("graphs")$
2070 (%i2) planar_embedding(grid_graph(3,3));
2071 (%o2) [[3, 6, 7, 8, 5, 2, 1, 0], [4, 3, 0, 1], [3, 4, 7, 6],
2072                                       [8, 7, 4, 5], [1, 2, 5, 4]]
2073 @end example
2074
2075 @opencatbox
2076 @category{Package graphs}
2077 @category{Package graphs - properties}
2078 @closecatbox
2079 @end deffn
2080
2081 @deffn {関数} print_graph (@var{gr})
2082 グラフ @var{gr}についてのある情報を印字します。
2083
2084 例:
2085 @c ===beg===
2086 @c load ("graphs")$
2087 @c c5 : cycle_graph(5)$
2088 @c print_graph(c5)$
2089 @c dc5 : cycle_digraph(5)$
2090 @c print_graph(dc5)$
2091 @c out_neighbors(0, dc5);
2092 @c ===end===
2093 @example
2094 (%i1) load ("graphs")$
2095 (%i2) c5 : cycle_graph(5)$
2096 (%i3) print_graph(c5)$
2097 Graph on 5 vertices with 5 edges.
2098 Adjacencies:
2099   4 :  0  3
2100   3 :  4  2
2101   2 :  3  1
2102   1 :  2  0
2103   0 :  4  1
2104 (%i4) dc5 : cycle_digraph(5)$
2105 (%i5) print_graph(dc5)$
2106 Digraph on 5 vertices with 5 arcs.
2107 Adjacencies:
2108   4 :  0
2109   3 :  4
2110   2 :  3
2111   1 :  2
2112   0 :  1
2113 (%i6) out_neighbors(0, dc5);
2114 (%o6)                          [1]
2115 @end example
2116
2117 @opencatbox
2118 @category{Package graphs}
2119 @closecatbox
2120 @end deffn
2121
2122 @deffn {関数} radius (@var{gr})
2123 グラフ @var{gr}の半径を返します。
2124
2125 例:
2126 @c ===beg===
2127 @c load ("graphs")$
2128 @c radius(dodecahedron_graph());
2129 @c ===end===
2130 @example
2131 (%i1) load ("graphs")$
2132 (%i2) radius(dodecahedron_graph());
2133 (%o2)                           5
2134 @end example
2135
2136 @opencatbox
2137 @category{Package graphs}
2138 @category{Package graphs - properties}
2139 @closecatbox
2140 @end deffn
2141
2142 @deffn {関数} set_edge_weight (@var{e}, @var{w}, @var{gr})
2143 グラフ @var{gr}の辺 @var{e}に重み @var{w}を割り当てます。
2144
2145 例:
2146 @c ===beg===
2147 @c load ("graphs")$
2148 @c g : create_graph([1, 2], [[[1,2], 1.2]])$
2149 @c get_edge_weight([1,2], g);
2150 @c set_edge_weight([1,2], 2.1, g);
2151 @c get_edge_weight([1,2], g);
2152 @c ===end===
2153 @example
2154 (%i1) load ("graphs")$
2155 (%i2) g : create_graph([1, 2], [[[1,2], 1.2]])$
2156 (%i3) get_edge_weight([1,2], g);
2157 (%o3)                          1.2
2158 (%i4) set_edge_weight([1,2], 2.1, g);
2159 (%o4)                         done
2160 (%i5) get_edge_weight([1,2], g);
2161 (%o5)                          2.1
2162 @end example
2163
2164 @opencatbox
2165 @category{Package graphs}
2166 @category{Package graphs - properties}
2167 @closecatbox
2168 @end deffn
2169
2170 @deffn {関数} set_vertex_label (@var{v}, @var{l}, @var{gr})
2171 グラフ @var{gr}の頂点 @var{v}にラベル @var{l}を割り当てます。
2172
2173
2174 例:
2175 @c ===beg===
2176 @c load ("graphs")$
2177 @c g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
2178 @c get_vertex_label(1, g);
2179 @c set_vertex_label(1, "oNE", g);
2180 @c get_vertex_label(1, g);
2181 @c ===end===
2182 @example
2183 (%i1) load ("graphs")$
2184 (%i2) g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
2185 (%i3) get_vertex_label(1, g);
2186 (%o3)                          One
2187 (%i4) set_vertex_label(1, "oNE", g);
2188 (%o4)                         done
2189 (%i5) get_vertex_label(1, g);
2190 (%o5)                          oNE
2191 @end example
2192
2193 @opencatbox
2194 @category{Package graphs}
2195 @category{Package graphs - properties}
2196 @closecatbox
2197 @end deffn
2198
2199 @deffn {関数} shortest_path (@var{u}, @var{v}, @var{gr})
2200 グラフ @var{gr}の @var{u}から @var{v}までの最短経路を返します。
2201
2202 例:
2203 @c ===beg===
2204 @c load ("graphs")$
2205 @c d : dodecahedron_graph()$
2206 @c path : shortest_path(0, 7, d);
2207 @c draw_graph(d, show_edges=vertices_to_path(path))$
2208 @c ===end===
2209 @example
2210 (%i1) load ("graphs")$
2211 (%i2) d : dodecahedron_graph()$
2212 (%i3) path : shortest_path(0, 7, d);
2213 (%o3)                   [0, 1, 19, 13, 7]
2214 (%i4) draw_graph(d, show_edges=vertices_to_path(path))$
2215 @end example
2216
2217 @opencatbox
2218 @category{Package graphs}
2219 @category{Package graphs - properties}
2220 @closecatbox
2221 @end deffn
2222
2223 @ifhtml
2224 @image{@value{figuresfolder}/graphs08,6cm}
2225 @end ifhtml
2226
2227 @deffn {関数} shortest_weighted_path (@var{u}, @var{v}, @var{gr})
2228 グラフ @var{gr}の @var{u}から @var{v}までの最短重み付き経路とその長さを返します。
2229
2230 重み付き経路の長さは経路内の辺の辺重みの和です。
2231 もし辺に重みがないなら、辺はデフォルト重み1を持ちます。
2232
2233 例:
2234
2235 @c ===beg===
2236 @c load ("graphs")$
2237 @c g: petersen_graph(20, 2)$
2238 @c for e in edges(g) do set_edge_weight(e, random(1.0), g)$
2239 @c shortest_weighted_path(0, 10, g);
2240 @c ===end===
2241 @example
2242 (%i1) load ("graphs")$
2243 (%i2) g: petersen_graph(20, 2)$
2244 (%i3) for e in edges(g) do set_edge_weight(e, random(1.0), g)$
2245 (%i4) shortest_weighted_path(0, 10, g);
2246 (%o4) [2.575143920268482, [0, 20, 38, 36, 34, 32, 30, 10]]
2247 @end example
2248
2249 @opencatbox
2250 @category{Package graphs}
2251 @category{Package graphs - properties}
2252 @closecatbox
2253 @end deffn
2254
2255 @deffn {関数} strong_components (@var{gr})
2256 有向グラフ @var{gr}の強成分を返します。
2257
2258 例:
2259 @c ===beg===
2260 @c load ("graphs")$
2261 @c t : random_tournament(4)$
2262 @c strong_components(t);
2263 @c vertex_out_degree(3, t);
2264 @c ===end===
2265 @example
2266 (%i1) load ("graphs")$
2267 (%i2) t : random_tournament(4)$
2268 (%i3) strong_components(t);
2269 (%o3)                 [[1], [0], [2], [3]]
2270 (%i4) vertex_out_degree(3, t);
2271 (%o4)                           3
2272 @end example
2273
2274 @opencatbox
2275 @category{Package graphs}
2276 @category{Package graphs - properties}
2277 @closecatbox
2278 @end deffn
2279
2280 @deffn {関数} topological_sort (@var{dag})
2281
2282 Returns a topological sorting of the vertices of a directed graph
2283 有向グラフ @var{dag}の頂点のトポロジカルソートを返します。
2284 もし @var{dag}が有向無閉路グラフなら空のリストを返します。
2285
2286 例:
2287 @c ===beg===
2288 @c load ("graphs")$
2289 @c g:create_graph(
2290 @c          [1,2,3,4,5],
2291 @c          [
2292 @c           [1,2], [2,5], [5,3],
2293 @c           [5,4], [3,4], [1,3]
2294 @c          ],
2295 @c          directed=true)$
2296 @c topological_sort(g);
2297 @c ===end===
2298 @example
2299 (%i1) load ("graphs")$
2300 (%i2) g:create_graph(
2301          [1,2,3,4,5],
2302          [
2303           [1,2], [2,5], [5,3],
2304           [5,4], [3,4], [1,3]
2305          ],
2306          directed=true)$
2307 (%i3) topological_sort(g);
2308 (%o3)                    [1, 2, 5, 3, 4]
2309 @end example
2310
2311 @opencatbox
2312 @category{Package graphs}
2313 @category{Package graphs - properties}
2314 @closecatbox
2315 @end deffn
2316
2317 @deffn {関数} vertex_connectivity (@var{g})
2318 グラフ @var{g}の頂点連結性を返します。
2319
2320 @code{min_vertex_cut}も参照してください。
2321
2322 @opencatbox
2323 @category{Package graphs}
2324 @category{Package graphs - properties}
2325 @closecatbox
2326 @end deffn
2327
2328 @deffn {関数} vertex_degree (@var{v}, @var{gr})
2329 グラフ @var{gr}の頂点 @var{v}の次数を返します。
2330
2331 @opencatbox
2332 @category{Package graphs}
2333 @category{Package graphs - properties}
2334 @closecatbox
2335 @end deffn
2336
2337 @deffn {関数} vertex_distance (@var{u}, @var{v}, @var{gr})
2338 (有向)グラフ @var{gr}の @var{u}と @var{v}の間の最短経路の長さを返します。
2339
2340 例:
2341 @c ===beg===
2342 @c load ("graphs")$
2343 @c d : dodecahedron_graph()$
2344 @c vertex_distance(0, 7, d);
2345 @c shortest_path(0, 7, d);
2346 @c ===end===
2347 @example
2348 (%i1) load ("graphs")$
2349 (%i2) d : dodecahedron_graph()$
2350 (%i3) vertex_distance(0, 7, d);
2351 (%o3)                           4
2352 (%i4) shortest_path(0, 7, d);
2353 (%o4)                   [0, 1, 19, 13, 7]
2354 @end example
2355
2356 @opencatbox
2357 @category{Package graphs}
2358 @category{Package graphs - properties}
2359 @closecatbox
2360 @end deffn
2361
2362 @deffn {関数} vertex_eccentricity (@var{v}, @var{gr})
2363
2364 グラフ @var{gr}の頂点 @var{v}の離心率を返します。
2365
2366 例:
2367 @c ===beg===
2368 @c load ("graphs")$
2369 @c g:cycle_graph(7)$
2370 @c vertex_eccentricity(0, g);
2371 @c ===end===
2372 @example
2373 (%i1) load ("graphs")$
2374 (%i2) g:cycle_graph(7)$
2375 (%i3) vertex_eccentricity(0, g);
2376 (%o3)                           3
2377 @end example
2378
2379 @opencatbox
2380 @category{Package graphs}
2381 @category{Package graphs - properties}
2382 @closecatbox
2383 @end deffn
2384
2385 @deffn {関数} vertex_in_degree (@var{v}, @var{gr})
2386 有向グラフ @var{gr}の頂点 @var{v}の内次数を返します。
2387
2388 例:
2389 @c ===beg===
2390 @c load ("graphs")$
2391 @c p5 : path_digraph(5)$
2392 @c print_graph(p5)$
2393 @c vertex_in_degree(4, p5);
2394 @c in_neighbors(4, p5);
2395 @c ===end===
2396 @example
2397 (%i1) load ("graphs")$
2398 (%i2) p5 : path_digraph(5)$
2399 (%i3) print_graph(p5)$
2400 Digraph on 5 vertices with 4 arcs.
2401 Adjacencies:
2402   4 :
2403   3 :  4
2404   2 :  3
2405   1 :  2
2406   0 :  1
2407 (%i4) vertex_in_degree(4, p5);
2408 (%o4)                           1
2409 (%i5) in_neighbors(4, p5);
2410 (%o5)                          [3]
2411 @end example
2412
2413 @opencatbox
2414 @category{Package graphs}
2415 @category{Package graphs - properties}
2416 @closecatbox
2417 @end deffn
2418
2419 @deffn {関数} vertex_out_degree (@var{v}, @var{gr})
2420 有向グラフ @var{gr}の頂点 @var{v}の外次数を返します。
2421
2422 例:
2423 @c ===beg===
2424 @c load ("graphs")$
2425 @c t : random_tournament(10)$
2426 @c vertex_out_degree(0, t);
2427 @c out_neighbors(0, t);
2428 @c ===end===
2429 @example
2430 (%i1) load ("graphs")$
2431 (%i2) t : random_tournament(10)$
2432 (%i3) vertex_out_degree(0, t);
2433 (%o3)                           2
2434 (%i4) out_neighbors(0, t);
2435 (%o4)                        [7, 1]
2436 @end example
2437
2438 @opencatbox
2439 @category{Package graphs}
2440 @category{Package graphs - properties}
2441 @closecatbox
2442 @end deffn
2443
2444 @deffn {関数} vertices (@var{gr})
2445 グラフ @var{gr}の頂点のリストを返します。
2446
2447 例:
2448 @c ===beg===
2449 @c load ("graphs")$
2450 @c vertices(complete_graph(4));
2451 @c ===end===
2452 @example
2453 (%i1) load ("graphs")$
2454 (%i2) vertices(complete_graph(4));
2455 (%o2)                     [3, 2, 1, 0]
2456 @end example
2457
2458 @opencatbox
2459 @category{Package graphs}
2460 @category{Package graphs - properties}
2461 @closecatbox
2462 @end deffn
2463
2464 @deffn {関数} vertex_coloring (@var{gr})
2465 グラフ @var{gr}の頂点の最適色付けを返します。
2466
2467 関数は、彩色数と @var{gr}の頂点の色付けを表すリストを返します。
2468
2469 例:
2470 @c ===beg===
2471 @c load ("graphs")$
2472 @c p:petersen_graph()$
2473 @c vertex_coloring(p);
2474 @c ===end===
2475 @example
2476 (%i1) load ("graphs")$
2477 (%i2) p:petersen_graph()$
2478 (%i3) vertex_coloring(p);
2479 (%o3) [3, [[0, 2], [1, 3], [2, 2], [3, 3], [4, 1], [5, 3],
2480                                  [6, 1], [7, 1], [8, 2], [9, 2]]]
2481 @end example
2482
2483 @opencatbox
2484 @category{Package graphs}
2485 @category{Package graphs - properties}
2486 @closecatbox
2487 @end deffn
2488
2489 @deffn {関数} wiener_index (@var{gr})
2490 グラフ @var{gr}のWiener指数を返します。
2491
2492 例:
2493 @c ===beg===
2494 @c load ("graphs")$
2495 @c wiener_index(dodecahedron_graph());
2496 @c ===end===
2497 @example
2498 (%i2) wiener_index(dodecahedron_graph());
2499 (%o2)                          500
2500 @end example
2501
2502 @opencatbox
2503 @category{Package graphs}
2504 @category{Package graphs - properties}
2505 @closecatbox
2506 @end deffn
2507
2508 @subsection Modifying graphs
2509
2510 @deffn {関数} add_edge (@var{e}, @var{gr})
2511 辺 @var{e}をグラフ @var{gr}に加えます。
2512
2513 例:
2514 @c ===beg===
2515 @c load ("graphs")$
2516 @c p : path_graph(4)$
2517 @c neighbors(0, p);
2518 @c add_edge([0,3], p);
2519 @c neighbors(0, p);
2520 @c ===end===
2521 @example
2522 (%i1) load ("graphs")$
2523 (%i2) p : path_graph(4)$
2524 (%i3) neighbors(0, p);
2525 (%o3)                          [1]
2526 (%i4) add_edge([0,3], p);
2527 (%o4)                         done
2528 (%i5) neighbors(0, p);
2529 (%o5)                        [3, 1]
2530 @end example
2531
2532 @opencatbox
2533 @category{Package graphs}
2534 @category{Package graphs - modifications}
2535 @closecatbox
2536 @end deffn
2537
2538 @deffn {関数} add_edges (@var{e_list}, @var{gr})
2539 リスト @var{e_list}の中の辺すべてをグラフ @var{gr}に加えます。
2540
2541 例:
2542 @c ===beg===
2543 @c load ("graphs")$
2544 @c g : empty_graph(3)$
2545 @c add_edges([[0,1],[1,2]], g)$
2546 @c print_graph(g)$
2547 @c ===end===
2548 @example
2549 (%i1) load ("graphs")$
2550 (%i2) g : empty_graph(3)$
2551 (%i3) add_edges([[0,1],[1,2]], g)$
2552 (%i4) print_graph(g)$
2553 Graph on 3 vertices with 2 edges.
2554 Adjacencies:
2555   2 :  1
2556   1 :  2  0
2557   0 :  1
2558 @end example
2559
2560 @opencatbox
2561 @category{Package graphs}
2562 @category{Package graphs - modifications}
2563 @closecatbox
2564 @end deffn
2565
2566 @deffn {関数} add_vertex (@var{v}, @var{gr})
2567 頂点 @var{v}をグラフ @var{gr}に加えます。
2568
2569 例:
2570 @c ===beg===
2571 @c load ("graphs")$
2572 @c g : path_graph(2)$
2573 @c add_vertex(2, g)$
2574 @c print_graph(g)$
2575 @c ===end===
2576 @example
2577 (%i1) load ("graphs")$
2578 (%i2) g : path_graph(2)$
2579 (%i3) add_vertex(2, g)$
2580 (%i4) print_graph(g)$
2581 Graph on 3 vertices with 1 edges.
2582 Adjacencies:
2583   2 :
2584   1 :  0
2585   0 :  1
2586 @end example
2587
2588 @opencatbox
2589 @category{Package graphs}
2590 @category{Package graphs - modifications}
2591 @closecatbox
2592 @end deffn
2593
2594 @deffn {関数} add_vertices (@var{v_list}, @var{gr})
2595 リスト @var{v_list}の中の頂点すべてをグラフ @var{gr}に加えます。
2596
2597 @opencatbox
2598 @category{Package graphs}
2599 @category{Package graphs - modifications}
2600 @closecatbox
2601 @end deffn
2602
2603 @deffn {関数} connect_vertices (@var{v_list}, @var{u_list}, @var{gr})
2604 グラフ @var{gr}に関して、
2605 リスト @var{v_list}内の頂点すべてを
2606 リスト @var{u_list}内の頂点に連結します。
2607
2608
2609 @var{v_list}と @var{u_list}は1つの頂点か、頂点のリストを取り得ます。
2610
2611 例:
2612 @c ===beg===
2613 @c load ("graphs")$
2614 @c g : empty_graph(4)$
2615 @c connect_vertices(0, [1,2,3], g)$
2616 @c print_graph(g)$
2617 @c ===end===
2618 @example
2619 (%i1) load ("graphs")$
2620 (%i2) g : empty_graph(4)$
2621 (%i3) connect_vertices(0, [1,2,3], g)$
2622 (%i4) print_graph(g)$
2623 Graph on 4 vertices with 3 edges.
2624 Adjacencies:
2625   3 :  0
2626   2 :  0
2627   1 :  0
2628   0 :  3  2  1
2629 @end example
2630
2631 @opencatbox
2632 @category{Package graphs}
2633 @category{Package graphs - modifications}
2634 @closecatbox
2635 @end deffn
2636
2637 @deffn {関数} contract_edge (@var{e}, @var{gr})
2638 グラフ @var{gr}の辺 @var{e}を縮約します。
2639
2640 例:
2641 @c ===beg===
2642 @c load ("graphs")$
2643 @c g: create_graph(
2644 @c       8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2645 @c print_graph(g)$
2646 @c contract_edge([3,4], g)$
2647 @c print_graph(g)$
2648 @c ===end===
2649 @example
2650 (%i1) load ("graphs")$
2651 (%i2) g: create_graph(
2652       8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2653 (%i3) print_graph(g)$
2654 Graph on 8 vertices with 7 edges.
2655 Adjacencies:
2656   7 :  4
2657   6 :  4
2658   5 :  4
2659   4 :  7  6  5  3
2660   3 :  4  2  1  0
2661   2 :  3
2662   1 :  3
2663   0 :  3
2664 (%i4) contract_edge([3,4], g)$
2665 (%i5) print_graph(g)$
2666 Graph on 7 vertices with 6 edges.
2667 Adjacencies:
2668   7 :  3
2669   6 :  3
2670   5 :  3
2671   3 :  5  6  7  2  1  0
2672   2 :  3
2673   1 :  3
2674   0 :  3
2675 @end example
2676
2677 @opencatbox
2678 @category{Package graphs}
2679 @category{Package graphs - modifications}
2680 @closecatbox
2681 @end deffn
2682
2683 @deffn {関数} remove_edge (@var{e}, @var{gr})
2684 グラフ @var{gr}から辺 @var{e}を削除します。
2685
2686 例:
2687 @c ===beg===
2688 @c load ("graphs")$
2689 @c c3 : cycle_graph(3)$
2690 @c remove_edge([0,1], c3)$
2691 @c print_graph(c3)$
2692 @c ===end===
2693 @example
2694 (%i1) load ("graphs")$
2695 (%i2) c3 : cycle_graph(3)$
2696 (%i3) remove_edge([0,1], c3)$
2697 (%i4) print_graph(c3)$
2698 Graph on 3 vertices with 2 edges.
2699 Adjacencies:
2700   2 :  0  1
2701   1 :  2
2702   0 :  2
2703 @end example
2704
2705 @opencatbox
2706 @category{Package graphs}
2707 @category{Package graphs - modifications}
2708 @closecatbox
2709 @end deffn
2710
2711 @deffn {関数} remove_vertex (@var{v}, @var{gr})
2712 グラフ @var{gr}から頂点 @var{v}を削除します。
2713
2714 @opencatbox
2715 @category{Package graphs}
2716 @closecatbox
2717 @end deffn
2718
2719 @subsection Reading and writing to files
2720
2721 @deffn {関数} dimacs_export (@var{gr}, @var{fl})
2722 @deffnx {関数} dimacs_export (@var{gr}, @var{fl}, @var{comment1}, ..., @var{commentn})
2723
2724 グラフをファイル @var{fl}にDIMACSフォーマットでエクスポートします。
2725 オプションのコメントはファイルの頭に加えられます。
2726
2727 @opencatbox
2728 @category{Package graphs}
2729 @category{Package graphs - io}
2730 @closecatbox
2731 @end deffn
2732
2733 @deffn {関数} dimacs_import (@var{fl})
2734
2735 DIMACSフォーマットのファイル @var{fl}からグラフを返します。
2736
2737 @opencatbox
2738 @category{Package graphs}
2739 @category{Package graphs - io}
2740 @closecatbox
2741 @end deffn
2742
2743 @deffn {関数} graph6_decode (@var{str})
2744
2745 文字列 @var{str}にgraph6フォーマットで符号化されたグラフを返します。
2746
2747 @opencatbox
2748 @category{Package graphs}
2749 @category{Package graphs - io}
2750 @closecatbox
2751 @end deffn
2752
2753 @deffn {関数} graph6_encode (@var{gr})
2754
2755 グラフ @var{gr}をgraph6フォーマットに符号化した文字列を返します。
2756
2757 @opencatbox
2758 @category{Package graphs}
2759 @category{Package graphs - io}
2760 @closecatbox
2761 @end deffn
2762
2763 @deffn {関数} graph6_export (@var{gr_list}, @var{fl})
2764
2765 リスト @var{gr_list}内のグラフをファイル @var{fl}に
2766 graph6フォーマットでエクスポートします。
2767
2768
2769 @opencatbox
2770 @category{Package graphs}
2771 @category{Package graphs - io}
2772 @closecatbox
2773 @end deffn
2774
2775 @deffn {関数} graph6_import (@var{fl})
2776
2777 graph6フォーマットのファイル @var{fl}からグラフのリストを返します。
2778
2779 @opencatbox
2780 @category{Package graphs}
2781 @category{Package graphs - io}
2782 @closecatbox
2783 @end deffn
2784
2785 @deffn {関数} sparse6_decode (@var{str})
2786
2787 文字列 @var{str}にsparse6フォーマットで符号化されたグラフを返します。
2788
2789 @opencatbox
2790 @category{Package graphs}
2791 @category{Package graphs - io}
2792 @closecatbox
2793 @end deffn
2794
2795 @deffn {関数} sparse6_encode (@var{gr})
2796
2797 グラフ @var{gr}をsparse6フォーマットに符号化した文字列を返します。
2798
2799 @opencatbox
2800 @category{Package graphs}
2801 @category{Package graphs - io}
2802 @closecatbox
2803 @end deffn
2804
2805 @deffn {関数} sparse6_export (@var{gr_list}, @var{fl})
2806
2807 リスト @var{gr_list}内のグラフを
2808 ファイル @var{fl}にsparse6フォーマットでエクスポートします。
2809
2810 @opencatbox
2811 @category{Package graphs}
2812 @category{Package graphs - io}
2813 @closecatbox
2814 @end deffn
2815
2816 @deffn {関数} sparse6_import (@var{fl})
2817
2818 sparse6フォーマットのファイル @var{fl}からグラフのリストを返します。
2819
2820
2821 @opencatbox
2822 @category{Package graphs}
2823 @category{Package graphs - io}
2824 @closecatbox
2825 @end deffn
2826
2827 @subsection Visualization
2828
2829 @deffn {関数} draw_graph (@var{graph})
2830 @deffnx {関数} draw_graph (@var{graph}, @var{option1}, ..., @var{optionk})
2831 @code{draw}パッケージを使ってグラフを描画します。
2832
2833 頂点を配置するのに使われるアルゴリズムは
2834 オプション引数 @var{program}で指定されます。
2835 デフォルト値は @code{program=spring_embedding}です。
2836 @var{draw_graph}は
2837 頂点を配置するのにgraphvizプログラムも使うことができますが、
2838 graphvizを別途インストールしなければいけません。
2839
2840 例 1:
2841
2842 @c ===beg===
2843 @c load ("graphs")$
2844 @c g:grid_graph(10,10)$
2845 @c m:max_matching(g)$
2846 @c draw_graph(g,
2847 @c    spring_embedding_depth=100,
2848 @c    show_edges=m, edge_type=dots,
2849 @c    vertex_size=0)$
2850 @c ===end===
2851 @example
2852 (%i1) load ("graphs")$
2853 (%i2) g:grid_graph(10,10)$
2854 (%i3) m:max_matching(g)$
2855 (%i4) draw_graph(g,
2856    spring_embedding_depth=100,
2857    show_edges=m, edge_type=dots,
2858    vertex_size=0)$
2859 @end example
2860
2861 @ifhtml
2862 @image{@value{figuresfolder}/graphs09,6cm}
2863 @end ifhtml
2864
2865 例 2:
2866
2867 @c ===beg===
2868 @c load ("graphs")$
2869 @c g:create_graph(16,
2870 @c     [
2871 @c      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2872 @c      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2873 @c      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2874 @c      [10,14],[15,14],[13,14]
2875 @c     ])$
2876 @c t:minimum_spanning_tree(g)$
2877 @c draw_graph(
2878 @c     g,
2879 @c     show_edges=edges(t),
2880 @c     show_edge_width=4,
2881 @c     show_edge_color=green,
2882 @c     vertex_type=filled_square,
2883 @c     vertex_size=2
2884 @c     )$
2885 @c ===end===
2886 @example
2887 (%i1) load ("graphs")$
2888 (%i2) g:create_graph(16,
2889     [
2890      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2891      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2892      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2893      [10,14],[15,14],[13,14]
2894     ])$
2895 (%i3) t:minimum_spanning_tree(g)$
2896 (%i4) draw_graph(
2897     g,
2898     show_edges=edges(t),
2899     show_edge_width=4,
2900     show_edge_color=green,
2901     vertex_type=filled_square,
2902     vertex_size=2
2903     )$
2904 @end example
2905
2906 @ifhtml
2907 @image{@value{figuresfolder}/graphs10,6cm}
2908 @end ifhtml
2909
2910 例 3:
2911
2912 @c ===beg===
2913 @c load ("graphs")$
2914 @c g:create_graph(16,
2915 @c     [
2916 @c      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2917 @c      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2918 @c      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2919 @c      [10,14],[15,14],[13,14]
2920 @c     ])$
2921 @c mi : max_independent_set(g)$
2922 @c draw_graph(
2923 @c     g,
2924 @c     show_vertices=mi,
2925 @c     show_vertex_type=filled_up_triangle,
2926 @c     show_vertex_size=2,
2927 @c     edge_color=cyan,
2928 @c     edge_width=3,
2929 @c     show_id=true,
2930 @c     text_color=brown
2931 @c     )$
2932 @c ===end===
2933 @example
2934 (%i1) load ("graphs")$
2935 (%i2) g:create_graph(16,
2936     [
2937      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
2938      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
2939      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
2940      [10,14],[15,14],[13,14]
2941     ])$
2942 (%i3) mi : max_independent_set(g)$
2943 (%i4) draw_graph(
2944     g,
2945     show_vertices=mi,
2946     show_vertex_type=filled_up_triangle,
2947     show_vertex_size=2,
2948     edge_color=cyan,
2949     edge_width=3,
2950     show_id=true,
2951     text_color=brown
2952     )$
2953 @end example
2954
2955 @ifhtml
2956 @image{@value{figuresfolder}/graphs11,6cm}
2957 @end ifhtml
2958
2959 例 4:
2960
2961 @c ===beg===
2962 @c load ("graphs")$
2963 @c net : create_graph(
2964 @c     [0,1,2,3,4,5],
2965 @c     [
2966 @c      [[0,1], 3], [[0,2], 2],
2967 @c      [[1,3], 1], [[1,4], 3],
2968 @c      [[2,3], 2], [[2,4], 2],
2969 @c      [[4,5], 2], [[3,5], 2]
2970 @c     ],
2971 @c     directed=true
2972 @c     )$
2973 @c draw_graph(
2974 @c     net,
2975 @c     show_weight=true,
2976 @c     vertex_size=0,
2977 @c     show_vertices=[0,5],
2978 @c     show_vertex_type=filled_square,
2979 @c     head_length=0.2,
2980 @c     head_angle=10,
2981 @c     edge_color="dark-green",
2982 @c     text_color=blue
2983 @c     )$
2984 @c ===end===
2985 @example
2986 (%i1) load ("graphs")$
2987 (%i2) net : create_graph(
2988     [0,1,2,3,4,5],
2989     [
2990      [[0,1], 3], [[0,2], 2],
2991      [[1,3], 1], [[1,4], 3],
2992      [[2,3], 2], [[2,4], 2],
2993      [[4,5], 2], [[3,5], 2]
2994     ],
2995     directed=true
2996     )$
2997 (%i3) draw_graph(
2998     net,
2999     show_weight=true,
3000     vertex_size=0,
3001     show_vertices=[0,5],
3002     show_vertex_type=filled_square,
3003     head_length=0.2,
3004     head_angle=10,
3005     edge_color="dark-green",
3006     text_color=blue
3007     )$
3008 @end example
3009
3010 @ifhtml
3011 @image{@value{figuresfolder}/graphs12,6cm}
3012 @end ifhtml
3013
3014 例 5:
3015
3016 @c ===beg===
3017 @c load("graphs")$
3018 @c g: petersen_graph(20, 2);
3019 @c draw_graph(g, redraw=true, program=planar_embedding);
3020 @c ===end===
3021 @example
3022 (%i1) load("graphs")$
3023 (%i2) g: petersen_graph(20, 2);
3024 (%o2)                         GRAPH
3025 (%i3) draw_graph(g, redraw=true, program=planar_embedding);
3026 (%o3)                         done
3027 @end example
3028
3029 @ifhtml
3030 @image{@value{figuresfolder}/graphs14,6cm}
3031 @end ifhtml
3032
3033 例 6:
3034
3035 @c ===beg===
3036 @c load("graphs")$
3037 @c t: tutte_graph();
3038 @c draw_graph(t, redraw=true,
3039 @c               fixed_vertices=[1,2,3,4,5,6,7,8,9]);
3040 @c ===end===
3041 @example
3042 (%i1) load("graphs")$
3043 (%i2) t: tutte_graph();
3044 (%o2)                         GRAPH
3045 (%i3) draw_graph(t, redraw=true,
3046                     fixed_vertices=[1,2,3,4,5,6,7,8,9]);
3047 (%o3)                         done
3048 @end example
3049
3050 @ifhtml
3051 @image{@value{figuresfolder}/graphs15,6cm}
3052 @end ifhtml
3053
3054 @opencatbox
3055 @category{Package graphs}
3056 @closecatbox
3057 @end deffn
3058
3059 @defvr {オプション変数} draw_graph_program
3060 デフォルト値: @var{spring_embedding}
3061
3062 頂点を配置するのに使われるプログラムのデフォルト値は
3063 @code{draw_graph}プログラムです。
3064
3065 @opencatbox
3066 @category{Package graphs}
3067 @category{Package graphs - draw_graphs options}
3068 @closecatbox
3069 @end defvr
3070
3071 @defvr {draw_graphオプション} show_id
3072 デフォルト値: @var{false}
3073
3074 もし @var{true}なら頂点のidが表示されます。
3075
3076 @opencatbox
3077 @category{Package graphs}
3078 @category{Package graphs - draw_graphs options}
3079 @closecatbox
3080 @end defvr
3081
3082 @defvr {draw_graphオプション} show_label
3083 デフォルト値: @var{false}
3084
3085 もし @var{true}なら頂点のラベルが表示されます。
3086
3087 @opencatbox
3088 @category{Package graphs}
3089 @category{Package graphs - draw_graphs options}
3090 @closecatbox
3091 @end defvr
3092
3093 @defvr {draw_graphオプション} label_alignment
3094 デフォルト値: @var{center}
3095
3096 頂点のラベル/idをいかに整列させるか決めます。
3097 @code{left}, @code{center}, @code{right}であり得ます。
3098
3099 @opencatbox
3100 @category{Package graphs}
3101 @category{Package graphs - draw_graphs options}
3102 @closecatbox
3103 @end defvr
3104
3105 @defvr {draw_graphオプション} show_weight
3106 デフォルト値: @var{false}
3107
3108 もし @var{true}なら辺の重みを表示します。
3109
3110 @opencatbox
3111 @category{Package graphs}
3112 @category{Package graphs - draw_graphs options}
3113 @closecatbox
3114 @end defvr
3115
3116 @defvr {draw_graphオプション} vertex_type
3117 デフォルト値: @var{circle}
3118
3119 頂点をいかに表示するか定義します。
3120 可能な値に関しては、
3121 @code{draw}パッケージの @var{point_type}オプションを参照してください。
3122
3123 @opencatbox
3124 @category{Package graphs}
3125 @category{Package graphs - draw_graphs options}
3126 @closecatbox
3127 @end defvr
3128
3129 @defvr {draw_graphオプション} vertex_size
3130 頂点のサイズ。
3131
3132 @opencatbox
3133 @category{Package graphs}
3134 @category{Package graphs - draw_graphs options}
3135 @closecatbox
3136 @end defvr
3137
3138 @defvr {draw_graphオプション} vertex_color
3139 頂点を表示するのに使う色。
3140
3141 @opencatbox
3142 @category{Package graphs}
3143 @category{Package graphs - draw_graphs options}
3144 @closecatbox
3145 @end defvr
3146
3147 @defvr {draw_graphオプション} show_vertices
3148 デフォルト値: []
3149
3150 選択された頂点を異なる色を使って表示。
3151
3152 @opencatbox
3153 @category{Package graphs}
3154 @category{Package graphs - draw_graphs options}
3155 @closecatbox
3156 @end defvr
3157
3158 @defvr {draw_graphオプション} show_vertex_type
3159
3160 @var{show_vertices}で指定された頂点をいかに表示するか定義します。
3161 可能な値については、
3162 @code{draw}パッケージの @var{point_type}オプションを参照してください。
3163
3164 @opencatbox
3165 @category{Package graphs}
3166 @category{Package graphs - draw_graphs options}
3167 @closecatbox
3168 @end defvr
3169
3170 @defvr {draw_graphオプション} show_vertex_size
3171 @var{show_vertices}内の頂点のサイズ
3172
3173 @opencatbox
3174 @category{Package graphs}
3175 @category{Package graphs - draw_graphs options}
3176 @closecatbox
3177 @end defvr
3178
3179 @defvr {draw_graphオプション} show_vertex_color
3180 @var{show_vertices}リスト内の頂点を表示するのに使う色。
3181
3182 @opencatbox
3183 @category{Package graphs}
3184 @category{Package graphs - draw_graphs options}
3185 @closecatbox
3186 @end defvr
3187
3188 @defvr {draw_graphオプション} vertex_partition
3189 デフォルト値: []
3190
3191 グラフの頂点の分割 @code{[[v1,v2,...],...,[vk,...,vn]]}
3192 分割内のそれぞれのリストの頂点は異なる色で描画されます。
3193
3194 @opencatbox
3195 @category{Package graphs}
3196 @category{Package graphs - draw_graphs options}
3197 @closecatbox
3198 @end defvr
3199
3200 @defvr {draw_graphオプション} vertex_coloring
3201 頂点の色付けを指定します。
3202 色付け @var{col}は
3203 @var{vertex_coloring}が返すようなフォーマットで指定されなければいけません。
3204
3205 @opencatbox
3206 @category{Package graphs}
3207 @category{Package graphs - draw_graphs options}
3208 @closecatbox
3209 @end defvr
3210
3211 @defvr {draw_graphオプション} edge_color
3212 辺を表示するのに使われる色。
3213
3214 @opencatbox
3215 @category{Package graphs}
3216 @category{Package graphs - draw_graphs options}
3217 @closecatbox
3218 @end defvr
3219
3220 @defvr {draw_graphオプション} edge_width
3221 辺の幅。
3222
3223 @opencatbox
3224 @category{Package graphs}
3225 @category{Package graphs - draw_graphs options}
3226 @closecatbox
3227 @end defvr
3228
3229 @defvr {draw_graphオプション} edge_type
3230 辺をいかに表示するか定義します。
3231 @code{draw}パッケージの@var{line_type}オプションを参照してください。
3232
3233 @opencatbox
3234 @category{Package graphs}
3235 @category{Package graphs - draw_graphs options}
3236 @closecatbox
3237 @end defvr
3238
3239 @defvr {draw_graphオプション} show_edges
3240 異なる色を使ってリスト @var{e_list}内で指定された辺を表示する。
3241
3242 @opencatbox
3243 @category{Package graphs}
3244 @category{Package graphs - draw_graphs options}
3245 @closecatbox
3246 @end defvr
3247
3248 @defvr {draw_graphオプション} show_edge_color
3249 @var{show_edges}リスト内の辺を表示するのに使う色。
3250
3251 @opencatbox
3252 @category{Package graphs}
3253 @category{Package graphs - draw_graphs options}
3254 @closecatbox
3255 @end defvr
3256
3257 @defvr {draw_graphオプション} show_edge_width
3258 @var{show_edges}内の辺の幅。
3259
3260 @opencatbox
3261 @category{Package graphs}
3262 @category{Package graphs - draw_graphs options}
3263 @closecatbox
3264 @end defvr
3265
3266 @defvr {draw_graphオプション} show_edge_type
3267 @var{show_edges}内の辺を以下に表示するかを定義します。
3268 @code{draw}パッケージの@var{line_type}オプションを参照してください。
3269
3270 @opencatbox
3271 @category{Package graphs}
3272 @category{Package graphs - draw_graphs options}
3273 @closecatbox
3274 @end defvr
3275
3276 @defvr {draw_graphオプション} edge_partition
3277 グラフの辺の分割 @code{[[e1,e2,...],...,[ek,...,em]]}
3278 分割内のそれぞれのリストの辺は異なる色を使って描画されます。
3279
3280 @opencatbox
3281 @category{Package graphs}
3282 @category{Package graphs - draw_graphs options}
3283 @closecatbox
3284 @end defvr
3285
3286 @defvr {draw_graphオプション} edge_coloring
3287 辺の色付け。
3288 色付けは
3289 関数 @var{edge_coloring}が返すようなフォーマットで指定しなければいけません。
3290
3291 @opencatbox
3292 @category{Package graphs}
3293 @category{Package graphs - draw_graphs options}
3294 @closecatbox
3295 @end defvr
3296
3297 @defvr {draw_graphオプション} redraw
3298 デフォルト値: @var{false}
3299
3300 もし @code{true}なら、
3301 たとえ位置がグラフの以前の描画から保存されていても頂点位置が再計算されます。
3302
3303 @opencatbox
3304 @category{Package graphs}
3305 @category{Package graphs - draw_graphs options}
3306 @closecatbox
3307 @end defvr
3308
3309 @defvr {draw_graphオプション} head_angle
3310 デフォルト値: 15
3311
3312 (有向グラフの)弧に表示される矢印の角度。
3313
3314 @opencatbox
3315 @category{Package graphs}
3316 @category{Package graphs - draw_graphs options}
3317 @closecatbox
3318 @end defvr
3319
3320 @defvr {draw_graphオプション} head_length
3321 デフォルト値: 0.1
3322
3323 (有向グラフの)弧に表示される矢印の長さ。
3324
3325 @opencatbox
3326 @category{Package graphs}
3327 @category{Package graphs - draw_graphs options}
3328 @closecatbox
3329 @end defvr
3330
3331 @defvr {draw_graphオプション} spring_embedding_depth
3332 デフォルト値: 50
3333
3334 バネ埋め込みグラフ描画アルゴリズムでの繰り返し回数
3335
3336 @opencatbox
3337 @category{Package graphs}
3338 @category{Package graphs - draw_graphs options}
3339 @closecatbox
3340 @end defvr
3341
3342 @defvr {draw_graphオプション} terminal
3343 描画で使う端末。
3344 (@code{draw}パッケージの @var{terminal}オプションを参照してください。)
3345
3346 @opencatbox
3347 @category{Package graphs}
3348 @category{Package graphs - draw_graphs options}
3349 @closecatbox
3350 @end defvr
3351
3352 @defvr {draw_graphオプション} file_name
3353 端末がスクリーンでないなら、描画のファイル名。
3354
3355 @opencatbox
3356 @category{Package graphs}
3357 @category{Package graphs - draw_graphs options}
3358 @closecatbox
3359 @end defvr
3360
3361 @defvr {draw_graphオプション} program
3362 グラフの頂点を配置するのに使われるプログラムを定義します。
3363 graphvizプログラム (dot, neato, twopi, circ, fdp)の1つ,
3364 @var{circular}, @var{spring_embedding}, @var{planar_embedding}を取り得ます。
3365 2連結平面グラフでは @var{planar_embedding}だけが利用可能です。
3366 @code{program=spring_embedding}の時、
3367 固定位置の頂点の集合が @var{fixed_vertices}オプションで指定可能です。
3368
3369 @opencatbox
3370 @category{Package graphs}
3371 @category{Package graphs - draw_graphs options}
3372 @closecatbox
3373 @end defvr
3374
3375 @defvr {draw_graphオプション} fixed_vertices
3376 正多角形沿いに固定された位置を持つ頂点のリストを指定します。
3377 @code{program=spring_embedding}の時、使うことができます。
3378
3379 @opencatbox
3380 @category{Package graphs}
3381 @category{Package graphs - draw_graphs options}
3382 @closecatbox
3383 @end defvr
3384
3385 @deffn {関数} vertices_to_path (@var{v_list})
3386 頂点のリスト @var{v_list}を
3387 @var{v_list}で定義された経路の辺のリストに変換します。
3388
3389 @opencatbox
3390 @category{Package graphs}
3391 @closecatbox
3392 @end deffn
3393
3394 @deffn {関数} vertices_to_cycle (@var{v_list})
3395 頂点のリスト @var{v_list}を
3396 @var{v_list}で定義された閉路の辺のリストに変換します。
3397
3398 @opencatbox
3399 @category{Package graphs}
3400 @closecatbox
3401 @end deffn