无向图及有向图.ppt

离散数学图论的起源1.哥尼斯堡七桥问题哥尼斯堡七桥问题解决方式图论的起源欧拉图从这个问题可以看出：2、一百多年以后3.哈密尔顿回路问题哈密尔顿回路图4、“四色猜想”问题5、又过了半个世纪学好图论十分重要第7章图的概念

本章学习：
1.无向图及有向图
2.通路、回路、图的连通性
3.图的矩阵表示
4.最短路径及关键路径
今日内容预备知识1、无序积：A&B
设A、B为两集合，称
{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B。
为方便起见，将无序对{a,b}记作(a,b)。
(a,b)＝(b,a)
例：
设A={a,b},B={c,d},则A&B＝？A&A＝？
A&B={(a,c),(a,d),(b,c),(b,d)}
A&A={(a,a),(a,b),(b,b)}
2、无向图
一个无向图G是一个二元组<V,E>,即G=<V,E>,其中:
①.V是一个非空集合,称为G的顶点集,V中元素称为顶点或结点;
②.E是无序积V&V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边。
无向图示例3、有向图
一个有向图D是一个二元组<V,E>,
即D=<V,E>,其中：
①.V同无向图中的顶点集;
②.E是笛卡儿积的多重子集,其元素称为有向边,也简称边.

有向图示例图的一些概念和规定标定图与非标定图、基图关联与关联次数、环、孤立点关联与关联次数、环、孤立点相邻与邻接例：点边之间的关联次数例：点点、边边之间的相邻关系顶点的度数d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=0d+(v1)=2
d+(v2)=1
d+(v3)=3
d+(v4)=1
d+(v5)=1最大(出/入)度,最小(出/入)度握手定理（图论基本定理）

问题研究握手定理

度数列度数列举例度数列举例(4，4，3，1，0)(3，4，3，4，2)可图化的充要条件例7.1：
(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？
已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？
解：
1.由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数序列。
2.显然，图G中的其余顶点度数均为2时G图的顶点数最少.设G图至少有x个顶点.由握手定理可知，
3×4+2×(x-4)=2×10
解得:x=8
所以G至少有8个顶点。

简单图与多重图43完全图完全图举例正则图子图在上图中，(2)，(3)均为(1)的子图；(3)是生成子图；导出子图举例补图在下图中，(1)是(2)的补图，当然(2)也是(1)的补图，就是说，(1)，(2)互为补图。同样，(3)，(4)互为补图。图的同构图同构(graphisomorphism)图的同构

55(2)(3)(4)(5)和(6)不同构,因为在(6)中有三个彼此不邻接的顶点,而在(5)找不到三个彼此不邻接的顶点.判断两个图同构的必要条件是:
顶点数相同;
边数相同;
对应顶点的度数也相同.例7.2(2)画出3阶2条边的所有非同构的有向简单图
由握手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2。度数列及入度出度列为作业Q&A