首页 › 智能体/知识库 › 多智能体协同控制(2):代数图论

百花深处宝 發表於 2024-9-23 15:25:00

多智能体协同控制(2):代数图论

<p data-first-child="" data-pid="3pH-C_nk">在上一节中，提到了<strong>分布式一致性算法的实现与多智能体之间的交流方式密切相关</strong>。这一节用<strong>图论</strong>来揭示不同多智能体之间交流方式的本质差异。</p>
<p data-pid="J6VSv8Pl"><strong><em>图的基本定义</em></strong></p>
<p data-pid="duXwQYAy">我们可以将不同智能体之间的通信方式，抽象出来，称为“<strong>通信图</strong>”（graph）。</p>
<figure data-size="small">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="554" width="918" data-rawwidth="918" data-rawheight="554" data-size="normal" data-caption="" data-original="https://pic4.zhimg.com/v2-a90c4ae11dfcf240e90d535ae44f84b1_r.jpg" data-actualsrc="https://pic4.zhimg.com/v2-a90c4ae11dfcf240e90d535ae44f84b1_b.jpg" data-original-token="v2-c184fa4b33c8b07bcbbff8dacfed6e9c" data-lazy-status="ok" data-src="https://pic4.zhimg.com/80/v2-a90c4ae11dfcf240e90d535ae44f84b1_1440w.webp"></div>
</figure>
<p data-pid="hoxUk-XO">如右图所示，舍弃物理意义，将每个智能体抽象成<strong>节点</strong>（vertex）1,、2、3、4。 一张图中所有<strong>节点的集合</strong>记为：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="V=\left\{ v_1,v_2,...,v_N \right\} "><span id="MathJax-Element-1-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;V&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">V={v1,v2,...,vN}</span></span></span></p>
<figure data-size="small">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="240" width="687" data-rawwidth="687" data-rawheight="240" data-size="normal" data-caption="" data-original="https://pic3.zhimg.com/v2-8e7c9cc44a1dc17bf136d3a6894f2036_r.jpg" data-actualsrc="https://pic3.zhimg.com/v2-8e7c9cc44a1dc17bf136d3a6894f2036_b.jpg" data-original-token="v2-371ac7ba5ba9e0b6cd9e63e516dd6243" data-lazy-status="ok" data-src="https://pic3.zhimg.com/80/v2-8e7c9cc44a1dc17bf136d3a6894f2036_1440w.webp"></div>
</figure>
<p data-pid="w5GbCpOf">用上图中箭头表示通信方式。圆点表示<strong>尾巴</strong>（tail），箭头表示<strong>头部</strong>（head），直线表示<strong>边</strong>（edge）。可以用&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="e_{12}=\left( v_1,v_2 \right) "><span id="MathJax-Element-2-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;e&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;12&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">e12=(v1,v2)</span></span></span>&nbsp;来表示边，它的含义是：<strong>节点1（母节点）发送信息给节点2（子节点），节点2接收来自节点1的信息</strong>。对于节点2来说，节点1就是它的邻居（neighbor）。信息在传输过程中，可能被扭曲：放大或缩小。因此在每条边上添加一个<strong>权重系数</strong>&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ij}"><span id="MathJax-Element-3-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aij</span></span></span>&nbsp;，注意，下标i为子节点，下标j为母节点，所以上图中记为&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{21}"><span id="MathJax-Element-5-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;21&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">a21</span></span></span>&nbsp;。图中所有边的集合记为：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="E"><span id="MathJax-Element-4-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;E&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">E</span></span></span>&nbsp;。</p>
<p data-pid="oFhJBOWI">对于节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-6-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;来说，它可能会接收来自不同邻居（母节点）的信息，这些邻居构成节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-7-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的<strong>邻居集合</strong>：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="N_i=\left\{ v_j|\left( v_j,v_i \right) \in E \right\} "><span id="MathJax-Element-8-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/msub&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2208;&lt;/mo&gt;&lt;mi&gt;E&lt;/mi&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">Ni={vj|(vj,vi)∈E}</span></span></span>&nbsp;，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="|N_i|"><span id="MathJax-Element-9-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">|Ni|</span></span></span>&nbsp;表示节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-10-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的邻居的个数，又称为节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-12-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的<strong>入度</strong>（in-degree）；同样它也会发送信息给其他节点（子节点），子节点的个数称为节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-11-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的<strong>出度</strong>（out-degree）。</p>
<p data-pid="oQElafE-">如果Graph（后简写为G）中任意节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-13-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的入度和出度相等，则把G称为<strong>平衡图</strong>（balanced graph）。</p>
<figure data-size="small">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="267" width="740" data-rawwidth="740" data-rawheight="267" data-size="normal" data-caption="" data-original="https://picx.zhimg.com/v2-1a0ed5619ba78d95158b8f52f607b689_r.jpg" data-actualsrc="https://picx.zhimg.com/v2-1a0ed5619ba78d95158b8f52f607b689_b.jpg" data-original-token="v2-281feab655d2f623e9748181a6662db0" data-lazy-status="ok" data-src="https://picx.zhimg.com/80/v2-1a0ed5619ba78d95158b8f52f607b689_1440w.webp"></div>
</figure>
<p data-pid="gMMu7mS7">如果任意两个节点之间的通信是相互的：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\left( v_i,v_j \right) \in E\Longrightarrow \left( v_j,v_i \right) \in E"><span id="MathJax-Element-14-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2208;&lt;/mo&gt;&lt;mi&gt;E&lt;/mi&gt;&lt;mo stretchy=&quot;false&quot;&gt;&amp;#x27F9;&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2208;&lt;/mo&gt;&lt;mi&gt;E&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">(vi,vj)∈E⟹(vj,vi)∈E</span></span></span>&nbsp;，如上图所示，则称G为<strong>双向图</strong>（bidirectional）；否则称G为<strong>有向图</strong>（directed）。</p>
<p data-pid="WQtMti7j">在双向图的基础上，如果有权重系数&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ij}=a_{ji}"><span id="MathJax-Element-15-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aij=aji</span></span></span>&nbsp;，则称G为<strong>无向图</strong>。节点之间可用一条直线连接。</p>
<figure data-size="small">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="192" width="645" data-rawwidth="645" data-rawheight="192" data-size="normal" data-caption="" data-original="https://picx.zhimg.com/v2-ff38663bf272f14867dbfe26647ea89f_r.jpg" data-actualsrc="https://picx.zhimg.com/v2-ff38663bf272f14867dbfe26647ea89f_b.jpg" data-original-token="v2-a877c4658feca00eac0f523cc8099b31" data-lazy-status="ok" data-src="https://picx.zhimg.com/80/v2-ff38663bf272f14867dbfe26647ea89f_1440w.webp"></div>
</figure>
<p data-pid="fIPGlfwP">如果从某个节点出发，能够遍历所有节点，则称G有生成树（spanning tree）。<strong>有生成树是实现控制算法</strong>的必要条件。</p>
<hr>
<p data-pid="ZR_i3m9S"><strong>图矩阵</strong></p>
<p data-pid="Jsao3xuz">一张图G的的结构和属性可以通过研究与G相关的矩阵来揭示，也就是<strong>代数图论</strong>（algebraic graph theory）。</p>
<p data-pid="e3IyEfDb">一个N节点的G中边的权重系数&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ij}"><span id="MathJax-Element-17-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aij</span></span></span>&nbsp;可以构成一个邻接矩阵（adjacency matrix）：</p>
<p data-pid="iuVqU_da"><span class="ztext-math" data-eeimg="1" data-tex="A=\left[ \begin{matrix} a_{11}&amp;a_{12}&amp; \cdots&amp; a_{1N}\\ a_{21}&amp; \ddots&amp; &amp;\vdots\\ \vdots&amp; &amp; \ddots&amp;\vdots\\ a_{N1}&amp; a_{N2}&amp;\cdots&amp; a_{NN}\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-16-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;A&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;11&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;12&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;21&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22EE;&lt;/mo&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22EE;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22EE;&lt;/mo&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">A=</span></span></span></span></p>
<p data-pid="mM64G3J9">若&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\left( v_j,v_i \right) \in E"><span id="MathJax-Element-20-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2208;&lt;/mo&gt;&lt;mi&gt;E&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">(vj,vi)∈E</span></span></span>&nbsp;，则&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ij}&gt;0"><span id="MathJax-Element-19-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;&amp;gt;&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aij&gt;0</span></span></span>&nbsp;；否则&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ij}=0"><span id="MathJax-Element-18-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aij=0</span></span></span>&nbsp;。默认每个节点知道自己的信息，不需要和自己通信，则对角元素&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{ii}=0"><span id="MathJax-Element-21-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">aii=0</span></span></span>&nbsp;。</p>
<p data-pid="1OI4sBf7">定义节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-22-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;的加权入度（weighted in-degree）为A的第i行所有元素之和：</p>
<p data-pid="MyAa2Hkg"><span class="ztext-math" data-eeimg="1" data-tex="d_i=\sum_{j=1}^N{a_{ij}}\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-23-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;munderover&gt;&lt;mo&gt;&amp;#x2211;&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/munderover&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">di=∑j=1Naij</span></span></span></span>定义节点<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-24-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>的加权出度（weighted out-degree）为A的第i列所有元素之和：</p>
<p data-pid="aAlBrddL"><span class="ztext-math" data-eeimg="1" data-tex="d_{i}^{o}=\sum_{j=1}^N{a_{ji}}\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-25-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;msubsup&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;o&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;munderover&gt;&lt;mo&gt;&amp;#x2211;&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/munderover&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">dio=∑j=1Naji</span></span></span></span></p>
<p data-pid="9hyE0aF2">在文献中，通常将节点&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-26-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;简称为节点i，并且直接使用入度、出度等概念，省略“加权”。</p>
<p class="ztext-empty-paragraph">&nbsp;</p>
<p data-pid="qvrWVehZ"><strong>L矩阵</strong></p>
<p data-pid="OCsTHHPG">接下来介绍的<strong>拉普拉斯矩阵</strong>(Laplacian matrix)，简称为<strong>L矩阵</strong>。在后续的内容中，我们将会看到L矩阵在多智能体系统中<strong>举足轻重</strong>的地位。</p>
<p data-pid="tbjI6Q95">首先定义入度矩阵&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="D=\mathrm{diag}\left\{ d_i \right\} "><span id="MathJax-Element-29-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;d&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;i&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;a&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;g&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">D=diag{di}</span></span></span>&nbsp;，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\mathrm{diag}\left\{ d_i \right\} "><span id="MathJax-Element-27-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;d&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;i&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;a&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;g&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">diag{di}</span></span></span>&nbsp;表示以元素&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="d_i"><span id="MathJax-Element-28-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">di</span></span></span>&nbsp;作为主对角线元素的对角矩阵。</p>
<p data-pid="mwk2FxV0">L矩阵定义为：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="L=D-A"><span id="MathJax-Element-30-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;A&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">L=D−A</span></span></span>&nbsp;。</p>
<p data-pid="BjS-GlLk">用一个小栗子来更好的理解D矩阵和L矩阵。</p>
<figure data-size="normal">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="704" width="1844" data-rawwidth="1844" data-rawheight="704" data-size="normal" data-caption="" data-original="https://pic4.zhimg.com/v2-7bedf334507a5ab7ad5b2ba081b1e71d_r.jpg" data-actualsrc="https://pic4.zhimg.com/v2-7bedf334507a5ab7ad5b2ba081b1e71d_b.jpg" data-original-token="v2-b727bef9fd9dc462341d6e515c1fde43" data-lazy-status="ok" data-src="https://pic4.zhimg.com/80/v2-7bedf334507a5ab7ad5b2ba081b1e71d_1440w.webp"></div>
</figure>
<p data-pid="W3Y1p7Iq">上图中一共有N=6个节点，每条边的权重系数取为1。右图显示了这个G的生成树：节点1的信息，可分别通过1-2-4和1-3-5-6传达到G中的所有节点。</p>
<p data-pid="F8sY3Pyf">G的邻接矩阵A根据图写出：</p>
<p data-pid="-Vx-IDQ2"><span class="ztext-math" data-eeimg="1" data-tex="A=\left[ a_{ij} \right] =\left[ \begin{matrix}{} 0&amp; 0&amp;1&amp; 0&amp; 0&amp; 0\\ 1&amp;0&amp; 0&amp; 0&amp; 0&amp; 1\\ 1&amp; 1&amp; 0&amp; 0&amp; 0&amp;0\\ 0&amp; 1&amp; 0&amp; 0&amp;0&amp; 0\\ 0&amp; 0&amp; 1&amp;0&amp; 0&amp; 0\\ 0&amp; 0&amp;0&amp; 1&amp; 1&amp;0\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-31-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;A&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;/mrow&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">A==</span></span></span></span></p>
<p data-pid="2IcXUIyn">由于节点1只接收来自节点3的信息，因此第一行只有&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{13}=1"><span id="MathJax-Element-32-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;13&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">a13=1</span></span></span>&nbsp;，其余元素均为0；</p>
<p data-pid="3r1gJuUG">节点2接收来自节点1和节点6的信息，因此第二行中，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="a_{21}=1,a_{26}=1"><span id="MathJax-Element-33-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;21&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;26&lt;/mn&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">a21=1,a26=1</span></span></span>&nbsp;，其余元素为0。其他类似写出。</p>
<p data-pid="qB7i28at">根据对角入度矩阵D的定义：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="d_i=\sum_{j=1}^N{a_{ij}}"><span id="MathJax-Element-34-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;munderover&gt;&lt;mo&gt;&amp;#x2211;&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/munderover&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;msub&gt;&lt;mi&gt;a&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;mi&gt;j&lt;/mi&gt;&lt;/mrow&gt;&lt;/msub&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">di=∑j=1Naij</span></span></span>&nbsp;以及&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="D=\mathrm{diag}\left\{ d_i \right\} "><span id="MathJax-Element-35-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;d&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;i&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;a&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;g&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">D=diag{di}</span></span></span>&nbsp;，可以得出</p>
<p data-pid="72BDex1N"><span class="ztext-math" data-eeimg="1" data-tex="D=\mathrm{diag}\left\{ d_i \right\} =\left[ \begin{matrix}{} 1&amp; 0&amp;0&amp; 0&amp; 0&amp; 0\\ 0&amp;2&amp; 0&amp; 0&amp; 0&amp; 0\\ 0&amp; 0&amp; 2&amp; 0&amp; 0&amp;0\\ 0&amp; 0&amp; 0&amp; 1&amp;0&amp; 0\\ 0&amp; 0&amp; 0&amp;0&amp; 1&amp; 0\\ 0&amp; 0&amp;0&amp; 0&amp; 0&amp;2\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-36-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;d&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;i&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;a&lt;/mi&gt;&lt;mi mathvariant=&quot;normal&quot;&gt;g&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow&gt;&lt;mo&gt;{&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;d&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;}&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;/mrow&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">D=diag{di}=</span></span></span></span></p>
<p data-pid="vGoqJslX">根据定义&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="L=D-A"><span id="MathJax-Element-37-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;A&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">L=D−A</span></span></span>&nbsp;，有L矩阵：</p>
<p data-pid="PCfMKsvs"><span class="ztext-math" data-eeimg="1" data-tex="L=D-A=\left[ \begin{matrix}{} \,\, 1&amp;\,\, 0&amp; -1&amp; \,\, 0&amp; \,\, 0&amp; \,\, 0\\ -1&amp; \,\, 2&amp; \,\, 0&amp; \,\, 0&amp; \,\, 0&amp; -1\\ -1&amp;-1&amp; \,\, 2&amp; \,\, 0&amp; \,\, 0&amp; \,\, 0\\ \,\, 0&amp; -1&amp; \,\, 0&amp; \,\, 1&amp; \,\, 0&amp; \,\, 0\\ \,\, 0&amp; \,\, 0&amp; -1&amp; \,\, 0&amp; \,\, 1&amp; \,\, 0\\ \,\, 0&amp;\,\, 0&amp; \,\, 0&amp; -1&amp; -1&amp;\,\, 2\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-38-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mi&gt;D&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;A&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;/mrow&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">L=D−A=</span></span></span></span></p>
<p data-pid="IjsThQVF">可以看出，L矩阵的每一行所有元素之和为0，即行和为0。</p>
<hr>
<p data-pid="iOUOGa4H"><strong>L矩阵的特征值与特征向量</strong></p>
<p data-pid="fysZ5Q0n">在线性代数和矩阵论中，矩阵的特征值和特征向量都是最为核心的内容，他们在分析动态系统时至关重要。这里简单地列一下，具体的可以参考教科书。</p>
<p data-pid="sBCG8eZp">在线性代数中，我们学过：对于一个n阶方阵L，如果它有n个相异特征根&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _1,...\lambda _n"><span id="MathJax-Element-39-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;,&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;mo&gt;.&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;n&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ1,...λn</span></span></span>&nbsp;，则一定可以找到一个矩阵P，将L对角化：</p>
<p data-pid="HvdDe-wB"><span class="ztext-math" data-eeimg="1" data-tex="P^{-1}LP=\left[ \begin{matrix} \lambda _1&amp; &amp; &amp; \\ &amp;\lambda _2&amp; &amp; \\ &amp;&amp; \ddots&amp; \\ &amp; &amp;&amp; \lambda _n\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-40-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;msup&gt;&lt;mi&gt;P&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;/msup&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mi&gt;P&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;n&lt;/mi&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">P−1LP=[λ1λ2⋱λn]</span></span></span></span></p>
<p data-pid="m4WVNbEZ">如果某个特征根有重根，则不能找到这样的矩阵P，将L对角化。</p>
<p data-pid="cq3H8mqb">但在矩阵论中，我们又学到：如果矩阵L的所有元素都是实数，则一定可以把它化简成约当(Jordan)标准型:</p>
<p data-pid="rc-mB4wR"><span class="ztext-math" data-eeimg="1" data-tex="J=M^{-1}LM\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-41-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;J&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;msup&gt;&lt;mi&gt;M&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;/msup&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mi&gt;M&lt;/mi&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">J=M−1LM</span></span></span></span></p>
<p data-pid="29p53VXH"><span class="ztext-math" data-eeimg="1" data-tex="M=\left[ v_1\,\,v_2\,\,\cdots \,\,v_N \right] "><span id="MathJax-Element-43-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;M&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">M=</span></span></span>&nbsp;为右特征向量组成的矩阵，特征值&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _i"><span id="MathJax-Element-42-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λi</span></span></span>&nbsp;与特征向量&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_i"><span id="MathJax-Element-48-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">vi</span></span></span>&nbsp;满足关系：</p>
<p data-pid="9hbjDkVX"><span class="ztext-math" data-eeimg="1" data-tex="\left( \lambda _iI-L \right) v_i=0\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-46-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mi&gt;I&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">(λiI−L)vi=0</span></span></span></span>其中，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="I"><span id="MathJax-Element-44-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;I&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">I</span></span></span>&nbsp;为单位阵。</p>
<p data-pid="cPvv9woi"><span class="ztext-math" data-eeimg="1" data-tex="M^{-1}=\left[ w_{1}^{T}\,\,w_{2}^{T}\,\,\cdots \,\,w_{N}^{T} \right] ^T"><span id="MathJax-Element-49-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msup&gt;&lt;mi&gt;M&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;/msup&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;msup&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;mspace width=&quot;thinmathspace&quot; /&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/msup&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">M−1=T</span></span></span>&nbsp;为左特征向量组成的矩阵，特征值&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _i"><span id="MathJax-Element-45-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λi</span></span></span>&nbsp;与特征向量&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="w_{i}^{T}"><span id="MathJax-Element-47-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">wiT</span></span></span>&nbsp;满足关系：</p>
<p data-pid="UHGvkcgw"><span class="ztext-math" data-eeimg="1" data-tex="w_{i}^{T}\left( \lambda _iI-L \right) =0\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-50-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mi&gt;I&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">wiT(λiI−L)=0</span></span></span></span></p>
<p data-pid="TDw7qeAW">其中&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="w_{i}^{T}"><span id="MathJax-Element-51-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">wiT</span></span></span>&nbsp;是标准化的，即有&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="w_{i}^{T}v_i=1"><span id="MathJax-Element-52-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msubsup&gt;&lt;mi&gt;w&lt;/mi&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/mrow&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/mrow&gt;&lt;/msubsup&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">wiTvi=1</span></span></span>&nbsp;。</p>
<p data-pid="Hm0OU0Yp">Jordan矩阵为：</p>
<p data-pid="1xZzdpDJ"><span class="ztext-math" data-eeimg="1" data-tex="J=\left[ \begin{matrix} \lambda _1&amp;&amp; &amp; \\ &amp; \lambda _2&amp; &amp; \\ &amp; &amp;\ddots&amp; \\ &amp; &amp; &amp;\lambda _N\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-53-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;J&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">J=[λ1λ2⋱λN]</span></span></span></span></p>
<p data-pid="MIj9ftnh">此时对角元素&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _i"><span id="MathJax-Element-54-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λi</span></span></span>&nbsp;不是标量，而是一个Jordan块：</p>
<p data-pid="qoAS_7Ng"><span class="ztext-math" data-eeimg="1" data-tex="\left[ \begin{matrix} \lambda _i&amp;1&amp; &amp; \\ &amp; \lambda _i&amp; \ddots&amp; \\ &amp; &amp;\ddots&amp; 1\\ &amp; &amp; &amp;\lambda _i\\\end{matrix} \right] \\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-55-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mtable rowspacing=&quot;4pt&quot; columnspacing=&quot;1em&quot;&gt;&lt;mtr&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd /&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;mo&gt;&amp;#x22F1;&lt;/mo&gt;&lt;/mtd&gt;&lt;mtd&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;mtr&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd /&gt;&lt;mtd&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;/mtd&gt;&lt;/mtr&gt;&lt;/mtable&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">[λi1λi⋱⋱1λi]</span></span></span></span></p>
<p data-pid="3zGJek0G">很明显，Jordan标准型是更一般的矩阵对角化形式，建议仔细地阅读矩阵论的相关章节。</p>
<p data-pid="5O8VnYh5">此处，并不进一步展开。为了便于讨论，我们假设L矩阵的特征值都是互异的，因为相应的结论容易推广到Jordan标准型下。</p>
<p data-pid="swpRDWjF">设L矩阵的特征值按序排列为：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="|\lambda _1|\leqslant |\lambda _2|\leqslant \cdots |\lambda _N|"><span id="MathJax-Element-56-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2A7D;&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;mo&gt;&amp;#x2A7D;&lt;/mo&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msub&gt;&lt;mrow class=&quot;MJX-TeXAtom-ORD&quot;&gt;&lt;mo stretchy=&quot;false&quot;&gt;|&lt;/mo&gt;&lt;/mrow&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">|λ1|⩽|λ2|⩽⋯|λN|</span></span></span>&nbsp;。对于无向图，有&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="L=L^T"><span id="MathJax-Element-57-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;msup&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/msup&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">L=LT</span></span></span>&nbsp;，则所有特征值都是实数，可以排列为：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _1\leqslant \lambda _2\leqslant \cdots \lambda _N"><span id="MathJax-Element-58-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;&amp;#x2A7D;&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;2&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;&amp;#x2A7D;&lt;/mo&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msub&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ1⩽λ2⩽⋯λN</span></span></span>&nbsp;。</p>
<hr>
<p data-pid="dzO1FbJJ">前面说到L矩阵的行和为0，则<span class="ztext-math" data-eeimg="1" data-tex="L\underline{1}c=0\\"><span class="MathJax_SVG_Display"><span id="MathJax-Element-60-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;munder&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;&amp;#x005F;&lt;/mo&gt;&lt;/munder&gt;&lt;mi&gt;c&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;mspace linebreak=&quot;newline&quot; /&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation">L1_c=0</span></span></span></span>其中&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\underline{1}=\left[ 1\cdots 1 \right] ^T\in R^N"><span id="MathJax-Element-59-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;munder&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;&amp;#x005F;&lt;/mo&gt;&lt;/munder&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;msup&gt;&lt;mrow&gt;&lt;mo&gt;[&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;&amp;#x22EF;&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;]&lt;/mo&gt;&lt;/mrow&gt;&lt;mi&gt;T&lt;/mi&gt;&lt;/msup&gt;&lt;mo&gt;&amp;#x2208;&lt;/mo&gt;&lt;msup&gt;&lt;mi&gt;R&lt;/mi&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/msup&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">1_=T∈RN</span></span></span>&nbsp;，c为任意非零常数。</p>
<p data-pid="H4DzXN6o">根据特征值的定义：&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\left( \lambda _iI-L \right) v_i=0"><span id="MathJax-Element-63-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mrow&gt;&lt;mo&gt;(&lt;/mo&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mi&gt;I&lt;/mi&gt;&lt;mo&gt;&amp;#x2212;&lt;/mo&gt;&lt;mi&gt;L&lt;/mi&gt;&lt;mo&gt;)&lt;/mo&gt;&lt;/mrow&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mi&gt;i&lt;/mi&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">(λiI−L)vi=0</span></span></span>&nbsp;，可知L矩阵一定有一个特征值&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _1=0"><span id="MathJax-Element-61-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ1=0</span></span></span>&nbsp;，对应的特征向量为&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="v_1=\underline{1}c"><span id="MathJax-Element-62-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;v&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;munder&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;&amp;#x005F;&lt;/mo&gt;&lt;/munder&gt;&lt;mi&gt;c&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">v1=1_c</span></span></span>&nbsp;。</p>
<p data-pid="emNHii75"><strong>定理1：</strong>如果图G有生成树，则L的秩为N-1，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _1=0"><span id="MathJax-Element-64-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ1=0</span></span></span>&nbsp;有且仅有一个，相应的右特征向量为&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\underline{1}c"><span id="MathJax-Element-65-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;munder&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;mo&gt;&amp;#x005F;&lt;/mo&gt;&lt;/munder&gt;&lt;mi&gt;c&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">1_c</span></span></span>&nbsp;。</p>
<hr>
<p data-pid="OaNkSyDw">我们来看一个例子，更好地理解不同图拓扑下，L矩阵特征值的分布情况。</p>
<figure data-size="normal">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="1360" width="1682" data-rawwidth="1682" data-rawheight="1360" data-size="normal" data-caption="" data-original="https://pic4.zhimg.com/v2-1281c84f1e6ce1b399c47a7882191311_r.jpg" data-actualsrc="https://pic4.zhimg.com/v2-1281c84f1e6ce1b399c47a7882191311_b.jpg" data-original-token="v2-1011d23f860d96a059be55ac2059de73" data-lazy-status="ok" data-src="https://pic4.zhimg.com/80/v2-1281c84f1e6ce1b399c47a7882191311_1440w.webp"></div>
</figure>
<p data-pid="wcuQ9iou">在matlab中分别计算出每幅图的L矩阵，用<strong>eig指令</strong>计算出L矩阵的特征值。</p>
<p data-pid="U5gogL_o"><strong>详细代码见最后。</strong></p>
<p data-pid="sPe3wTeC">根据计算结果，可以列出9幅图的特征值为：</p>
<figure data-size="normal">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="453" width="1427" data-rawwidth="1427" data-rawheight="453" data-size="normal" data-caption="" data-original="https://pic3.zhimg.com/v2-241f1af50fdc068cebca1290a86466c4_r.jpg" data-actualsrc="https://pic3.zhimg.com/v2-241f1af50fdc068cebca1290a86466c4_b.jpg" data-original-token="v2-c46f55c7cac8134315baf2c2fbbb4063" data-lazy-status="ok" data-src="https://pic3.zhimg.com/80/v2-241f1af50fdc068cebca1290a86466c4_1440w.webp"></div>
</figure>
<p data-pid="HDmorkCM">同样可以在复平面上绘制出特征值的分布情况，如下图：</p>
<figure data-size="normal">
<div><img class="origin_image zh-lightbox-thumb lazy lazyload" height="1147" width="2090" data-rawwidth="2090" data-rawheight="1147" data-size="normal" data-caption="" data-original="https://pic4.zhimg.com/v2-5cea73dbd1072684b13127e5e1b8f7ab_r.jpg" data-actualsrc="https://pic4.zhimg.com/v2-5cea73dbd1072684b13127e5e1b8f7ab_b.jpg" data-original-token="v2-be0b2e0ee5a84bb02784edb2359c44e1" data-lazy-status="ok" data-src="https://pic4.zhimg.com/80/v2-5cea73dbd1072684b13127e5e1b8f7ab_1440w.webp"></div>
</figure>
<p data-pid="E-gqDvNu">观察上表与上图，可以得出以下结论：</p>
<p data-pid="lSiG6gAt">①由于L矩阵行和为0，所有图的第一个特征值都为0，&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda _1=0"><span id="MathJax-Element-66-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;msub&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/msub&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;0&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ1=0</span></span></span>&nbsp;；</p>
<p data-pid="InqWffdh">②对于所有无向图（b,c,e,g,i）,所有特征值都是实数；</p>
<p data-pid="UuwfwK2G">③N节点完全图（c）的所有非零特征值为&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda =N"><span id="MathJax-Element-67-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mi&gt;N&lt;/mi&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ=N</span></span></span>&nbsp;；</p>
<p data-pid="AC_34gma">④有向树（d,f）的所有非零特征值为&nbsp;<span class="ztext-math" data-eeimg="1" data-tex="\lambda =1"><span id="MathJax-Element-68-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0; position: relative" tabindex="0" role="presentation" data-mathml="&lt;math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;&gt;&lt;mi&gt;&amp;#x03BB;&lt;/mi&gt;&lt;mo&gt;=&lt;/mo&gt;&lt;mn&gt;1&lt;/mn&gt;&lt;/math&gt;"><span class="MJX_Assistive_MathML" role="presentation">λ=1</span></span></span>&nbsp;；</p>
<p data-pid="DtA4TU4y">⑤有向N循环图的N个特征值均匀分布在以（1,0）为圆心，1为半径的圆上，且第一个特征值为0；</p>
<p data-pid="YIN_GABT"><strong>从下一节开始，将正式进入多智能体协同控制算法的介绍。做好面对数学疾风的准备吧。</strong></p>
<hr>
<p data-pid="F2i8Iz_g"><strong>详细代码：</strong></p>
<div class="highlight">
<pre class="highlighter-hljs"><code>clear;clc

%% 图a的特征值L矩阵之前已经算出来了
La = [ 10-1000;...
      -12   000 -1;...
      -1 -1   2000;...
       0 -1   0100;...
       00-1010;...
       00   0 -1 -12];
lambda_a = eig(La);

%% 图b的特征值
Ab = [ 01   1000;...
       10   1101;...
       11   0010;...
       01   0001;...
       00   1001;...
       01   0110];
   
Db = diag(sum(Ab'));% 取转置 是因为matlab默认对矩阵按列进行求和，而我们需要对行求和
Lb = Db - Ab;
lambda_b = eig(Lb);
   
%% 图c的特征值
Ac = [ 01   1111;...
       10   1111;...
       11   0111;...
       11   1011;...
       11   1101;...
       11   1110];
   
Dc = diag(sum(Ac'));
Lc = Dc - Ac;
lambda_c = eig(Lc);   
   
   
%% 图d的特征值
Ad = [ 00   0000;...
       10   0000;...
       10   0000;...
       01   0000;...
       00   1000;...
       00   1000];
   
Dd = diag(sum(Ad'));
Ld = Dd - Ad;
lambda_d = eig(Ld);   
         
%% 图e的特征值
Ae = [ 01   1111;...
       10   0000;...
       10   0000;...
       10   0000;...
       10   0000;...
       10   0000];
   
De = diag(sum(Ae'));
Le = De - Ae;
lambda_e = eig(Le);   
      
   
%% 图f的特征值
Af = [ 00   0000;...
       10   0000;...
       10   0000;...
       10   0000;...
       10   0000;...
       10   0000];
   
Df = diag(sum(Af'));
Lf = Df - Af;
lambda_f = eig(Lf);      


%% 图g的特征值
Ag = [ 01   0001;...
       10   1000;...
       01   0100;...
       00   1010;...
       00   0101;...
       10   0010];
   
Dg = diag(sum(Ag'));
Lg = Dg - Ag;
lambda_g = eig(Lg);

%% 图h的特征值
Ah = [ 00   0001;...
       10   0000;...
       01   0000;...
       00   1000;...
       00   0100;...
       00   0010];
   
Dh = diag(sum(Ah'));
Lh = Dh - Ah;
lambda_h = eig(Lh);

%% 图i的特征值
Ai = [ 01   0000;...
       10   1000;...
       01   0100;...
       00   1010;...
       00   0101;...
       00   0010];
   
Di = diag(sum(Ai'));
Li = Di - Ai;
lambda_i = eig(Li);

%% 绘制特征值分布图
figure
hf = gcf;
hf.Color= ; % 控制图形的整体颜色。（scope中被默认为灰黑色，此处修改为白色）
subplot(3,3,1)
plot(real(lambda_a),imag(lambda_a),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('a')

subplot(3,3,2)
plot(real(lambda_b),imag(lambda_b),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('b')

subplot(3,3,3)
plot(real(lambda_c),imag(lambda_c),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('c')


subplot(3,3,4)
plot(real(lambda_d),imag(lambda_d),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('d')


subplot(3,3,5)
plot(real(lambda_e),imag(lambda_e),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('e')

subplot(3,3,6)
plot(real(lambda_f),imag(lambda_f),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('f')

subplot(3,3,7)
plot(real(lambda_g),imag(lambda_g),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('g')
   
subplot(3,3,8)
plot(real(lambda_h),imag(lambda_h),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('h')

subplot(3,3,9)
plot(real(lambda_i),imag(lambda_i),'r*')
grid on
xlabel('实部')
ylabel('虚部')
title('i')</code></pre>
</div><br><br>
来源：https://www.cnblogs.com/zhangxianrong/p/18427130

查看完整版本: 多智能体协同控制(2):代数图论