图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点，[tex=2.357x1.143]dkoxwOpyXKTw0HsOj3nnBg==[/tex]条边，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至少有一个顶点度数大于等于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]。

2022-06-08

图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点，[tex=2.357x1.143]dkoxwOpyXKTw0HsOj3nnBg==[/tex]条边，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至少有一个顶点度数大于等于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]。

答案：

用反证法。假设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中每个顶点的度数都小于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]，由于[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点，[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中顶点度数必小于等于[tex=1.143x1.0]oTcZ8bPOd5+p8E1UHN7wXA==[/tex]。然而， [tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中有[tex=2.357x1.143]dkoxwOpyXKTw0HsOj3nnBg==[/tex]条边，根据握手定理，[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中所有顶点度数之和为[tex=8.786x1.357]HuoLL1cciwgFaSeWsXeggWXsIlIbd5sKLgLZp0i//nc=[/tex]，因此产生矛盾。故[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至少有一个顶点度数大于等于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]。

举一反三

内容

0
证明若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是每个区域至少由[tex=3.714x1.357]t4m09K08tJGB1uusdhNvVuc5URErc/eaaGjLa86CMP4=[/tex]条边围成的连通平面图，则[tex=7.143x1.357]LLrBhqlfzFUTMWOZW2F2hBiVCl9ndgMIOcEv+gIW3cs=[/tex]。这里[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]、[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]分别是图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的顶点数和边数。
1
设[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]
2
设[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.143x1.214]5v+MZormF/Vr6LmwYGDaHg==[/tex]
3
证明:若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通图，则有可能删除顶点使[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]变成不连通的当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]不是完全图。
4
证明有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的树，其顶点度数之和为[tex=2.429x1.143]rsnmA8IU9jfe9eDta3hFMA==[/tex]。