The GraphTheory Package

はじめる前に
新機能一覧
Maple ワークシートの作成
Mapleワークシートを共有
Maple ウィンドウのカスタマイズ
Maple システムのカスタマイズ
コネクティビティ
Mathematics
数学
- テンソル解析
- パッケージ
- ファンクションアドバイザ
- ベキ級数
- ベクトル解析
- 不活性関数
- 代数
- 因数分解と方程式解法
- 基本数学
- 基本的な注意事項
- 変分法
- 変換
- 幾何
- 微分代数方程式
- 微分幾何学
- 微分方程式
- 微積分
- 数
- 数値計算
- 数学関数
- 数論
- 最適化
- 特殊関数
- 統計
- 線形代数
- 群論
- 評価
- 論理
- 過去のパッケージ
- 金融
- 離散数学
  - グラフ理論
    - GraphTheory パッケージ
    - 例題
  - 組合せ論
  - 総和と差分方程式
  - 離散変換
  - OrderBasis コマンド
  - 積
- piecewise examples
- グラフ電卓
- 区分関数
物理
プログラミング
グラフィックス
Student パッケージ
Science and Engineering
科学・エンジニアリング
アプリケーションと例題
リファレンス
システム
MapleSim
MapleSim ツールボックス
MapleSim ヘルプ
Tasks
Toolboxes
エラーメッセージガイド
マニュアル
数学アプリ

This worksheet demonstrates some features of the GraphTheory package. It is presented in a tutorial format.

Creating Graphs

The main command for creating an undirected graph is the Graph command. For a directed graph the main command is the Digraph command. For both commands, you may specify the vertices in an ordered list. The vertices may be integers, symbols, or strings. By using strings, you can affix any text that you want for the vertex labels.

(1.1)

(1.2)

(1.3)

(1.4)

(1.5)

(1.6)

You may specify the numberof vertices, , in which case they are labeled 1,2,..., .

(1.7)

(1.8)

Inserting edges

You may insert edges into an undirected graph one at a time using the AddEdge command. Each edge should be input as a set of two vertices.

You can also specify more than one edge at a time in a set.

(1.1.1)

(1.1.2)

(1.1.3)

For a directed graph, use the AddArc command and input the edges as lists of vertices.

(1.1.4)

(1.1.5)

(1.1.6)

Using a set of edges

You may create an undirected graph with given edges by passing them in as a set where each edge is itself a set of two vertices. If the vertices are not specified explicitly, the vertices will be taken to be all vertices appearing in the set of edges. Thus, the previous graph G, which is a simple path, can be created by

(1.2.1)

(1.2.2)

Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 1, (3, 3) = 0, (3, 4) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 1, (4, 4) = 0})

(1.2.3)

Similarly, the above previous directed graph H, which is a directed path, can be created by

(1.2.4)

Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0})

(1.2.5)

Using an adjacency matrix

The above graphs G and H can also be created from the adjacency matrix. If the vertices are not explicitly given in a list, then the vertex labels are taken to be integers 1,2,...,n where n is the dimension of the adjacency matrix.

A := Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 1, (3, 3) = 0, (3, 4) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 1, (4, 4) = 0})

(1.3.1)

(1.3.2)

(1.3.3)

(1.3.4)

B := Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0})

(1.3.5)

(1.3.6)

(1.3.7)

(1.3.8)

Using a list of neighbors

If G has n vertices, the input is a list of n lists of vertices.

(1.4.1)

(1.4.2)

(1.4.3)

(1.4.4)

For a directed graph, the list of neighbors need not be symmetric. Here is a directed cycle, i.e., the directed edges 1 to 2, 2 to 3, 3 to 4 and 4 to 1. This list corresponds to the list of "departures" of the graph.

(1.4.5)

(1.4.6)

(1.4.7)

(1.4.8)

(1.4.9)

Using trails

This is a convenient shorthand. The trail 1,2,3,4 represents the edges 1 to 2 to 3 to 4.

(1.5.1)

(1.5.2)

(1.5.3)

(1.5.4)

(1.5.5)

Weighted edges

To create a weighted graph, use the weighted option.

(1.6.1)

An undirected edge (u,v) of weight w is input in the form [{u,v},w].
For a directed edge from u to v with weight w, use [[u,v],w] instead.

(1.6.2)

Matrix(5, 5, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (1, 5) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 0, (2, 4) = 0, (2, 5) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 1, (3, 5) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 1, (4, 4) = 0, (4, 5) = 0, (5, 1) = 0, (5, 2) = 0, (5, 3) = 0, (5, 4) = 0, (5, 5) = 0})

(1.6.3)

(1.6.4)

The same graph can be created directly with

(1.6.5)

An edge weight can be 0.

(1.6.6)

(1.6.7)

Matrix(5, 5, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (1, 5) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (2, 5) = 0, (3, 1) = 0, (3, 2) = 1, (3, 3) = 0, (3, 4) = 1, (3, 5) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 1, (4, 4) = 0, (4, 5) = 0, (5, 1) = 0, (5, 2) = 0, (5, 3) = 0, (5, 4) = 0, (5, 5) = 0})

(1.6.8)

Matrix(5, 5, {(1, 1) = 0, (1, 2) = 2.3, (1, 3) = 0, (1, 4) = 0, (1, 5) = 0, (2, 1) = 2.3, (2, 2) = 0, (2, 3) = 0., (2, 4) = 0, (2, 5) = 0, (3, 1) = 0, (3, 2) = 0., (3, 3) = 0, (3, 4) = 4.5, (3, 5) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 4.5, (4, 4) = 0, (4, 5) = 0, (5, 1) = 0, (5, 2) = 0, (5, 3) = 0, (5, 4) = 0, (5, 5) = 0})

(1.6.9)

Paths, cycles, and complete graphs

Paths and cycles can be created by using a trail. There are also two primitives for creating these because they are heavily used. There is also a primitive for creating complete graphs.

(1.7.1)

(1.7.2)

(1.7.3)

(1.7.4)

(1.7.5)

(1.7.6)

(1.7.7)

(1.7.8)

(1.7.9)

Drawing Graphs

Here we just show some examples which illustrate the main options.
Further examples are given under the section "Special Graphs".

(2.1)

(2.2)

If you dislike the placement of the vertices, you can specify them as follows.

(2.3)

The Petersen graph is very well known in graph theory. It is a non-planar graph. This is one of the standard drawings.

The placement of the vertices is stored in the graph data structure.

(2.4)

The "spring" method for drawing graphs will find other "symmetric" drawings of the Petersen graph. Try executing this a few times.

The spring method works in 3-D

The spring method will work for moderately large graphs (graphs up to 1000 vertices).

(2.5)

For large weighted graphs the edge weights and edge labels may "clutter" the graph. You can turn these off.

(2.6)

	Exporting and Importing Graphs
	The commands ExportGraph and ImportGraph allow you to output one or more graphs to a file or read graphs from a file. Supported formats are `dimacs`, `dimacs_relaxed`, `combinatorica`, `edges`, `metapost`, `dot`, `sparse6`, and `graph6`.

Graph Properties

There are lots of graph commands. Here we illustrate basic commands and how to accomplish various tasks.

Undirected graphs

(4.1.1)

(4.1.2)

(4.1.3)

(4.1.4)

(4.1.5)

(4.1.6)

(4.1.7)

(4.1.8)

(4.1.9)

(4.1.10)

(4.1.11)

(4.1.12)

(4.1.13)

(4.1.14)

(4.1.15)

(4.1.16)

(4.1.17)

(4.1.18)

(4.1.19)

(4.1.20)

(4.1.21)

(4.1.22)

Directed graphs

(4.2.1)

(4.2.2)

(4.2.3)

(4.2.4)

(4.2.5)

Matrix(5, 5, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 1, (1, 4) = 0, (1, 5) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 0, (2, 4) = 1, (2, 5) = 1, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 0, (3, 5) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0, (4, 5) = 1, (5, 1) = 0, (5, 2) = 0, (5, 3) = 0, (5, 4) = 1, (5, 5) = 0})

(4.2.6)

Matrix(5, 5, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 1, (1, 4) = 2, (1, 5) = 2, (2, 1) = 1, (2, 2) = 0, (2, 3) = 2, (2, 4) = 1, (2, 5) = 1, (3, 1) = infinity, (3, 2) = infinity, (3, 3) = 0, (3, 4) = infinity, (3, 5) = infinity, (4, 1) = infinity, (4, 2) = infinity, (4, 3) = infinity, (4, 4) = 0, (4, 5) = 1, (5, 1) = infinity, (5, 2) = infinity, (5, 3) = infinity, (5, 4) = 1, (5, 5) = 0})

(4.2.7)

Graph Attributes

You may attach arbitrary information to the graph as a whole, each vertex of the graph, and each edge of the graph. This is done using the attribute commands {Get/Set/List/Discard}{Graph/Vertex/Edge}Attribute(s).

(5.1)

(5.2)

(5.3)

(5.4)

(5.5)

Special Graphs and Random Graphs

The two packages SpecialGraphs and RandomGraphs must be loaded separately.

(6.1)

(6.2)

As an example, we assign random integer edge weights to the prism graph G and run Kruskal's algorithm to compute the minimal spanning tree and highlight the graph with the minimal spanning tree.