图论中的点割集,看书上的定义看不懂,能不能通俗的讲解一下

问题描述:

图论中的点割集,看书上的定义看不懂,能不能通俗的讲解一下

割点:对于连通图中的一个点,如果去掉这个点后,原来的图变成非连通图,那么这个点就称为原图的一个割点.
点割集:对与连通的的一个点集合A,如果去掉A中所有的点后,原来的图变成非连通图,那么这个点集合A就称为原图一个点割集.
有上面的定义可知,割点和点割集并不一定是唯一的.若点割集的任意真子集不是点割集的话,那么这个点割集就称为极小点割集.而所有点割集中含的点个数最少的点割集就称为最小点割集.极小点割集不一定是最小点割集,这是两个不同概念,容易混淆.
有不懂的再问我吧.那一般怎么看一个点是不是割点呢,是不是只要去掉这点看原图还连不连通就可以了? 如果是点割集呢?要怎么找嗯,判断割点方法就是看去掉这个点后原图是否连通。判断点割集也是一样的,就是看去掉这个点集合后原图是否连通。那如果让你找点割集咋办,那么多点分别组合来看去掉后是否连通吗是尝试着组合时的,因为点割集有很多的,所以要找一个点割集一般是不困难的,但要说一个有效算法的话,我目前还没有找到哈,估计它不是一个多项式算法。我给你说个我认为的简单直观的算法吧:给定一个图后,找出其度最大的点,把这个点去掉,并去掉其所有邻边,若此图不联通,那么去掉的那点就构成了一个割点。若联通,再在剩下的图中找最大度的点,去掉度最大点与其邻边,若剩下的图不联通,那么刚才去掉的两个点构成点割集。否则继续找剩下的图的最大度点...以此类推...这个方法是最简单直观的,但不一定是最好的方法了.......