举一反三
- 证明:若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通图，则有可能删除顶点使[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]变成不连通的当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]不是完全图。
- 设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[br][/br][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=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]没有包含奇数条边的回路。
内容
- 0
无向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex](1) [tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是否为Euler 图，为什么?[img=353x260]17873c0595f5d37.png[/img]
- 1
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是有11个顶点或更多顶点组成的无向简单图，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]或其补[tex=0.786x1.143]+451LNTzFcllUr/bPjBymg==[/tex]是非平面图。
- 2
证明或反驳下一结论：连通图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的任一边为[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的某一生成树的弦。
- 3
证明：若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]是同构的有向图，则[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]的逆图也是同构的。
- 4
设 [tex=0.643x1.0]jLbabU9pW65GUKemsNBJWw==[/tex] 为无向连通图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的一个边割集,证明 [tex=2.786x1.143]jMAYbh8you1a6SvAPIb1IA==[/tex] 不含 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的生成树.