图中的行走

本节提供了斯坦利书第一章的一些例子 [Stanley2013].

我们首先创建一个有4个顶点的图：

sage: G = Graph(4)
sage: G
Graph on 4 vertices

这张图还没有边：

sage: G.vertices()
[0, 1, 2, 3]
sage: G.edges()
[]

在添加边之前，我们需要告诉Sage我们的图可以有循环和多个边

sage: G.allow_loops(True)
sage: G.allow_multiple_edges(True)

现在，我们可以通过指定由一条边连接的顶点元组来添加边。如果存在多条边，则需要添加具有多重性的元组。：：

sage: G.add_edges([(0,0),(0,0),(0,1),(0,3),(1,3),(1,3)])

现在让我们看看图表！:

sage: G.plot()
Graphics object consisting of 11 graphics primitives
thematic_tutorials/algebraic_combinatorics/../media/graph.png

我们可以构造邻接矩阵：

sage: A = G.adjacency_matrix()
sage: A
[2 1 0 1]
[1 0 0 2]
[0 0 0 0]
[1 2 0 0]

行中的条目 i 和列 j 的 ell -的次方 A 给出了路径的长度 ell 从顶点 i 到顶点 j . 让我们验证一下：

sage: A**2
[6 4 0 4]
[4 5 0 1]
[0 0 0 0]
[4 1 0 5]

从顶点有4条长度为2的路径 0 到顶点 1 ：在 0 然后是边缘 (0, 1) （2个选择）或采取优势 (0, 3) 然后是两个边中的任何一个 (3, 1) （两种选择）：

sage: (A**2)[0,1]
4

为了计算封闭行走的次数，我们还可以看看 ell -特征值的次幂。即使特征值不是整数，我们发现它们的平方和是整数：

sage: A.eigenvalues()
[0, -2, 0.5857864376269049?, 3.414213562373095?]
sage: sum(la**2 for la in A.eigenvalues())
16.00000000000000?

我们可以通过观察 ell -矩阵的次幂：

sage: (A**2).trace()
16