设[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]为无向连通图，有[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个结点，那么[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中至少有几条边？为什么？若是有向图又如何？
举一反三
- 有[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个顶点的强连通有向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]至少有[input=type:blank,size:4][/input]条弧。
- 无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]是欧拉图，当且仅当[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]满足下面4个条件中的哪一个？（1）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的所有结点的次数为偶数；（2）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的所有结点的次数为奇数；（3）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]连通且所有结点的次数为偶数；（4）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]连通且所有结点的次数为奇数.
- 有[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个顶点的有向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]最多有[input=type:blank,size:4][/input]条弧。
- 利用[tex=2.357x1.0]kfpThotcKMAogYhLU6M1UQ==[/tex]定理证明：若[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]阶图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]是[tex=1.857x1.143]y7i0KNMTbem23CcX+abErQ==[/tex]边连通的[tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex]正则图，且[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]是偶数，则[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]存在完美匹配。
- 设 [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]的生成树.