设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的结点是由所有0和1的有序[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组所组成，两个结点相邻当且仅当对应的两个有序[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组有一个坐标不相同，这样的图称为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图。试证明[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图有[tex=0.929x1.214]K4h+M94mGh2tzbuD4aMPBQ==[/tex]个结点，有[tex=3.071x1.214]+4r++Be+q7J+TIKf8LTG/Q==[/tex]条边且是一个二部图。

2022-07-01

设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的结点是由所有0和1的有序[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组所组成，两个结点相邻当且仅当对应的两个有序[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组有一个坐标不相同，这样的图称为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图。试证明[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图有[tex=0.929x1.214]K4h+M94mGh2tzbuD4aMPBQ==[/tex]个结点，有[tex=3.071x1.214]+4r++Be+q7J+TIKf8LTG/Q==[/tex]条边且是一个二部图。

答案：

分析：本题中图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是一种二元[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体结构，可以作为超级计算机静态连接网络的拓扑结构。这种结构的连接比较密集，但缺乏可扩展性难于组成高维超立方体。证明：因为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图的结点为所有的有序[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组，可设[tex=18.643x1.286]R7wEzKOeHFkdyMSlwQ55/X72kBJT/BVN+JUIPysL8oBZgbYrMkflNQlG15tHK9WiFl7c8PEGap8XXI31geDdnLH651Vj0JuCOyGDxW8kVG+db1rumbXnYWH7gmBi233/v9dte6N8SGdF8gsNFedKrA==[/tex]，则[tex=2.857x1.5]L2hV/BmMBXt/2l8CptnlVA==[/tex]，故[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图有[tex=0.929x1.214]K4h+M94mGh2tzbuD4aMPBQ==[/tex]个结点。因为每个[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组都有[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]个[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组与它只有一个坐标不相同，故[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图每个结点的度数为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]，故边数为[tex=8.071x1.571]91rllUXNeTXbl4KAVz5hZwqz7HjHBIA5ADXN8SDlAfVb1eeZSQ5fl3vc0i7z/YJK[/tex]。把[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图的结点分类，若[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]元组中1的个数为偶数个，则对应结点属于[tex=0.857x1.0]N7iCrOsS+NNEUUlnsYCi1g==[/tex]，其余属于[tex=0.643x1.0]O+viFNA0oHTwnBtQyi80Zw==[/tex]。由[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图的定义可知[tex=0.857x1.0]N7iCrOsS+NNEUUlnsYCi1g==[/tex]中点互不相邻，[tex=0.643x1.0]O+viFNA0oHTwnBtQyi80Zw==[/tex]中结点也互不相邻，故[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]-维立方体图是二部图。

举一反三

内容

0
证明:如果能够证明如下命题，那么就可以证明:对所有的正整数[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]和[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]，[tex=2.857x1.357]x53ByXNSe9QoR8aqSxOunQ==[/tex]为真。对所有的正整数[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]，[tex=2.786x1.357]EoVija0Wvc60C/7c5b0GFg==[/tex]为真，且对所有的正整数[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]和[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]，[tex=7.929x1.357]0dcb1Sn642lu4eYwYSzkT6BFGKP9IDOc8rzsQP2x7jI=[/tex]为真。[br][/br]
1
证明：[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]个文字的积对应于[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]立方体[tex=1.214x1.214]09ZXoxVTCdKWQQldwFb9rQ==[/tex]的[tex=1.929x1.214]81VS3KyJUvSh5fSsf22g6Q==[/tex]维子立方体，其中立方体的顶点对应于标识顶点的位串表示的小项。
2
一棵树有[tex=1.0x1.0]QqIFaXbQ6A36xW+3hO3KXw==[/tex]个顶点的度数为2，[tex=1.0x1.0]iXd4QjwGFKTINrjsSR2Bbg==[/tex]个顶点度数为[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]，[tex=2.786x0.786]SfRiiP9LQZvM06avh0qv8w==[/tex]，[tex=1.0x1.0]DFEdoZ8mQiZ9bmPkw4i5PQ==[/tex]个顶点度数为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]，问它有几个度数为1的顶点?
3
一个图中包含[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]个连通分量,若按深度优先搜索方法访问所有节点,则必须调用次深度优先遍历算法。未知类型：{'options': ['[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]', '[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]', '[tex=2.143x1.143]RXOR4dwGRJqPM4VCsVYEvg==[/tex]', '[tex=2.143x1.143]LZ+KIQ24FJDpshqxAt5v1A==[/tex]'], 'type': 102}
4
设[tex=1.071x1.286]mdrkz91/hsK6dkSTPIkGTg==[/tex]表示[tex=0.5x1.0]ycRjqHa76IDpEZtluYQxdQ==[/tex]上的模[tex=0.429x1.214]adIpAOtu2Zm0WIyZC7drnQ==[/tex]等价关系，[tex=1.143x1.214]w0jOWBOYpEcoMNBewKVdIw==[/tex]表示[tex=0.5x1.0]ycRjqHa76IDpEZtluYQxdQ==[/tex]上的模[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]等价关系，证明[tex=2.071x1.357]P0L7JYeLBZhCns8KrVsSlA==[/tex]细分[tex=2.0x1.357]ksGluXMZdLzDXcW003uvAg==[/tex]当且仅当[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]是[tex=0.429x1.214]adIpAOtu2Zm0WIyZC7drnQ==[/tex]的整数倍。