Showing posts with label 图论. Show all posts
Showing posts with label 图论. Show all posts
2012/08/30
欧拉回路的回朔算法
首先算法不会给出所有的回路，当算法结束的时候，得到的仅仅是一个回路，算法检查边的顺序不同会造成结果的回路不同。把所有的边编号，其中的变量的含义g[node][i]是从node出发第i条边到达的节点。
search可以看成是检查当前节点node有没有未用过的边，如果没有就会返回，调用堆栈往上一层，search( g[node][i] )返回说明，边i到达节点g[node][i]，但是这个节点无边可用了，我们把i记下来(回朔)，然后看看从node出发的其他边能不能前进，如果假设node出来就一条边，那么算法会再往上返回，上面一层会认为node无边可用了，把探索的时候通向node的边也记下来。
分析算法的运行过程，算法一开始从一个节点开始，只要发现没用过的边就往前走，称这时候为探索模式，一直到没有边可用，注意这时候并不代表所有的边都用过了，还可能是当前节点的连接的边都用过了。没有边可用的时候算法开始回朔，回朔的同时记录边，回朔到某个节点，又有没用过的边，算法又开始往前，直到又没有边可用，开始回朔。最后所有的边都用完的时候，算法会一直到回朔到起点，最后记录的是从起点出来的边。
任何边在算法运行过程中只会被用一次，回朔开始的时候必然是到达了一个以前访问过的节点，因为如果到达一个节点，没被访问过，并且又无边可用，这个节点的度为1，不存在欧拉回路。
第一次回朔是什么时候开始的呢？回朔发生以前，站在任何一个节点看，算法必然是进去出来交替发生，对任何一个非起点节点，一进一出我们把节点的度减掉2，可以看出对于非起点节点是不可能发生进去出不来的情况，因为他们的度都是偶数，所以回朔第一次发生必然是在起点，因为起点是直接出来，度只需要减1。
还有一点就是，虽然第一次回朔发生在起点，在回朔的过程中还是会发现有的节点的degree没用完，算法可能再次进入探索模式。也就是当前节点有边可用进入探索模式，无边可用进入回朔模式。
2012/08/25
Matching
图里的match是边的集合M，要求M里没有两个边是有公共顶点的。这个名字可能是起源于婚姻问题，如果有公共顶点就是重婚了，所以是不允许的。
Marriage Problem: $m$个男孩，每个男孩认识一些女孩，现在开始match，要求每个男孩必须和他认识的女孩结婚，求这种方法存在的充分必要条件。
Hall's Theorem: Marriage Problem有解的充要条件是，任取$k$个男孩，他们必须认识至少$k$个女孩，其中$1\leq k\leq m$
二分图的最大match可以用网络流里面的Augmenting path来解决，先回顾一下网络流里的一些概念。
Residual network：对于一个网络上的flow来说，Residual network记录了这个flow在不违反网络每个路径的流量限制的条件下的所有变化的自由度。而且Residual network上的flow和原来的flow叠加还是原网络的一个合法的flow，满足flow的三个约束。
Augmenting path：是Residual network上的一个从源头到终点的简单路径。
augmenting path的residual capacity：是这个augmenting path上在Residual network里允许的最大流量。
所以Augmenting path不过是有向图的一个简单路径，所以用BFS或DFS查找均可。
二分图的最大match是这样转换为最大流问题的，首先男孩那边加一个节点$s$作为源头，并且和所有的男孩相连，女孩这边加一个节点作为终点$t$，同样和所有女孩相连，男孩到女孩的所有边都是男孩指向女孩。每条边的容量都设置为1。
很显然最后的flow不会有两个男孩连接到一个女孩，否则从这个女孩到$t$的流量就为2，这是不可能的。假设起始的时候flow的流量为0，每找到一个Augmenting path，这个path的容量只能是1。
用DFS找Augmenting path的时候，可以直接遍历所有男孩，因为这就相当于遍历所有$s$的邻居。
考虑两种Augmenting path，最简单的情况是，从某男出发，第一步就发现一个没被match的女孩，得一条边的Augmenting path；如果从某男开始DFS遇到的第一个女孩已经match了，这时候DFS不能停，因为按Residual network的容量看，这女孩到和她match的男孩的路径有一个反向的容量，所以继续，坏的情况，这男孩只认识这一个女孩，这时候DFS要开始返回了，这条path不是Augmenting path，好的情况，这男孩还认识其他没match的女孩，DFS会访问到这个新没match的女孩，这时候我们就得到了一条Augmenting path。
第二种情况实际上是劝说一个已经match的男孩换女朋友。
程序是这样的，bpm(u)可以理解为给u找女朋友，如果发现的女孩已有男朋友，劝说其男朋友换女朋友，而且不能换DFS已经见过的女孩，既然让人家换就得给人家找所有要再调bpm。
算法最终返回的条件是发现一个新的没match的女孩，而且这时候所有Augmenting path的男孩都得换女朋友。
Marriage Problem: $m$个男孩，每个男孩认识一些女孩，现在开始match，要求每个男孩必须和他认识的女孩结婚，求这种方法存在的充分必要条件。
Hall's Theorem: Marriage Problem有解的充要条件是，任取$k$个男孩，他们必须认识至少$k$个女孩，其中$1\leq k\leq m$
二分图的最大match可以用网络流里面的Augmenting path来解决，先回顾一下网络流里的一些概念。
Residual network：对于一个网络上的flow来说，Residual network记录了这个flow在不违反网络每个路径的流量限制的条件下的所有变化的自由度。而且Residual network上的flow和原来的flow叠加还是原网络的一个合法的flow，满足flow的三个约束。
Augmenting path：是Residual network上的一个从源头到终点的简单路径。
augmenting path的residual capacity：是这个augmenting path上在Residual network里允许的最大流量。
二分图的最大match
所以Augmenting path不过是有向图的一个简单路径，所以用BFS或DFS查找均可。
二分图的最大match是这样转换为最大流问题的，首先男孩那边加一个节点$s$作为源头，并且和所有的男孩相连，女孩这边加一个节点作为终点$t$，同样和所有女孩相连，男孩到女孩的所有边都是男孩指向女孩。每条边的容量都设置为1。
很显然最后的flow不会有两个男孩连接到一个女孩，否则从这个女孩到$t$的流量就为2，这是不可能的。假设起始的时候flow的流量为0，每找到一个Augmenting path，这个path的容量只能是1。
用DFS找Augmenting path的时候，可以直接遍历所有男孩，因为这就相当于遍历所有$s$的邻居。
考虑两种Augmenting path，最简单的情况是，从某男出发，第一步就发现一个没被match的女孩，得一条边的Augmenting path；如果从某男开始DFS遇到的第一个女孩已经match了，这时候DFS不能停，因为按Residual network的容量看，这女孩到和她match的男孩的路径有一个反向的容量，所以继续，坏的情况，这男孩只认识这一个女孩，这时候DFS要开始返回了，这条path不是Augmenting path，好的情况，这男孩还认识其他没match的女孩，DFS会访问到这个新没match的女孩，这时候我们就得到了一条Augmenting path。
第二种情况实际上是劝说一个已经match的男孩换女朋友。
程序是这样的，bpm(u)可以理解为给u找女朋友，如果发现的女孩已有男朋友，劝说其男朋友换女朋友，而且不能换DFS已经见过的女孩，既然让人家换就得给人家找所有要再调bpm。
算法最终返回的条件是发现一个新的没match的女孩，而且这时候所有Augmenting path的男孩都得换女朋友。
2012/08/04
Cut-Set
cut-set也叫cocycle。任取一个支撑树，树上的边称为branch，图里其他的边称为chord。
任何一个cut-set必然包含任何一个支撑树的至少一条边。反过来，连通图$G$里的任何一个最小集合，如果这个集合包含所有支撑树的至少一条边，这个最小集合是一个cut-set。
任何一个cut-set必然包含任何一个cycle的偶数个边。
任取一个支撑树$T$，$b$为$T$的任何一个边，显然$\{b\}$是$T$的cut-set，$\{b\}$把图的顶点分为两部分，考虑整个图的一个cut-set，把图的顶点分成同样的两部分，而且这个cut-set只包含$T$的一个branch，其他的都是chord，这个cut-set称为fundamental cut-set respect to $T$。
支撑树$T$的任意一个边对应了唯一的一个fundamental cut-set。
对偶性，Fundamental cut-set和Fundamental cycle的关系，我们知道任选一个chord对应了一个Fundamental cycle，这个cycle上的边除了一个chord其他的是branch。进一步的每个branch对应了一个Fundamental cut-set，这个cut-set包含一个branch，其他都是chord。
一个cut-set respect两个顶点$v_1, v_2$意思是这个cut-set吧两个顶点分在两个不同的集合里。
一个weighted无向图，上面的cut-set的capacity是这个cut-set里的所有边的weight的和。
定理：$v_1, v_2$之间的最大可能flow等于所有的respect这两个顶点的cut-set里capacity最小的。
任何一个cut-set必然包含任何一个支撑树的至少一条边。反过来，连通图$G$里的任何一个最小集合，如果这个集合包含所有支撑树的至少一条边，这个最小集合是一个cut-set。
任何一个cut-set必然包含任何一个cycle的偶数个边。
任取一个支撑树$T$，$b$为$T$的任何一个边，显然$\{b\}$是$T$的cut-set，$\{b\}$把图的顶点分为两部分，考虑整个图的一个cut-set，把图的顶点分成同样的两部分，而且这个cut-set只包含$T$的一个branch，其他的都是chord，这个cut-set称为fundamental cut-set respect to $T$。
支撑树$T$的任意一个边对应了唯一的一个fundamental cut-set。
对偶性，Fundamental cut-set和Fundamental cycle的关系，我们知道任选一个chord对应了一个Fundamental cycle，这个cycle上的边除了一个chord其他的是branch。进一步的每个branch对应了一个Fundamental cut-set，这个cut-set包含一个branch，其他都是chord。
一个cut-set respect两个顶点$v_1, v_2$意思是这个cut-set吧两个顶点分在两个不同的集合里。
Network Flows
一个weighted无向图，上面的cut-set的capacity是这个cut-set里的所有边的weight的和。
定理：$v_1, v_2$之间的最大可能flow等于所有的respect这两个顶点的cut-set里capacity最小的。
2012/05/27
Colouring
顶点的着色把顶点分成不同的集合，所以着完色后，这些集合之间的边的性质决定了着色的性质。
比如bipart是用分成两个集合，边的性质是：任何一个边的两个端点分别在不同的集合里。
但是并不是所有的图都可以这样把顶点集合分成两部分，使得没有两个相邻顶点的颜色相同。一般的着色问题是，至少需要把顶点分成几部分？
1) 贪心算法：a) 把图的节点排序，颜色排序。 b) 给第$i$个节点着色的时候检查它所有已经着色的邻居找到最小的没被用过的颜色，用这个颜色
分析：如果一个节点的degree为d，那么遍历颜色最坏的情况是前d个颜色都被用了，只能用第d+1个颜色。从整个图来看，图的最大degree给使用的颜色(chromatic number)一个上界$\Delta+1$
n个委员会，其中可能有重复的成员，安排他们开会，显然不能有重复成员的委员会被安排到同一天开会，问题：找到最小的天数使得每个委员会都能开一次会。模型是以每个委员会为顶点，以有重复成员的关系为边画一个图，找出图的chromatic number。
比如bipart是用分成两个集合，边的性质是：任何一个边的两个端点分别在不同的集合里。
但是并不是所有的图都可以这样把顶点集合分成两部分，使得没有两个相邻顶点的颜色相同。一般的着色问题是，至少需要把顶点分成几部分？
1) 贪心算法：a) 把图的节点排序，颜色排序。 b) 给第$i$个节点着色的时候检查它所有已经着色的邻居找到最小的没被用过的颜色，用这个颜色
分析：如果一个节点的degree为d，那么遍历颜色最坏的情况是前d个颜色都被用了，只能用第d+1个颜色。从整个图来看，图的最大degree给使用的颜色(chromatic number)一个上界$\Delta+1$
n个委员会，其中可能有重复的成员，安排他们开会，显然不能有重复成员的委员会被安排到同一天开会，问题：找到最小的天数使得每个委员会都能开一次会。模型是以每个委员会为顶点，以有重复成员的关系为边画一个图，找出图的chromatic number。
2012/05/26
Travelling Round a Graph
Hamiltonian是要求访问所有的节点，所以边越多的图越容易成为可能；Eulerian是要求访问所有的边。
1) Hamiltonian Graph
Dirac定理：$G$是一个简单图，有$p$个节点，如果所有节点的degree都大于$\frac{1}{2}p$，那么图里存在Hamilton回路。
如果图里有Hamilton回路，有一个算法可以决定图是不是平面图，把图的Hamilton回路画在平面上使其是图的外边缘，其他的边都在这个回路的内部。内部的边一般会相交，如果能把这些内部的边分成两类，它们的交点只发生在两类之间(可以用另外一个图，节点是原图的边，如果两边在原图相交，在这个新图里加一条边，如果这个新图是两部图那个这个分类就是可能的)，可以把这两类边一类画在回路内部，一类画在回路外部，这样就得到一个平面图的画法。
TSP：TSP的解的长度大于最小支持树的长度，小于最小支撑树的长度的2，即$MST < TSP \leq 2\ MST$。
下界：根据下面两个事实可以构造下界
a) Hamilton回路有两条边和图里的任何一个节点相关的方式是，一个边进入一个边出来。
b) 如果从图里去掉一个节点$v$，Hamilton回路里这个节点也去掉，剩下的Hamilton回路是剩下的图的一个MST，这个MST加上一条到$v$的边，得到一个原图的MST。
上界：如果沿着图的MST走一遍在转回来是图的一个回路，这个回路的长度是MST的2倍，通过这个回路可以构造一个Hamilton回路，这个Hamilton回路的长度不大于刚才的MST回路。
Gray Godes：是$2^n$个长度为$n$的二进制数的一个排列，特点是相邻的两个只差一位。可以看成$n$立方体的顶点的一个Hamilton回路，下图是3位Gray Godes的生成方式
a) 相邻顶点之间只差一个坐标。
b) 立方体上面的4个顶点最后一位是1，除了最后一位前两位构成$n=2$的Gray Godes，下面4个顶点最后一位是0，除了最后一位前两位构成$n=2$的Gray Godes。把两个$n=2$的Gray Godes接起来的位置是各自的$n=2$起点和终点。上面$n=2$的Hamilton回路反过来走，完成回路的最后一步不去终点，直接到另一个$n=2$的Hamilton回路，正过来在走一次，这样得到$n=3$的Hamilton回路。这个性质可以推广到n维的情况，递归的由$n-1$的Gray Godes获得，给出了一种Gray Godes的生成方法。
2) Eulerian Graph
定理：图里有Euler回路的充要条件是所有节点的degree都是偶数。
证明：如果一个图所有节点的degree都是偶数，那么这个图是由没有共边的回路构成，这个结论可以用归纳法证明，任选一个起点，开始一个walk，当遇到已经被walk包含的节点的时候，得到一个回路，把这个回路包含的边从图里去掉，每个节点减少的degree是2，所以剩下的图仍然满足所有节点都是偶数。
定理：图里存在Euler trail的充要条件是有且只有两个节点的degree是奇数。
得更紧的TSP上界，方法是从MST开始，加入一些边使得得到的新图里面有一个Eular回路，然后改变这个Eular回路遇到重复的节点的时候走shortcut得一个Hamilton回路，可以证明这个Hamilton回路的长度小于$\frac{3}{2}$TSP。
3) 有向图
定理：有向图里Eular回路存在的充要条件是每个节点的indegree和outdegree相等。
Memory wheel：把$2^n$个0,1排成一个圆，这个圆开始转，从任何一个点开始，记录$n$个数字构成一个二进制数，从任何一点开始都可以记录，所以有$2^n$种可能。Memory wheel是使得每个得到的$n$二进制数都不同。
模型：要做记录的二进制长度为$n$的Memory wheel，构造一个有向图，Memory wheel的特点是当前数的后$n-1$个数字和下一个数的前$n-1$个数字相同。也就是说知道当前数字，后面的数字前$n-1$个数字已经定了，后面那个数字有两个可能。用有向图描述，就是出发后可能的去向A0和A1。
先画顶点，顶点为长度为$n-1$的二进制数，顶点代表的是xA，出发到达的顶点是A0和A1。然后在图里找到一个Eular回路就得到了一个Memory wheel构造方式，现在这样的图里Eular回路是存在的。
1) Hamiltonian Graph
Dirac定理：$G$是一个简单图，有$p$个节点，如果所有节点的degree都大于$\frac{1}{2}p$，那么图里存在Hamilton回路。
如果图里有Hamilton回路，有一个算法可以决定图是不是平面图，把图的Hamilton回路画在平面上使其是图的外边缘，其他的边都在这个回路的内部。内部的边一般会相交，如果能把这些内部的边分成两类，它们的交点只发生在两类之间(可以用另外一个图，节点是原图的边，如果两边在原图相交，在这个新图里加一条边，如果这个新图是两部图那个这个分类就是可能的)，可以把这两类边一类画在回路内部，一类画在回路外部，这样就得到一个平面图的画法。
TSP：TSP的解的长度大于最小支持树的长度，小于最小支撑树的长度的2，即$MST < TSP \leq 2\ MST$。
下界：根据下面两个事实可以构造下界
a) Hamilton回路有两条边和图里的任何一个节点相关的方式是，一个边进入一个边出来。
b) 如果从图里去掉一个节点$v$，Hamilton回路里这个节点也去掉，剩下的Hamilton回路是剩下的图的一个MST，这个MST加上一条到$v$的边，得到一个原图的MST。
上界：如果沿着图的MST走一遍在转回来是图的一个回路，这个回路的长度是MST的2倍，通过这个回路可以构造一个Hamilton回路，这个Hamilton回路的长度不大于刚才的MST回路。
Gray Godes：是$2^n$个长度为$n$的二进制数的一个排列，特点是相邻的两个只差一位。可以看成$n$立方体的顶点的一个Hamilton回路，下图是3位Gray Godes的生成方式
a) 相邻顶点之间只差一个坐标。
b) 立方体上面的4个顶点最后一位是1，除了最后一位前两位构成$n=2$的Gray Godes，下面4个顶点最后一位是0，除了最后一位前两位构成$n=2$的Gray Godes。把两个$n=2$的Gray Godes接起来的位置是各自的$n=2$起点和终点。上面$n=2$的Hamilton回路反过来走，完成回路的最后一步不去终点，直接到另一个$n=2$的Hamilton回路，正过来在走一次，这样得到$n=3$的Hamilton回路。这个性质可以推广到n维的情况，递归的由$n-1$的Gray Godes获得，给出了一种Gray Godes的生成方法。
2) Eulerian Graph
定理：图里有Euler回路的充要条件是所有节点的degree都是偶数。
证明：如果一个图所有节点的degree都是偶数，那么这个图是由没有共边的回路构成，这个结论可以用归纳法证明，任选一个起点，开始一个walk，当遇到已经被walk包含的节点的时候，得到一个回路，把这个回路包含的边从图里去掉，每个节点减少的degree是2，所以剩下的图仍然满足所有节点都是偶数。
定理：图里存在Euler trail的充要条件是有且只有两个节点的degree是奇数。
得更紧的TSP上界，方法是从MST开始，加入一些边使得得到的新图里面有一个Eular回路，然后改变这个Eular回路遇到重复的节点的时候走shortcut得一个Hamilton回路，可以证明这个Hamilton回路的长度小于$\frac{3}{2}$TSP。
3) 有向图
定理：有向图里Eular回路存在的充要条件是每个节点的indegree和outdegree相等。
Memory wheel：把$2^n$个0,1排成一个圆，这个圆开始转，从任何一个点开始，记录$n$个数字构成一个二进制数，从任何一点开始都可以记录，所以有$2^n$种可能。Memory wheel是使得每个得到的$n$二进制数都不同。
模型：要做记录的二进制长度为$n$的Memory wheel，构造一个有向图，Memory wheel的特点是当前数的后$n-1$个数字和下一个数的前$n-1$个数字相同。也就是说知道当前数字，后面的数字前$n-1$个数字已经定了，后面那个数字有两个可能。用有向图描述，就是出发后可能的去向A0和A1。
先画顶点，顶点为长度为$n-1$的二进制数，顶点代表的是xA，出发到达的顶点是A0和A1。然后在图里找到一个Eular回路就得到了一个Memory wheel构造方式，现在这样的图里Eular回路是存在的。
2012/02/29
图论基本概念
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。
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。
Subscribe to:
Posts (Atom)