1)子图：子图可以用构造的方式产生，一个图$G$，从其中拿出一些节点$V$，这些节点构成一个子图（只有节点的子图）；接着拿一些$G$的边，能拿的边都是必然是以$V$为端点的，还是子图；继续拿，拿到不能再拿得到induced by $V$的子图。
Euler path(cycle) $x_1, \cdots, x_n$最主要的性质是包括所有的边，并且只包含一次，长度是定的，边的个数。
Hamilton path(cycle) $y_1, \cdots, y_n$最主要的性质是包括所有的顶点，并且只包含一次，节点数是定的，顶点的个数。
Euler path：节点是可以经过两次的， Hamilton path：不必经过每条边。
"节点不重复"是比"边不重复"强的要求，前者可推出后者。
2) Cycle是很重要的一个刻画图的属性：
1) 连通无cycle是树
2) 节点数大于等于2的树必然有2个节点的degree是1，也就是叶子。反过来如果一个图的最小degree大于1，那么必然不是树，必然有cycle。
3) 如果一个图如果只有一个cycle，那么这个图就是这个cycle加上一些根植在其上的树，如果不是树那么和只有一个cycle矛盾。
4) 如果一个图没有没有长度为奇数的cycle，那么这个图是两部图。
首先注意到，对于一个tree来说，连接任何两叶子个节点，也就是加入一个边，必然得到一个Cycle。
Fundamental Cycle：设$T$是图$G$的一个span tree，加入任何一个$G$的边到$T$里，得到的Cycle称为Fundamental Cycle。注意Fundamental Cycle必须依赖于span tree的选择，但是他们的个数是定的。
性质：图$G(V,E)$的Fundamental Cycle的个数是图的边的数量减去span tree的边的数量，也就是$|E|-(n-1)$。
性质：图的任何Cycle都是Fundamental Cycle的组合。
3) 图的同构，定义为a)存在一组标签，两图的端点同用这一组标签，b)任意两个标签之间的边数是相等的。
Labelled Tree的意思是，考虑上面的同构的定义，如果同一个树，用一组标签，但是标注的顶点不一样，这样可以看成两个tree，如果这两个tree不满足同构的定义，那么认为是两个Labelled Tree。当然本身不同构的tree自然是不同的Labelled Tree
顶点个数为$n$的Labelled Tree的个数$T(n)=n^{n-2}$
5) 平面图
桥，平面图的桥只和一个face就是边界face接触，不是桥的边都和两个face接触。
平面图的欧拉公式：$$V-E+R=2$$
平面图把平面分成不同的region，region的度是其接触的边的数量，如果一个region接触了一个边两次，计数region的度的时候算两次，则所有region的度的和是边的数量的2倍。
$K_{3,3}$不是平面图：region的边界显然是cycle，而$K_{3,3}$没有奇数边的cycle，所以它里面的cycle边的数量都大于等于4，也就是region的度大于等于4；通过欧拉公式可得如果$K_{3,3}$是平面图的话，region的个数是5，这给出了一个region度和的下界5*4=20，但是我们知道这个和其实是边数量的2倍，也就是18，矛盾。
圆和弦分的区域
$n$个点分布在圆上，任取两个点，画一个弦，假设没有三个弦交在同一点，求这些弦把圆内部分成的区域的数量。
去掉圆周的弧剩下的构成一个图，
弦的交点的数量${n\choose 4}$，且这些交点的degree是4。其他在圆周上的$n$个上顶点，他们的degree为$n-1$。
正多面体由两个参数决定，a) 顶点处相遇的面的个数，记为$m$，b) 面是正多边形，多边形的边数，记为$n$。
所有可能的正多面体$(m,n)$是$(3,3),(3,4),(4,3),(3,5),(5,3)$。
面只有正5边形和6边形的多面体：正5边形的内角，5边形可以分成3个三角形，所以内角的和是$3\pi$，每个内角为$\frac{3\pi}{5}$。正6边形的内角为$\frac{2\pi}{3}$。考虑多面体的顶点，最多有3个面可以相遇，因为不论如何组合，4个角的和都大于$2\pi$。
多面体的事实给出如下两个关系：a) 每个顶点的degree为3，所以整个图的degree为3p。 b)面的degree为$5x+6x$，$x,y$为两种正多边形的个数。
图论给出另外两个关系：a)欧拉公式。b)整个图的degree为边数的2倍。
上面的关系可以导出$x=12$，也就是这种多面体的正5边形的个数为12。
No comments:
Post a Comment