Abstract: 机器学习中我们希望从数据中挖掘隐含信息或模型，若将图中的结点作为随机变量，连接作为相关性关系，那么我们就能构造出图模型，并期望解决这一问题。而构造这样的概率图模型需要一定的图论知识。本文就总结了图论的基本概念、以及与ML的关系。
图论：以图为研究对象，描述某些事物间的特定关系。由结点与边组成，G = {V，E}。有向边与无向边。有向图与无向图。
树型结构：树是图的一种；从根节点开始，并能和其他结点相连接的图；有向性
ML X 图论：决策树；概率图模型
//马上要考离散了，紧张复习ing… 把离散中的图论与ML结合起来复习，感觉还行 ~
图论 Graph Theory
关键图：
- 路：开路，回路，真路，链，闭链
- 连通图，连通子图，分图
- 欧拉图，哈密顿图
- 树，生成树，最小生成树，有向树
- 二部图
- 平面图
机器学习与图论
ML: 从数据中挖掘隐含信息与模型
- 将图中的结点作为随机变量，边（连接）作为相关性关系，则可构造出图模型。
- 概率图模型（概率论+图论）是实现这一任务的重要手段
决策树：可表示为给定特征条件下类的条件概率分布。
- 结点：由表示特征的内部结点和表示类的叶节点构成
- 决策树的学习包括特征的选择、决策树的生成和决策树的剪枝
- 树型：包含于图论
图论
- 数学的分支
- 以图为研究对象，研究顶点和边组成的图形
- 图数据结构或树型算法：来源于图论
Loosey–goosey图
非线性结构：
- 最基础特征：数据不遵循特有顺序（至少无明显数值关系），类似数组和链表
树
- 树型结构：从根节点开始，并能和其他结点相连接；
- 树由一组规则定义而成：即一个根结点可能连接或不连接到其他结点，但最终所有叶结点或内部结点都能追溯到这个特定的位置。
- 一些树有更多的特定规则，如二叉搜索树，该树在任意时间内每个结点都只和两个子结点相连
- 机器学习常用的决策树：可以看成是 IF-THEN 规则的集合；即由决策树的根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
- 树的有向性：一棵树只能朝一个方向传播，即树型是由有向边（directed edge）构成的；每棵树都是由根节点开始，向下往子节点或叶节点传播；每条路径唯一，且路径上所有子节点有且仅有一个父节点；故树型结构一定不会存在循环结构或链路
图
不存在根节点、叶节点、单向边等概念，图中结点可连接多个子节点和多个父节点，路径可有向或无向
有向图（directed graphs）和无向图（undirected graphs）
- 图的基本原则：有且至少有1个单结点（才能被看做是图啊）
- 结点和结点之间的连接并没有确切的规则，边（有时候也称为链接）能以任何方式连接结点
- 边的类型（大多数情况下：有向/无向）是图之间最大、最明显的区别之一。
- 有向边：规定两结点间只有单一方向，origin——>destination
- 无向边：两结点间路径双向互通，未固定起始结点和目标结点
- 有向图：所有边都是有向边；无向图：所有边都是无向边
图（如何定义图？）
图：一种正式表征网络的结构，基本上是所有互连对象的集合；结点无层次结构
图与函数的一致性：
- 函数：二维坐标轴上分布的有序对（x，y）集合
- 图：（x，y）=（点vertices，边edges）/（v，e）；图的正式数学定义即为：G=（V，E）
- 有序对（V，E）：由2组对象组成，一组结点，一组边
下图是无向图G={8，12}
下图是有向图G={3，3}
图论的应用
1.网络是巨大的图结构
- 互联网——边、终端——结点、用户——在图中切换（如点击URL来回浏览）
以网页间的切换为例：有向边——只能从一个网页转到另一个；无向边——可在两网页间来回切换
2.社交网络是图结构
微信：大型无向图
- 微信本身是一个庞大的社交网络图
- 结点：用户；边：用户间的沟通联系（好友关系）
- 无向性（理解为信息沟通的双向性）：两个用户间的关系是双向的，可互相传递信息，无起始结点和目标结点的概念
微博：大型有向图
- 有向性（信息传播的单向性）：用户发微博时博文会在同时间点由用户向粉丝发送，这一过程有方向且不可逆
概率图模型
ML:从数据中挖掘隐含信息与模型
- 将图中的结点作为随机变量，边（连接）作为相关性关系，则可构造出图模型。
- 概率图模型（概率论+图论）是实现这一任务的重要手段
概率图模型
- 图论定义：概率图模型是一个包含结点与边的图；结点分为2类：隐含结点和观测结点；边分2类：有向边与无向边
- 概率论定义：概率图模型是一个概率分布，图中的结点对应于随机变量，边对应于随机变量的相关性关系
给定一个实际问题，我们通常会观测到一些数据，并且希望能够挖掘出隐含在数据中的知识。那么怎样才能使用概率图模型从数据中挖掘这些隐藏知识呢？
- 构建一个图：用观测结点表示观测到的数据，用隐含结点表示潜在的知识，用边来描述知识与数据的相互关系，最后获得一个概率分布。给定概率分布之后，通过进行两个任务获取知识：即推断 (给定观测结点，推断隐含结点的后验分布）和学习 (学习概率分布的参数）。
基本图模型的2个类别
- 贝叶斯网络（Bayesian Network）
- 马尔科夫随机场(Markov Random Field)
- 二者的主要区别：采用不同类型的图来表达变量间的关系；贝叶斯网络采用有向无环图（Directed Acyclic Graph）来表达因果关系；马尔可夫随机场则采用无向图 (Undirected Graph) 来表达变量间的相互作用；
图论——详细概念梳理
图论是一种表示 “多对多” 的关系
图是由顶点和边组成的：(可以无边，但至少包含一个顶点)
- 一组顶点：通常用 V(vertex) 表示顶点集合
- 一组边：通常用 E(edge) 表示边的集合
图可以分为有向图和无向图，在图中：
- (v, w) 表示无向边，即 v 和 w 是互通的
图可以分为有权图和无权图：
- 有权图：每条边具有一定的权重(weight)，通常是一个数字
- 无权图：每条边均没有权重，也可以理解为权为 1
图又可以分为连通图和非连通图：
- 连通图：所有的点都有路径相连
- 非连通图：存在某两个点没有路径相连
图中的顶点有度的概念：
- 度(Degree)：所有与它连接点的个数之和
- 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
- 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和
Extensional Resources
Difference between Trees and Graphs
What’s the difference between the data structure Tree and Graph?
Applications of Graph Theory In Computer Science: An Overview
Data structures: Introduction to graphs（视频）
