若无向图G(V,E)中含7个顶点,为保证图G在任何情况下都是连通的,则需要的边数最少是多少?

devtools/2024/10/9 3:30:19/

这乍一看是不是可抽象(迷糊)了,butttt待我小翻译一下。

先举少一点的例子,假如我们有三个点,我给你两条边,那是不是不管咋连都一定一定是连通的。

75c31fe9631a4fcabdcd17a2cad24e23.png

那我们再进一步,假如四个点呢?我给你四条边那一定一定是连通的。

482910df9e4f42c1b586f01cd43c7319.png 

同理,那五个点呢??我给你七条边那一定一定也能保证是连通的。

d840ea65116b429abe785e42d6bb8942.png 

 发现什么了吗?其实就是前n-1个点已经构成完全图了,所以这时候如果再来一个点,是不是只能再加一条边与其相连啦(因为前n-1个点已经全部连通了嘛)那我们看回问题,完全是不是就能够满足任意啦,我把你所有的路都走了,接下来我第7个点,你是不是必须给我安排一根。

那答案就是 6(6-1)/2 + 1

(不要问我为什么不画了,因为很懒,有问题接着发私信蛤)


http://www.ppmy.cn/devtools/120422.html

相关文章

【STM32】 TCP/IP通信协议(1)--LwIP介绍

一、前言 TCP/IP是干啥的?它跟SPI、IIC、CAN有什么区别?它如何实现stm32的通讯?如何去配置?为了搞懂这些问题,查询资料可解决如下疑问: 1.为什么要用以太网通信? 以太网(Ethernet) 是指遵守 IEEE 802.3 …

操作符详解与表达式求值

目录 操作符分类 1.算数操作符 2.移位操作符&#xff08;只适用于整数范围&#xff09; &#xff08;1&#xff09;引入 &#xff08;2&#xff09;左移操作符<< &#xff08;2&#xff09;右移操作符>> 3.位操作符 4.赋值操作符 复合赋值符 5.单目操作符 5…

【系统架构设计师】专题:需求工程总结

更多内容请见: 备考系统架构设计师-核心总结目录 文章目录 一、软件需求二、需求获取三、需求分析3.1 需求分析的任务3.2 结构化的需求分析四、需求定义五、需求验证六、需求管理一、软件需求 软件需求是指 用户对系统在功能、行为、性能、设计约束等方面的期望。是指用户解决…

CSS点击事件穿透

假设盒子中有一个按钮&#xff0c;要实现点击按钮时透过按钮的点击事件&#xff0c;只触发盒子的点击事件&#xff0c;这个时候只需要给按钮设置如下属性即可&#xff1a; button {/* 清除点击事件 */pointer-events: none; } uniapp测试代码如下&#xff1a; <templat…

IDEA开发SpringBoot项目基础入门教程。包括Spring Boot简介、IDEA创建相关工程及工程结构介绍、书写配置文件、Bean对象管理等内容

文章目录 0. 关于本文1. 概述1.1 Spring简介1.2 Spring Boot简介1.3 传统的开发方式1.3.1 简述1.3.2 缺点 1.4 Spring Boot的优点 2. 创建一个简单的Spring Boot应用程序2.1 在IDEA创建项目2.2 pom配置文件内容2.3 启动类2.4 创建Controller 3. 从Maven工程创建Spring Boot工程…

git 报错git: ‘remote-https‘ is not a git command. See ‘git --help‘.

报错内容 原因与解决方案 第一种情况&#xff1a;git路径错误 第一种很好解决&#xff0c;在环境变量中配置正确的git路径即可&#xff1b; 第二种情况 git缺少依赖 这个情况&#xff0c;网上提供了多种解决方案。但如果比较懒&#xff0c;可以直接把仓库地址的https改成ht…

Web3.0 应用项目

Web3.0 是下一代互联网的概念&#xff0c;旨在去中心化、用户拥有数据控制权和通过区块链技术实现信任的网络。Web3.0的应用项目主要集中在区块链、加密货币、去中心化应用 (DApps)、去中心化金融 (DeFi)、NFT&#xff08;非同质化代币&#xff09;等领域。以下是一些典型的 We…

车辆重识别(2020NIPS去噪扩散概率模型)论文阅读2024/9/27

[2] Denoising Diffusion Probabilistic Models 作者&#xff1a;Jonathan Ho Ajay Jain Pieter Abbeel 单位&#xff1a;加州大学伯克利分校 摘要&#xff1a; 我们提出了高质量的图像合成结果使用扩散概率模型&#xff0c;一类潜变量模型从非平衡热力学的考虑启发。我们的最…