什么是图?
2021/12/21 23:26:18
本文主要是介绍什么是图?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一章 什么是图?
什么是图?
定义: 图是由若干的顶点(即点或节点)及连接两顶点的边(或线或关系)所构成的图形。
原文: A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines).
引用: https://en.wikipedia.org/wiki/Graph_theory
在看到上述定义我们应该还是一脸的疑惑,因为我们不知道其前后关系。只知晓一个定义,这样的知识其实是很容易忘记的,那让我们开始完整学习吧。
一、导论
在我们先今,数据直接的关联在不断增强,系统也越发复杂庞大。我们怎么把数据之间的关联利用好,变得越发的重要。
1.1错误的”图”
在我们未接触或者了解图的时候,我们眼中的图是这样的
上述其实就是我们生活中接触到的”图像”和”图表”,这些并不是我们今天要将的主题的”图”。
那图张什么样子呢?
上述应该是一个比较经典的图结构,这个图是PageRank 这个图算法具有代表性的案例关于PageRank图算法本次不做介绍,大家可以自行百度相关内容。
上图中各个圈(1、2、3、E、C、G等等)即开篇-图定义中的顶点(即点或节点),图连接各个圈的线即开篇-图定义中边(或线或关系)。通过上述内容我们大致了解了什么图?但图的起源、图的发展、图的作用、图的分类、以及图现在的趋势我们是不了解的,让我继续下面的内容吧。
1.2图的起源
其实图的发展历史可以追溯到1937年,当时遇到一个问题,即知名的”哥尼斯堡七桥”问题。当时有一个人欧拉,他解决了这个问题,并且他的解决方案奠定了我们现在所说的图论。
问题是这样的: 如何将下图中的各个桥只走一次,并且全部走完呢?
上图为哥尼斯堡市,图中的绿色为连接城镇的桥梁,问题就是如何将图中的绿色每个只走一次,并且全部走完。
在1737年的时候欧拉解决了该问题,通过将桥和地方进行抽象将点和边。通过”一笔画”方法解决了该问题。(一笔画这边不做展开,感兴趣的自行搜索相关资料),这简单4点7边奠定了我们现在使用的”图论”。
我们上述不断的在说图论,那么图论和我们讲说的图是什么关系?
图论是以图作为研究对象。图论是离散数学的一个分支,是一门研究图(Graph)的学问。所以我们常说的图其实就是图论研究的对象而已。
我们常将图做如下表示:
Graph即图对象有时也写为G,V为顶点集合,E为边集合
1.3 图的分类
我们日常工作中会接触到很多所谓的图,有各种各样的类别,知道这些图的类别是我们和其人沟通重要的知识点之一。
图有很多划分的标准,下面我们举例常见的几个。
1.根据点边类型的数量进行划分。
① 同构图: 一种点类型一种边类型的图
② 异构图: 不同类型的节点和边的图
2.根据图的联通情况、方向、属性、环路我们可以在进行划分
③ 连通图: 根据点是否与其他点相连
④ 有向图 : 根据边上是否存在方向
⑤ 有环图:根据图中是否存在环路
⑥ 带权图:根据边上是否存在属性
3.根据图的拓扑结构我们在进行划分
1. 随机结构 2.小世界结构 3.无标度结构
⑦ 随机结构:
均匀分布,没有结构或者层级模式。任何顶点到其他顶点都是等概率的。
⑧ 小世界结构:
该结构在社交网络中非常常见也非常具有代表性,其基于“6度空间理论”,你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过6个中间人你就能够认识任何一个陌生人。
⑨ 无标度结构
图中符合幂律分布,就会产生无标度网络比较有代表性的为万维网。
4.根据点边数量以及连接关系划分
⑩ 二部图(又叫”二分部”)
下图中User和Item同类型之间不关联,两种之间相互连接。即为二部图,将其衍生可以到K-部图。
1.4 图的使用场景
其实现在图已经融入了我们生活中的方方面面,例如我们衣食住行中用到的美团,他们就用了图进行推荐。在金融场景中图技术已经被大量金融机构用于欺诈检测、团伙发现等各个业务场景中。图的大到可以评估在一个大型系统的运行机制。小到可以衡量生物蛋白之间的稳定性。图已无处不在,并且万物皆可图进行表示。
1. 航空系统交通网络图
2.生物蛋白以及生物结构图
1.5 图的发展趋势
1.6 什么是图算法
我们在使用图当中经常会用到图算法这个技术,那什么是图算法,图算法到底是做什么的呢?其实:图算法是图分析工具。图分析使用图的方法来分析关联数据的过。图算法是分析关联数据的一种有效方法。因为图的数学运算是针对关联运算进行设计的。图算法基于图论的数学原理,图算法利用顶点之间的关系来推断复杂系统的组织形式和动态性。使用者可以利用这些算法来发现隐藏的信息,关联甚至可以做到预测。
未完待续…..
这篇关于什么是图?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?