当前课程知识点:软件理论基础 > 第一章 基础知识 > 1.3 图 > Video
欢迎同学们来到《软件理论基础》Mooc课堂
现在介绍第三节:图
图实由两类元素构成
一类是顶点
顶点,也叫结点
用圆圈表示
像 a、b、c、d、e,是图的顶点
另一类是边
(a, b) 是有向边,从 a 指向 b
(b, c)、(b, e)、(c, e),等等
实际上,边
是顶点集合的一个关系
图中,边上标些数字
叫标记图
以后在自动机
经常要用到这种图
图中通路,也叫 walk
表示这样一些边连成的
由尾和首连接起来的边
像 (c, e)、(e, d)、(d, c)、(c, e)、(e, b)
构成的一个线路,叫做通路
在图中,有一种叫做路径
它是一种通路
没有重复的边
这个图中
从 e 开始,(e, d)(d, c)(c, e)(e, b)
是一条没有重复边的通路
称为路径
另外,这图中有一条路径
没有重复的顶点
像从 d 开始
(d, c)、(c, e)、 到 (e, b)
没有顶点重复
这样的路径,叫做简单路径
图中有一种,叫回路,也叫作环
是从某一点出发
譬如,从 e 开始出发,又回到它自己
这样一条路径叫做回路
在回路中
只有一点
从这点开始,譬如从 c 开始
c 到 e,e 到 b,再回到 c
只有这一点 c 出现重复
这样的回路叫做简单回路
图中有一类特殊的图
叫作树
有一个顶点或结点
没有入边连接它
叫作根结点
还有一些顶点,没有出边
这类顶点叫作叶结点
有些顶点,有进来的边,也有出去的边
是内部结点
在内部结点,像这个结点
是从这个顶点连接它
这结点叫做这个顶点的子结点
而这结点叫做这个结点的父结点
树中
的特点是没有环
树可以定义高度
这个结点,边的个数
是 0 个边,层数为 0
这个结点, 从根结点到它有一条边
它的层数是 一
这个结点,从根结点到它
通过两条边,是两层
而这个结点,从根结点到它
有三条边,是三层
这棵树
结点最高的层数
像这个结点
是这棵树最高的层数,三层
定义为树的高度
这节内容介绍完毕
谢谢大家!
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试