当前位置：新励学网 > 秒知问答 > 离散数学题目用图论解

离散数学题目用图论解

发表时间：2024-07-19 15:53:07 来源：网友投稿

转化为图论问题既是：

在一个N顶点的无向图中，当边数K>(N-1)(N-2)/2时，证明其为连通图，证明如下：

假设存在一个N节点K条边无向图，为不连通的，即设它存在2个连通分支（连通分支越多，边数越少，故只需讨论两个连通分支的情况），并设一个连通分支的节点数为S，则另一个连通分支为N-S，则易知：在这个图中，边数最大条数为

(S-1)(S)/2+（N-S)(N-S-1)/2，（每一个连通分支为完全图），整理得，边数最大为：N×N-(2S+1)+S×S(S>=1),而K>(N-1)(N-2)/2=N×N-3N+2>=N×N-(2S+1)+S×S，故，在这两个连通分支之间必存在边，结论得证。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！

相关资讯
  • 汽修专业新疆怎么找工作
    2025-04-06
  • 机械专业专长怎么写简历
    2025-04-06
  • 专科怎么报审计专业的
    2025-04-06
  • 专业学科导师类别怎么填
    2025-04-06
  • 查报考专业网站怎么查
    2025-04-06
  • 水电专业规划怎么写简历
    2025-04-06
  • 表演专业怎么留学的好呢
    2025-04-06
  • 专业防雷检测怎么收费的
    2025-04-06
  • 怎么查询同等学力专业
    2025-04-06
  • 高考技能专业怎么选择的
    2025-04-06
  • 钢筋套筒专业名称怎么写
    2025-04-06
  • 中专怎么填高考志愿专业
    2025-04-06
  • 中专统招怎么报志愿专业
    2025-04-06
  • 师范专业自我评价怎么写
    2025-04-06
  • 景观建筑换专业怎么换好
    2025-04-06
  • 建筑专业学生简历怎么写
    2025-04-06
    • 推荐资讯
  • 澳大利亚悉尼大学课程设置及特色课程有哪些
    2024-07-13 05:49:26
  • 重申正科级干部54岁改非,副科级干部52岁改非吗
    2024-08-21 18:13:41
  • 奉贤区正规财务咨询费用一般是多少
    2024-08-22 09:18:19
  • 黄金的价格是多少钱
    2024-10-16 13:30:48
  • 清流触石回旋激注的意思
    2024-12-15 11:56:38
  • 什么是专业学组
    2025-03-21 14:31:26
  • 针灸学科哪个专业最好
    2025-03-24 07:52:22
  • 国家级创业导师有哪些专业
    2025-03-28 07:32:04
  • 适合物控的专业有哪些专业
    2025-03-30 10:26:27

    • 新励学网教育平台

    海量全面 · 详细解读 · 快捷可靠

    最新文章

    累积科普文章数：18,862,126篇

    热门关注
  • 1 汽修专业新疆怎么找工作
  • 2 机械专业专长怎么写简历
  • 3 专科怎么报审计专业的
  • 4 专业学科导师类别怎么填
  • 5 查报考专业网站怎么查
  • 6 水电专业规划怎么写简历
  • 7 表演专业怎么留学的好呢
  • 8 专业防雷检测怎么收费的
  • 9 怎么查询同等学力专业
  • 10 高考技能专业怎么选择的
  • 11 钢筋套筒专业名称怎么写
  • 12 中专怎么填高考志愿专业
  • 13 中专统招怎么报志愿专业
  • 14 师范专业自我评价怎么写
  • 15 景观建筑换专业怎么换好
    • 网站导航
    首页
    教育
    考研
    作文
    公考
    申论
    留学
    建造
    会计
    问答