2015年9月15日星期二

图论趣题

近来开了算法高级课，更接近数学，今天研究了一天的图论，找到一篇好文章，特转载。
本文转载自：http://www.cnblogs.com/xpjiang/p/4403479.html  

1、证明：在连通无向图的每一对不同顶点之间都存在简单通路。
　　证明：设u和v是连通无向图G = (V, E)的两个不同的顶点，因为G是连通的，所以u和v之间至少有一条通路。设x0, x1, x2, ..., xn 是长度最短的通路的顶点序列，其中x0 = u 而xn = v。这条长度最短的通路是简单的。为了看明白这一点，假设它不是简单的。则对满足0≤i＜j的某个i 和j 来说，有xi = xj。这意味着通过删除顶点序列xi, ..., xj-1 所对应的边，就获得了带有顶点序列x0, x1, ..., xi-1, xj, ..., xn的从u到v的更短的通路。我们通过反证法引出了矛盾，因此原命题成立，命题得证。
2、证明：若带有n个顶点的简单图G具有超过(n-1)(n-2)/2 条边，则它是连通的。
　　提示：假设不连通，则至少有两个连通分支，证明它可能的最多的边数（无向完全图）小于等于(n-1)(n-2)/2条边，命题就得证了。
3、证明：带有n个顶点的连通图至少具有n-1条边。
　　证明：不妨设G是无向连通图（若G为有向图，可忽略边的方向讨论对应的底图）。设G中顶点为,v1, v2, ..., vn。由连通性，必存在与v1相邻的顶点，不妨设其为v2（否则，可重新编号），连接v1与v2得边e1，还是由连通性，在v3, v4, ..., vn中必存在与v1或v2相邻的顶点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1, v2, ..., vn-1中的某顶点相邻，得新边en-1，由此可见G中至少有n-1条边。
　　我经常提醒自己，有关正整数n的命题通常可以用数学归纳法加以证明，那么下面我们就来尝试一下。
　　对于归纳基础：0、1显然成立。
　　归纳假设：带有k个顶点的连通图至少具有k-1条边。下面我们来证明带有k+1个顶点的连通图至少具有k条边。我们把k+1个顶点分成两部分，一部分含有k个顶点，一部分只有一个顶点，对于k个顶点的连通图我们知道它至少具有k-1条边，我们只需要这样构造：把那个孤立的顶点与k个顶点中的任何一个连接形成一条边，那么显然带有k+1个顶点的连通图至少具有k条边（当然我们也可以用任何其它的划分方式，这样只需将证明过程改为强数学归纳法即可）。
4、已知V是一条割边的端点。证明：V是割点当且仅当它不是悬挂点（顶点是悬挂的，当且仅当它的度是1）。
　　证明：
　　　　充分性：V是割点那么它显然不是悬挂点，因为如果它是悬挂点的话，删除该点和它关联的边后图的连通分支显然没有增加。
　　　　必要性：当一条割边的端点不是悬挂点时，该端点一定是割点。若割边的端点不是悬挂点，则删除这条割边后，这端点所在的连通分支里包含除这个顶点外更多的顶点。所以，删除那个顶点以及与它关联的所有边，包括原来的割边，会产生比原来的图有更多的连通分支的图。
　　　　因此，割边的端点要不是悬挂点，它就是割点。
5、证明：具有至少两个顶点的简单图至少有两个顶点不是割点。
　　证明：反证法。假设存在至多一个不是割点的顶点的连通图G。顶点u和v之间的距离定义成在G里u和v之间最短通路的长度，表示成d(u,v)。设s和t是使得d(s,t)达到最大的G里的顶点。s或者t（或二者全部）是割点。所以不失一般性，假设s是割点。在通过从G删除s和与s关联的所有边而得出的图里，设w属于不包含t的那个连通分支，因为从w到t的每条通路都包含s，所以d(w,t)>d(s,t)。引出矛盾。因此原命题得证。
6、证明：若简单图G有k个连通分支，而且这些分支分别具有n1, n2, ..., nk个顶点，则G的边数不超过∑i=1~kC(ni, 2)。
　　证明：一条边不可能连接两个在不同连通分支里的顶点。因为在带ni个顶点的连通分支里至多有C(ni, 2)条边，所以在图中至多有∑i=1~kC(ni, 2)条边。
7、设p1和p2是简单图G中顶点u和v之间的没有相同边集的两条简单通路。试证明：在G中存在简单回路。
　　证明：设通路p1和p2分别是u = x0, x1, ..., xn = v。因为p1和p2不包含相同的边的集合，所以它们必然逐渐分叉。若这个分叉发生在它们中的一条已经结束后，则另一条通路的剩余部分是从v到v的简单回路。否则，可以假设x0 = y0, x1 = y1, ..., xi = yi，但是xi+1 ≠ yi+1。沿着通路yi, yi+1, yi+2等等前进，直到它再次遇到p1上的顶点为止。一旦回到p1上，就沿着它，在必要时刻向前或向后回到xi，因为xi = yi。这样就形成一条回路，它必然是简单的，因为在这些xj之间没有一条边能等于用过的yk之间的一条边。
8、证明：若图G中恰有两个奇数度顶点，则这两个顶点是连通的。
　　证明：设G中的两个奇数度顶点分别为u和v，若u与v不连通，即它们之间无任何通路，则G至少有两个连通分支G1、G2，u与v分别属于G1和G2，于是G1与G2中各含一个奇度顶点，这与握手定理（文末有介绍）的推论相矛盾，因而u与v必须是连通的。
9、如果一个简单无向图的所有顶点的度都等于k，则称该图为k正则图。证明：对于每一个大于2的偶数n，存在n个顶点的3正则图。
　　提示：构造性的存在性证明。方法多样。
————————————————下面几题属于现实问题抽象成图模型的问题，更具趣味性:-)—————————————————
10、证明：若有n个人，每个人恰有三个朋友，则n必为偶数。
　　证明：用n个顶点代表n个人，在两个朋友对应的顶点见连边，则得一个3正则图G。问题转化为求证3正则图必有偶数个顶点。设图G为任一3正则图，有n个顶点v1, v2, ..., vn，则所有顶点的度数之和为∑deg(vi) = 3n。由握手定理知3n为偶数，因此n是偶数。
　　[另：有趣的是，由本题与上一题的结论，我们可以得到一个为真的命题：存在3正则图当且仅当顶点数为大于2的偶数]
11、现有n个盒子，若每两个盒子里都恰有一个相同颜色的球，且每种颜色的球恰有两个放在不同的盒子中，问这n个盒子中共有多少种不同颜色的球？
　　提示：抽象成无向完全图，求边数：n(n-1)/2。
12、证明：在至少有2个人的人群里，至少有2个人，他们有相同的朋友数。
　　证明：注意到，等价地，设G为至少有两个顶点的简单图。证明：G中至少有两个顶点度数相同。若G中孤立的顶点个数大于等于2，结论显然成立。若G中有一个孤立顶点，则G中至少有三个顶点。不考虑孤立顶点，就是说G中每个顶点的度数都大于等于1。又因为G为简单图，所以每个顶点的度数小于等于n-1。因而G中顶点的度的取值只能是1, 2, ..., n-1这n-1个数。由鸽巢原理，取n-1个值的n个顶点的度至少有两个是相同的。
13、将无向完全图k6的边随意地涂上红色或绿色，证明：无论如何涂法，总存在红色的k3或绿色的k3。
　　证明：实在是手酸了：~，还是写提示吧。[hint：广义鸽巢原理+集合全集]。
　　当然，从应用题的方面考虑：我们可以出一个这样的题目——证明：任何6个人中，要么有三人彼此认识，要么有三人彼此不认识。
 补充：
握手定理：每个图中，顶点的度数和等于边数的两倍。 　　
　　对于无向图有∑(vεV)deg(v) = 2|E|。 
　　对于有向图有∑(vεV)(deg-(v)+deg+(v)) = 2|E|。
推论：任何图中，奇数度的顶点必为偶数个。
与之相关的定理：在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和。∑(vεV)deg-(v) = ∑(vεV)deg+(v) = |E|。
这些定理几乎是显然的，因此就不作证明了。
发帖者 时间： 没有评论:
标签：

2015年9月7日星期一

#LeetCode# Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
这个问题困扰了我快一个星期（小偷懒！）今天早晨拿出来重新看，仔细回味在某处看到的“先处理右子树”。有了灵光。

与上一个完全二叉树的问题比较，此树为任意树，意味着某个节点可能没有兄弟节点，或堂兄弟节点等，我们的难题在于怎么找到后继节点，怎么把当前节点与未知的XX节点链接起来。

所以，简化过程，

1. 先找到右孩子的第一个有效next链接节点
2. 左孩子nxet后继链接1中的有效next链接节点

这就是所谓的“先处理右子树”，相应的，我们的递归也先递归右子树。

上代码，


/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
    //1.先找右孩子第一个有效的next链接节点
    TreeLinkNode p = root.next;
    TreeLinkNode Node = null;
    while (p != null) {
        if (p.left != null) {
            Node = p.left;
            break;
        }
        if (p.right != null) {
            Node = p.right;
            break;
        }
        p = p.next;
    }
    
    //2. 左孩子nxet后继链接1中的有效next链接节点
    if (root.right != null) {
        root.right.next = Node;
    }
    
    if (root.left != null) {
        if (root.right != null) {
            root.left.next = root.right;
        } else {
            root.left.next = Node;
        }
    }
    
    //3.递归调用
    connect(root.right);
    connect(root.left);
    
    }
}

这里用Node来代表右孩子第一个有效的next链接节点，while语句判断两种情况，左子树不为空和左子树空右子树不为空。
接下来的链接过程与完全二叉树情况类同，不表。递归，注意先递归右子树，因为我们需要先处理右孩子/树。

好了，有点绕脑子的问题就停滞下来，该加把劲儿了。

LOL! 
发帖者 时间： 没有评论:
标签： , , , ,

2015年9月2日星期三

强烈推荐一款好用的chrome键盘控制插件Vimium

众所周知，熟练键盘的操作效率要比鼠标高很多，特别阅读代码、网页时候。Vim和Emacs的快捷键也一直为我们广泛称道。chrome上就有一款采用Vim快捷键的键盘控制插件——Vimium。

安装成功启用后，Shift+? 就可以调出帮助文件？


Enjoy your Vimium.

发帖者 时间： 没有评论:
标签：
订阅： 博文 (Atom)