设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。

2022-05-30

设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。

答案：

解：假设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树，根据题意，[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边，根据定义，[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路。反过来，假设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。令[tex=0.5x0.786]EL0hSqs6jZBGdsmH7TMShQ==[/tex]等于[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的分量的数目，每一个分量是一个有[tex=0.857x1.0]2PRcZYSCMRI7PuJElJaGIw==[/tex]个顶点的分量，且[tex=3.857x3.286]DlqTU1JW/SG6ctvom5fqrJqmLRetXzREJLaySd5pwDM=[/tex]，根据题意，[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中边的总数是[tex=7.286x3.286]BXa3rPJCmmvXLrQWsrgd3tqxKcYEDBdwewckcfhv+GwnCVmoItOCUM2ddHs9HnTi[/tex]。因为已知总数应为[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex].因此[tex=3.0x1.214]YSYuMbjTpmGQBhBVmkwrog==[/tex]是连通的并且满足树的定义。

举一反三

内容

0
设[tex=1.0x1.214]fxP5NKfuaC23W5waarA1ZQ==[/tex]和[tex=1.0x1.214]oSv4U8R1pGloBPK+RYGtWA==[/tex]是简单图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中顶点[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]和[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]之间的没有相同边集的两条简单通路。证明:在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中存在简单回路。
1
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是一个[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]阶有限群,试证:若对[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]的每一个因子[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex],[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至多只有一个[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]阶子群,则[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是循环群.
2
当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一条边[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]不包含在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的闭迹中时，[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]才是[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的割边。
3
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是有11个顶点或更多顶点组成的无向简单图，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]或其补[tex=0.786x1.143]+451LNTzFcllUr/bPjBymg==[/tex]是非平面图。
4
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的带宽表示成[tex=2.357x1.357]+ispcpTOSEXFYO/0sdUFNA==[/tex]，它是[tex=12.286x1.286]Rs3zT7wz/pxlo6jKCgp06tNnw2CSb4cf9MgLnRl3EihZTTlt8NhwAiNplmCDNs7m[/tex]在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的顶点a]，[tex=5.643x1.0]O9qGQWb1YzoOCaRetv+AwfgoAIwMQmd5CVpc52uzabc=[/tex]的所有排列上所取的最小值。即带宽是赋给相邻顶点的下标的最大差值在顶点的所有列表，上所取的最小值。求下列图的带宽。[tex=1.214x1.214]j06tnoZ4NyXuHtqWvo0Kfw==[/tex]