下载文档原格式
图论1．图的基本概念图：由一些点和连接两点间的连线组成图1在这个图中，521,,,v v v 称为这个图的顶点，顶点之间的连线621,,,e e e 称为这个图的边。
通常我们用V 表示一个图中所有顶点的集合，用E 表示一个图中所有边的集合。
于是一个图G 通常被定义为()E V G ,=，在上图中{}521,,,v v v V =，{}621,,,e e e E = 图的阶数：一个图中含有的顶点数。
例如上图中含有5个顶点，故上图称为5阶图 有向边（弧）：如果在图的定义中要求边e 对应的序偶><b a ,是有序的，即前后顺序是不能颠倒的，则称边e 为有向边或弧。
无向边：如果在图的定义中要求边e 对应的序偶><b a ,是无序的，即前后顺序是可以颠倒的，则称边e 为无向边无向图：如果一个图中的每一条边都是无向边，则称这个图为无向图 有向图：如果一个图中的每一条边都是有向边，则称这个图为有向图 如果图的某个顶点和某条边是相联的，则称它们是相关联的顶点的次数：在无向图中把与某个顶点相关联的边数称为该顶点的次数。
环算两次，顶点v 的次数记为()v d在有向图中从顶点v 出去的边数，称为顶点v 的出度，记为()v d +进入顶点v 的边数，称为顶点v 的入度，记为()v d-，()()()v d v dv d -++=定理：一个图中所有的顶点的次数之和等于边数之和的两倍 推论：任何图中奇数次顶点的总数必为偶数例：一次聚会中，认识奇数个人的人数必为偶数 孤立点：次数为0的顶点。
图2 图3多重边：在图中，如果两个顶点之间的边多于一条，那么这几条边就称为多重边。
多重图：含有多重边的图环：如果图中某条边的起点和终点为同一个顶点，那么称这条边为环 简单图：既没有多重边又没有环的图在图中如果顶点i v 和j v 之间至少存在一条边，那么称顶点i v 和j v 是相邻的。
如果边i e 和j e 之间至少有一个共同顶点，则称边i e 和j e 是相邻的子图：设有图()111,E V G =和()221,E V G =，如果21V V ⊆并且21E E ⊆，则称图1G 是图2G 的一个子图生成子图：，如果21V V =并且21E E ⊆，则称图1G 是图2G 的一个生成子图图4图5链：以顶点开始以顶点结束的顶点和边的非空有限交替序列 例如43152v e v e v 就是一条链，而4312v e v v 却不是一条链圈：如果一条链的起点和终点是同一个顶点，则称这条链是一个圈如21152v e v e v路：当一条链中所有边和所有顶点均不相同时就称这条链为路 回路：如果一个圈中的所有边均不向图并且除第一个顶点和最后一个顶点相同外其余顶点都不相同，则称这个圈为回路连通图：如果某个图中的任何两个顶点之间至少存在一条链，则称这个图为连通图在实际的应用中，经常会涉及到图中各个顶点之间的某种联系，例如，在城市公路交通图中，需要说明两个路口之间的路段的长度，这时就需要给图的边赋以某个数值（称为线权）或给顶点赋以某个数值（称为点权），我们把这种赋以了数值的图称为加权图或网络。
课程类型数学
“托兰定理”讲义编号：
托兰定理在求极值的图论问题中具有重要作用，本讲主要介绍该定理及其相关方法。
定理：有n个顶点且不含三角形的简单图G中最多有[n2/4]条边。
证明
1
例1 设n≥2。
平面上已给2n个点，每三点不共线。
在这些点之间连n2+1条线段。
证明至少形成n个以已知点为顶点的三角形。
例2 由n个点和这些点之间的l条连线段组成一个空间四边形，其中n=q2+q+1，l≥1/2q(q+1)2+1，q≥2，q∈N。
已知此图中任四点不共面，每点至少有一条连线段，存在一点至少有q+2条连线段。
证明：图中必存在一个空间四边形（即由四点A，B，C，D和四条连线段AB，BC，CD，DA组成的图形）
例3一次会议有500人参加，（i）如果每名代表认识的人数为400人，是否一定能选出6个人，每两人互相认识？(ii）如果每人认识的人数大于400人。
证明：一定能找到6个人，每两人互相认识。
托兰图
托兰图T n,r是具有n个顶点的完全r部图且其中各部集的大小最多相差1。
引理在具有n个顶点的r部简单图中，托兰图是唯一边数最多的图。
证明
2。
