图论和离散数学的Sage快速入门

这个 Sage 快速入门教程是为MAA准备工作坊“Sage：对本科生使用开源数学软件”开发的（由NSF提供资金，到期日：0817071）。它是根据Creative Commons Attribution -ShareLiked 3.0许可证授权的 (CC BY-SA ）

由于计算机是离散的和有限的，离散数学的主题是自然实现和使用。我们从图论开始。

图论

预定义的 graphs 对象提供了大量的示例。只需标签就可以看到！

sage: graphs.[tab]

它的同伴 digraphs 也有许多内置示例。

可视化图形与绘制函数类似。

sage: G = graphs.HeawoodGraph()
sage: plot(G)
Graphics object consisting of 36 graphics primitives

定义自己的图形很容易。一种方法是如下。

• 在列表旁边放置一个带有冒号的顶点（回想一下编程教程中的这个概念），以显示其相邻的顶点。例如，要将顶点4放在顶点0和2旁边，请使用 4:[0,2] .

• 现在用大括号将所有这些组合起来（在编程教程的高级附录中，这称为 词典 ）

sage: H=Graph({0:[1,2,3], 4:[0,2], 6:[1,2,3,4,5]})
sage: plot(H)
Graphics object consisting of 18 graphics primitives

邻接矩阵、其他图和类似的输入也被识别。

图具有顶点位置的“位置”信息。计算布局有几种不同的方法，也可以自己计算。预定义的图形通常带有“漂亮”的布局。

sage: H.set_pos(H.layout_circular())
sage: plot(H)
Graphics object consisting of 18 graphics primitives

顶点可以是很多东西，例如纠错代码的码字。

注解

技术警告：它们需要像Python的元组一样是“不可变的”。

这里我们有一个整数上的矩阵和一个作为顶点的变量矩阵。

sage: a=matrix([[1,2],[3,4]])
sage: var('x y z w')
(x, y, z, w)
sage: b=matrix([[x,y],[z,w]])
sage: a.set_immutable()
sage: b.set_immutable()
sage: K=DiGraph({a:[b]})
sage: show(K, vertex_size=800)

可以标记边。

sage: L=graphs.CycleGraph(5)
sage: for edge in L.edges():
....:     u = edge[0]
....:     v = edge[1]
....:     L.set_edge_label(u, v, u*v)
sage: plot(L, edge_labels=True)
Graphics object consisting of 16 graphics primitives

与其他数学领域有着天然的联系。这里我们计算立方体骨架的自同构群和特征值。

sage: C = graphs.CubeGraph(3)
sage: plot(C)
Graphics object consisting of 21 graphics primitives

sage: Aut=C.automorphism_group()
sage: print("Order of automorphism group: {}".format(Aut.order()))
Order of automorphism group:  48
sage: print("Group: \n{}".format(Aut)) # random
Group:
Permutation Group with generators [('010','100')('011','101'), ('001','010')('101','110'), ('000','001')('010','011')('100','101')('110','111')]

sage: C.spectrum()
[3, 1, 1, 1, -1, -1, -1, -3]

对图形有大量的 Latex 支持。下图显示了一个可以执行的操作的示例；这是Heawood图。

在下一个命令中按“tab”查看所有可用选项。

sage: sage.graphs.graph_latex.GraphLatex.set_option?

更离散的数学

离散数学是一个很广的领域，Sage对它的大部分都有很好的支持。这在很大程度上归因于“Sage”群体。这些开发人员以前是为MuPad开发的（称为“MuPad-combinat”），但在MuPad被出售前不久，就转投Sage。

简单组合学

Sage可以处理基本的组合结构，如组合和排列。

sage: pets = ['dog', 'cat', 'snake', 'spider']
sage: C=Combinations(pets)
sage: C.list()
[[], ['dog'], ['cat'], ['snake'], ['spider'], ['dog', 'cat'], ['dog', 'snake'], ['dog', 'spider'], ['cat', 'snake'], ['cat', 'spider'], ['snake', 'spider'], ['dog', 'cat', 'snake'], ['dog', 'cat', 'spider'], ['dog', 'snake', 'spider'], ['cat', 'snake', 'spider'], ['dog', 'cat', 'snake', 'spider']]

sage: for a, b in Combinations(pets, 2):
....:     print("The {} chases the {}.".format(a, b))
The dog chases the cat.
The dog chases the snake.
The dog chases the spider.
The cat chases the snake.
The cat chases the spider.
The snake chases the spider.

sage: for pair in Permutations(pets, 2):
....:     print(pair)
['dog', 'cat']
['dog', 'snake']
['dog', 'spider']
['cat', 'dog']
['cat', 'snake']
['cat', 'spider']
['snake', 'dog']
['snake', 'cat']
['snake', 'spider']
['spider', 'dog']
['spider', 'cat']
['spider', 'snake']

当然，我们经常需要这些数字，这些也存在。有些人很熟悉：

sage: Permutations(5).cardinality()
120

其他人则稍逊于此：

sage: D = Derangements([1,1,2,2,3,4,5])
sage: D.list()[:5]
[[2, 2, 1, 1, 4, 5, 3], [2, 2, 1, 1, 5, 3, 4], [2, 2, 1, 3, 1, 5, 4], [2, 2, 1, 3, 4, 5, 1], [2, 2, 1, 3, 5, 1, 4]]

还有一些更先进的，在这个例子中，对称多项式。

sage: s = SymmetricFunctions(QQ).schur()
sage: a = s([2,1])
sage: a.expand(3)
x0^2*x1 + x0*x1^2 + x0^2*x2 + 2*x0*x1*x2 + x1^2*x2 + x0*x2^2 + x1*x2^2

与此相关的各种功能也可用。

sage: binomial(25,3)
2300

sage: multinomial(24,3,5)
589024800

sage: falling_factorial(10,4)
5040

你认识这个著名的身份吗？

sage: var('k,n')
(k, n)
sage: sum(binomial(n,k),k,0,n)
2^n

密码学（教育用）

这在 Number theory quickstart . Sage在密码学方面有许多很好的教学资源。

sage: # Two objects to make/use encryption scheme
sage: #
sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: bin = BinaryStrings()
sage: #
sage: # Convert English to binary
sage: #
sage: P = bin.encoding("Encrypt this using S-DES!")
sage: print("Binary plaintext:  {}\n".format(P))
sage: #
sage: # Choose a random key
sage: #
sage: K = sdes.list_to_string(sdes.random_key())
sage: print("Random key:  {}\n".format(K))
sage: #
sage: # Encrypt with Simplified DES
sage: #
sage: C = sdes(P, K, algorithm="encrypt")
sage: print("Encrypted:  {}\n".format(C))
sage: #
sage: # Decrypt for the round-trip
sage: #
sage: plaintxt = sdes(C, K, algorithm="decrypt")
sage: print("Decrypted:  {}\n".format(plaintxt))
sage: #
sage: # Verify easily
sage: #
sage: print("Verify encryption/decryption: {}".format(P == plaintxt))
Binary plaintext:  01000101011011100110001101110010011110010111000001110100001000000111010001101000011010010111001100100000011101010111001101101001011011100110011100100000010100110010110101000100010001010101001100100001

Random key:  0100000011

Encrypted:  00100001100001010011000111000110010000011011101011111011100011011111101111110111110010101000010010001101101010101000010011001010100001010111000010001101000011001001111111110100001000010000110001011000

Decrypted:  01000101011011100110001101110010011110010111000001110100001000000111010001101000011010010111001100100000011101010111001101101001011011100110011100100000010100110010110101000100010001010101001100100001

Verify encryption/decryption:  True

编码理论

下面是一个线性二进制代码（组码）的简单示例。

从生成矩阵开始 \(\ZZ/2\ZZ\) .

sage: G = matrix(GF(2), [[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)

sage: C.is_self_dual()
False

sage: D = C.dual_code()
sage: D
[7, 3] linear code over GF(2)

sage: D.basis()
[
(1, 0, 1, 0, 1, 0, 1),
(0, 1, 1, 0, 0, 1, 1),
(0, 0, 0, 1, 1, 1, 1)
]

sage: D.permutation_automorphism_group()
Permutation Group with generators [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)]