当前位置: 首页 > news >正文

做品牌网站的企业/全国广告投放平台

做品牌网站的企业,全国广告投放平台,漯河网站建设,长春工作招聘网一.引例(哥尼斯堡七桥问题) 哥尼斯堡七桥问题是指在哥尼斯堡市(今属俄罗斯)的普雷格尔河(Pregel River)中,是否可以走遍每座桥一次且仅一次,最后回到起点的问题。这个问题被认为是图…

一.引例(哥尼斯堡七桥问题)

        哥尼斯堡七桥问题是指在哥尼斯堡市(今属俄罗斯)的普雷格尔河(Pregel River)中,是否可以走遍每座桥一次且仅一次最后回到起点的问题。这个问题被认为是图论的开端,也是数学史上著名的问题之一。

        欧拉在解决这个问题时,将问题转化为了图论中的欧拉回路问题。他证明了如果一个图中有欧拉回路,那么这个图中每个顶点的度数都是偶数。反之,如果每个顶点的度数都是偶数,那么这个图中就存在欧拉回路

        因此,哥尼斯堡七桥问题的答案是否定的,因为哥尼斯堡的地图中有两个岛屿,这两个岛屿与其他地区相连的桥的数量都是奇数,因此这个图中不存在欧拉回路。

二.图的逻辑结构

1.图的定义

图是由顶点的有穷非空集合和顶点之间边的几何组成。

通常表示为:G=(V,E)

注:

1)G表示一个图

2)V是图G中顶点的集合

3)E是图G中顶点之间边的集合

4)在线性表中,元素的个数可以为0,称之为空表;在树中,元素的个数可以为0,称之为空树;但是在图中,顶点个数不能为0,可以没有边。

2.有向图与无向图

若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)

如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。

若顶点vi和vj之间的边有方向,则称这条边为有向边,表示为<vi,vj>

如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。

3.图的基本术语

1)简单图

在图中,若不存在顶点到自身的边,且同一条边不重复出现。

注:数据结构中讨论的都是简单图

2)邻接/依附

无向图中,对于任意两个顶点vi和vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,vj)依附于顶点vi和顶点vj。

有向图中,对于任意两个顶点vi和vj,若存在弧<vi,vj>,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧<vi,vj>依附于顶点vi和顶点vj。

3)无向完全图/有向完全图

无向完全图:

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。

含有n个顶点的无向完全图中边的个数:

n*(n-1)/2

有向完全图:

在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。

含有n个顶点的有向完全图中边的个数:

n*(n-1)

4)稀疏图/稠密图

稀疏图:边数很少的图

稠密图:边数很多的图

5)度

无向图:TD(v)

入度:ID(v)

出度:OD(v)

6)度与边数的关系

所有顶点的度之和=边数*2

入度=出度=边数

7)权/网

权:对边赋予的有意义的数值量

(从一个顶点到另一个顶点所需要付出的代价)

网:边上带权的图

8)路径长度

非带权图:边的个数

带权图:各边权之和

9)简单回路

除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。

10)连通图

图中任意两个顶点都是联通的

11)连通分量

非连通图的极大连通子图

12)强连通图

在有向图中,堆图中任意一对顶点vi和vj(i!=j),若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径

13)生成树

n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图

含有n-1条边

生成树不是唯一的

14)生成森林

在非连通图中,由每个连通分量都可以得到一棵生成树,这些连通分量的生成树就组成了一个非连通图的生成森林。

4.不同结构中逻辑关系的对比

在线性结构中,数据元素之间仅具有线性关系。

在树结构中,结点之间具有层次关系。

在图结构中,任意两个顶点之间都可能有关系。

在线性结构中,元素之间的关系为前驱和后继。

在树结构中,结点之间的关系为双亲和孩子。

在图结构中,顶点之间的关系为邻接。

三.图的抽象数据类型定义

ADT Graph

Data

        顶点的有穷非空集合和边的集合

Operation

初始

销毁

深度优先搜索

广度优先搜索

 

相关文章:

【数据结构】图的简介(图的逻辑结构)

一.引例&#xff08;哥尼斯堡七桥问题&#xff09; 哥尼斯堡七桥问题是指在哥尼斯堡市&#xff08;今属俄罗斯&#xff09;的普雷格尔河&#xff08;Pregel River&#xff09;中&#xff0c;是否可以走遍每座桥一次且仅一次&#xff0c;最后回到起点的问题。这个问题被认为是图…...

2342.数位和相等数对的最大和

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;2342. 数位和相等数对的最大和 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 哈希表&#xff0c;根据数位和分组后&#xff0c;计算每组中最大两个数之和&#xff0c;然后返回最大值即可。…...

关于Spring Bean的一些总结

一、Spring Bean的生命周期 Spring中的Bean生命周期是指一个Bean从被创建、初始化&#xff0c;到被使用&#xff0c;再到被销毁的整个过程。在Spring容器管理的Bean中&#xff0c;生命周期的管理主要通过回调方法和事件监听来实现。以下是Spring Bean的生命周期的主要阶段和回…...

6.2 List和Set接口

1. List接口 List接口继承自Collection接口&#xff0c;List接口实例中允许存储重复的元素&#xff0c;所有的元素以线性方式进行存储。在程序中可以通过索引访问List接口实例中存储的元素。另外&#xff0c;List接口实例中存储的元素是有序的&#xff0c;即元素的存入顺序和取…...

2023数维杯国际赛数学建模D题完整论文分享!

大家好&#xff0c;终于完成了2023年第九届数维杯国际大学生数学建模挑战赛D题The Mathematics of Laundry Cleaning&#xff08;洗衣清洁的数学原理&#xff09;的完整论文啦。 D论文共43页&#xff0c;一些修改说明10页&#xff0c;正文25页&#xff0c;附录8页。 D题第一问…...

golang中context使用总结

一、context使用注意事项 在使用context时&#xff0c;有一些需要注意的事项&#xff0c;以及一些与性能优化相关的建议&#xff1a; 避免滥用context传递数据&#xff1a;context的主要目的是传递请求范围的数据和取消信号&#xff0c;而不是用于传递全局状态或大量数据。滥用…...

医院数字化LIS(检验信息系统)源码

临床检验信息管理系统&#xff08;LIS&#xff09;是利用计算机连接医疗设备&#xff0c;通过计算机信息处理技术&#xff0c;将医院检验科或实验室的临床检验数据进行自动收集、存储、处理、提取、传输和交换&#xff0c;满足所有授权用户的功能需求。 一、系统概述 1.LIS&am…...

挑战单芯片NOA,这款“All in one”方案或将改变主流市场走向

随着降本增效、电子架构升级&#xff08;尤其是跨域计算、多域融合等概念&#xff09;以及供应链减复&#xff08;降低电子物料的SKU&#xff09;的需求愈加明确&#xff0c;对于车载计算赛道&#xff0c;也带来新的变化。 比如&#xff0c;去年9月&#xff0c;英伟达率先发布下…...

CODING DevOps产品认证笔记

1.敏捷&精益&瀑布概述 1.1 敏捷软件开发 第一章敏捷软件开发背景 背景&#xff1a;乌卡时代 易变性:当今世界的变化越来越多越来越快&#xff0c;越来越不可预测。不确定性:历史上的任何一个时代所带来的经验已经无法为当今世界的所有变化提供参照。复杂性:事物间的…...

信息系统项目管理师 第四版 第5章 信息系统工程

1.软件工程 1.1.架构设计 1.2.需求分析 1.3.软件设计 1.4.软件实现 1.5.部署交互 1.6.过程管理 2.数据工程 2.1.数据建模 2.2.数据标准化 2.3.数据运维 2.4.数据开发利用 2.5.数据库安全 3.系统集成 3.1.集成基础 3.2.网络集成 3.3.数据集成 3.4.软件集成 3.…...

对话芯动科技 | 助力云游戏 4K级服务器显卡的探索与创新

2021年芯动科技推出了基于IMG BXT GPU IP的风华1号显卡。单块风华1号显卡可在台式机和云游戏中实现4K级别的性能&#xff0c;渲染能力达到5 TFLOPS&#xff0c;如果在服务器中同时运行两块显卡&#xff0c;性能还可翻倍。该显卡是为不断扩大的安卓云游戏市场量身定制的&#xf…...

[HTML]Web前端开发技术1,meta,HBuilder等——喵喵画网页

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;大大会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…...

网上申请的电信卡能用多长时间?可以长期使用吗?

我们在网上总能看到一些关于流量卡的广告&#xff0c;都是19元&#xff0c;29元100多g的套餐&#xff0c;乍一看这些套餐非常便宜&#xff0c;但是小编提醒大家一定要注意优惠期。 ​  网上的流量卡套餐&#xff0c;都是由基础套餐额外赠送充值送话费等内容组成&#xff0c;…...

交换机的工作原理

局域网交换技术是数据链路层上的技术&#xff0c;就是转发数据帧。在数据通信中&#xff0c;所有交换设备都执行两个基本操作&#xff1a; 交换数据帧生成并维护交换地址表 交换数据帧 交换机根据数据帧的MAC地址&#xff08;物理地址&#xff09;进行数据帧的转发操作。交换…...

如何使用ArcGIS Pro制作粉饰效果

在地图上&#xff0c;如果某个部分比较重要&#xff0c;直接的制图不能将其凸显出来&#xff0c;如果想要突出显示重要部分&#xff0c;可以通过粉饰效果来实现&#xff0c;这里为大家介绍一下方法&#xff0c;希望能对你有所帮助。 数据来源 本教程所使用的数据是从水经微图…...

CSS滚动捕获 scroll-snap-align

CSS滚动捕获 scroll-snap-align 看到 align, 就条件反射想到对齐方式, 嗯猜对了. 不过要先看一下若干名词介绍 scroll-snap-align 指定了盒子的 snap position, 即盒子 snap area 和滚动容器的 snapport 的对齐方式. 这个属性是定义在滚动元素上, 而不是滚动容器上 语法 这个…...

基础课8——中文分词

中文分词指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在英文的行文中&#xff0c;单词之间是以空格作为自然分界符的&#xff0c;而中文只是字、句和段能通过明显的分界符来简单划界&#xff0c;唯独词没有一个…...

OpenHarmony应用开发入门教程(一、开篇)

前言 华为正式宣布2024年发布的华为鸿蒙OS Next版将不再兼容安卓系统。这一重大改变&#xff0c;预示着华为鸿蒙OS即将进入一个全新的阶段。 都说科技无国界&#xff0c;这是骗人的鬼话。谷歌的安卓12.0系统早已发布&#xff0c;但是自从受到美影响&#xff0c;谷歌就拒绝再向…...

vue侦听器详解及代码

在 Vue 中&#xff0c;我们可以使用侦听器&#xff08;watcher&#xff09;来监听数据的变化&#xff0c;并在数据发生变化时执行相应的操作。Vue 提供了 watch 选项来定义侦听器&#xff0c;并可以使用 vm.$watch 方法来创建侦听器。 下面是一个简单的示例&#xff0c;我们监…...

Python爬虫的七个常用技巧总结,这些你一定得知道!

文章目录 前言1、基本抓取网页2、使用代理IP3、Cookies处理4、伪装成浏览器5、验证码的处理6、gzip压缩7、多线程并发抓取关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战…...

【Linux】U盘安装的cfg引导文件配置

isolinux.cfg文件 default vesamenu.c32 timeout 600display boot.msg# Clear the screen when exiting the menu, instead of leaving the menu displayed. # For vesamenu, this means the graphical background is still displayed without # the menu itself for as long …...

Theory behind GAN

假如要生成一些人脸图&#xff0c;实际上就是想要找到一个分布&#xff0c;从这个分布内sample出来的图片像是人脸&#xff0c;分布之外生成的就不像人脸。而GAN要做的就是找到这个distribution。 在GAN之前用的是Maximum Likelihood Estimation。 Maximum Likelihood Estimat…...

《Deep learning for fine-grained image analysis: A survey》阅读笔记

论文标题 《Deep learning for fine-grained image analysis: A survey》 作者 魏秀参&#xff0c;旷世研究院 初读 摘要 细粒度图像分析&#xff08;FGIA&#xff09;的任务是分析从属类别的视觉对象。 细粒度性质引起的类间小变化和类内大变化使其成为一个具有挑战性的…...

节点导纳矩阵

节点导纳矩阵&#xff08;Node Admittance Matrix&#xff09;是电力系统分析中的关键工具&#xff0c;它用于描述电力系统中不同节点之间的电导和电纳参数。这个矩阵为电力工程师提供了深入了解电力系统运行和分析所需的数学工具。 节点导纳矩阵是一个复数矩阵&#xff0c;通常…...

小米真无线耳机 Air 2s产品蓝牙配对ubuntu20.04 笔记本电脑

小米真无线耳机 Air 2s产品蓝牙配对ubuntu20.04 笔记本电脑 1.我的笔记本是 22款联想拯救者y9000k&#xff0c;安装了双系统&#xff0c;ubuntu20.04。 2.打开耳机&#xff0c;按压侧面按钮2秒&#xff0c;指示灯显示白色闪烁。 3.打开ubunru20.04 系统右上角wifi的位置&…...

Python爬虫批量下载图片

一、思路&#xff1a; 1. 分析URL&#xff0c;图片的URL内嵌于base_url的返回当中 2. 下载图片 二、代码 import time import requests import os from lxml import etreeclass DownloadImg():爬虫进行美女图片下载def __init__(self):self.url http://xxxxxx/4kmeinv/self…...

java入门,从CK导一部分数据到mysql

一、需求 需要从生产环境ck数据库导数据到mysql&#xff0c;数据量大约100w条记录。 二、处理步骤 1、这里的关键词是生产库&#xff0c;第二就是100w条记录。所以处理数据的时候就要遵守一定的规范。首先将原数据库表进行备份&#xff0c;或者将需要导出的数据建一张新的表了…...

表白墙/留言墙 —— 中级SpringBoot项目,MyBatis技术栈MySQL数据库开发,练手项目前后端开发(带完整源码) 全方位全步骤手把手教学

&#x1f9f8;欢迎来到dream_ready的博客&#xff0c;&#x1f4dc;相信你对这篇博客也感兴趣o (ˉ▽ˉ&#xff1b;) &#x1f4dc;表白墙/留言墙初级Spring Boot项目&#xff08;此篇博客的简略版&#xff0c;不带MyBatis数据库开发&#xff09; 目录 1、项目前端页面及项目…...

Stable Diffusion - StableDiffusion WebUI 软件升级与扩展兼容

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/134463035 目前&#xff0c;StableDiffusion WebUI 的版本是 1.6.0&#xff0c;同步更新 controlnet、tagcomplete、roop、easy-prompt-selector等…...

git创建新分支将项目挂载到新分支操作

1.如果是本地项目,没有关联过git // 在git创建仓库(默认master分支) // 复制克隆链接(默认下载下来的是master仓库,克隆指定分支如下所示) git clone -b 分支名 克隆地址 // 将某分支克隆下来后,直接将项目放到新文件夹内(执行以下命令提交即可) git add . git commit -m 备注…...