图的重新定义

定义"/>

图的重新定义

2019独角兽企业重金招聘Python工程师标准>>>

跟着上面

图究竟是什么组成的？

这里给出图的符号化定义，如下：

 文字描述：

G是一个边集合E所组成。任意边的元素e是个二元配对,x,y。p(e)是对e的二元配对的项的集合化。V集合是P(E)。E集合内，所有元素的p(e) 均属于V集合。

这里需要补充说明对e的操作，是否x == y，定义如下

null(e)是个集合。表示e的二元配对的内容，如果各自作为集合时，他们的交集。显然，如果是孤立顶点，x=y时，交集存在。反之则不存在。此处没有使用vec是因为，对于V集合的获取， p(e)足够描述。而null此处表示，该e并不存在真正的边的意思。如果null(e)为空，则不包含任何元素。由此说明e不为空。否定之否定。

可能大家觉得这个很绕，但在首先不违背逻辑，同时，对代码设计，具有简洁清晰描述的作用。

此处根据公理化集合论的选择公理，对G，E，V进行一个约束，如下：

文字描述，任意集合A，对于任意被A所包含的集合B而言，总存在一个集合C,B与C的并为A，交为空。如果一个集合中，存在连个相同的元素。则总能找到一个B，使得其属于A，且只包含其中一个元素。此时，任意C，如果和B的并为A。则C必然和B的交不为空。

关于图的定义有几点说明的：

1、首先不是异想天开，非要和图论书不一样。而是很多问题，传统的定义确实有麻烦，例如G=G1+G2。

2、定义中，没有规定 e(x,y) x,y一定要不等。e(x,x)实际上就是指孤立点。

3、没有说明是有限集合。图论中对图的定义是有限的。虽然有差别但谈不上我的定义和图论有矛盾。

4、没有规定E是非空集合。当然E是空集时，V自然也是空集。空图是有意义的。特别是判断两个图是否连通或交操作。

5、没有规定，不是孤立点即存在边 e(x,y) x,y不相等时，e(x,x）是否存在。

6、这里只是强调图论讨论的是点与点的关联，没有关联的概念，图论则没有存在的价值。此处特地强调 (x,y) = (y,x)，因此是无向边。关于有向图，边有方向性，我认为，和边的权重（例如距离，负载)都是额外的约束属性。对于有向图的边，后续会如下定义，以区别 （x,(x,y)) = (x,(y,x)) = ((x,y),x) = ((y,x),x)。当然

为了有效解决上述声明 5，对于e(x,x)的含混不清的概念，以下引入两个操作符

前面的操作，表示对E集合中所有边元素(x,y)二元项x不等于y的数量读取。后面的操作表示对所有E的元素的数量读取。

其实可以发现，对于指定的

为了统一描述，这里

以后除了特殊声明，上述操作只针对G处理。

在图论中，存在 阶 order ，边数 (size）的概念，实际就对等为

那么现在我们判断两个图是否相等，则变得的简单了。

这里意味着，如果我们是按照以边为存储图的方式，则通过上述的理论描述，我们可以仅通过对边集合的全遍历比较，判断是否正确。当然经过排序的边集合，我们只要判断存在错误，就可以对整图的相等进行否定。

下面看一下连通定义。

图论上，关于“关联”已经没有必要了。因为现在的图是以边为基础。但邻接边(adjacent edge)也变的格外重要。现有图论的定义如下：

有一个共同顶点的两条不同变，成为邻接边。

由此这里创造一个新的符号a(e)（我尽量回避现有图论的符号，同时尽可能保持他们原有的含义） 。a(e)的符号化定义如下

 文字描述是，A是个边的集合。边集E中，任意满足以下条件的边，都属于 A。

该边端点集合和e的端点集合交不为空。

这里我们可以证明，即便E中存在e(x,x), e(x,y)，也不会影响a(e)的性质。无非a(e)中多了e(x,x)本身。

但 当前a(e）,并不是传统图论的临界边的性质。此处引出个av(e)的定义，区别a(e)是仅针对相同端点。如下

文字描述下，总存在一个x，属于一个边的 p(e)操作后的集合，就是该边的端点集。所有满足这个条件的e都在av(e)里。

这里需要注意的是，av(e)并没有针对x进行约束。就是说我们并没有说av(e)是针对某个具体的顶点x的。可以回顾a(e),av(e)的定义，那么其实可以发现， av(e)可以有很多种可能。而我们把所有av(e)组成个集合。是个什么东西？哈。看个例子

假设有 边 e1(v1,v2) e2(v2,v3) 那么 a(e) 包含 e1,e2,e3。那么av(e)则可能有三种。 v1,v2,v3。

当然对于大多数图论证明，除非是三角形，否则上述的av(e)含义不大。因此对av(e)进行一个扩充。av(e,v)。但前期v需要属于p(e)此时，av(e,v)就等同了传统图论的 adjacent edge。

我相信，你可能会说，累不累。这样来说明一个邻接边。OK。我建议你去打开现有图论的书籍，从邻接边开始一直看到连通图的定义，我相信，你看完之前我已经写好了我下面的公式。

我对a(e)修正如下,并定义为con(e) 

这里做个递归定义。首先，e肯定在A中。对于任意A中的元素，只要和E中任意的元素y存在端点集合有交集的，则y也在A的元素中。

要满足上面的定义，则所有和e有邻接的边，他们的邻接边也在A集合里。

而这个集合就是一个e所能连通到所有边的集合。 由此，落在con(e)集合内的元素，都和e连通，反之则不连通。

这里有几个说明：

1、这里没有强调 e(x,y) 和e(x,x)，因为即便存在 e(x,x)，也不影响一个其他边的连通性的问题。

2、这里没有说有限的概念。这如同，自然数的定义一样。如果自然数的定义强调有限，就不会是自然数了。同时也不影响很多数论知识在无限中的推广。例如存在无限个素数。这里con(e)对连通的定义，实际可以是对无限图的连通的定义。

3、这比a(e)就多了2个内容。这也是为什么我始终想通过边来定义图的原因。在实际工程中发现基于顶点定义图的理论，在算法描述上会有很大的障碍。不同任务下的特殊化处理杂乱。

上述这些（自以为是)的图论定义，虽然看起来古怪，但是却可以给工程上带来理论指导作用。至少上述定义并没有违法公理化集合论，以及传统图论的相关概念与上述定义并不矛盾。

有上面的定义，我们在工程，编程上，对图的构造。按照边的方式进行。对于任意存在的顶点 v，我们仍然存在 e(v,v)这条边。当然对于连通遍历时，没有意义，不过我们完全可以有如下定义，来区分判断当前边的相邻边是否扫描完毕。

假设，我们的任意边，按照如下方式排序，任何相邻的边，要么他们完全不同，要么他们较大的端点号相同。由此，假设有4个顶点，22相连。则实际存储按如下排序

(3,0),(3,1),(3,2),(3,3),(2,0),(2,1),(2,2),(1,0),(1,1),(0,0)

此时，(x,x)正好是不同的大端点相同的边集合的分界线。此时这个边集已经包含了顶点和边的所有信息。这比把顶点作为一个数组，边作为一个数组分别处理要方便（现在有了理论支撑，以前按照传统图论则不行）（我们不谈顶点或边上的加权信息，那完全是需要指针来索引的）

同时根据上面的理论（实际上不是创造的定义，而是图论和公理化集合论的力量），我们可以根据上述边的数组进行扫描，判断两个图是否相等。

而我们希望寻找诸如包含顶点2的所有边，那么我们可以有一个索引表，每个记录包含两个内容（作为小端点时，最大大端点的存储位置，作为大端点时的第一个存储位置）。例如 顶点2，则包含两个索引

small_pos = 2

big_pos = 4

而对于(2,0),(2,1)...比较好遍历。对于 (n+2,2)的情况其实也不难。每次访问完当前的 small_pos时，可以知道对应的大端点的值例如 5，由此可以直接简单的通过索引表对应4的位置，找到 4的big_pos。再搜索是否有 (4,2)边。

当然，你可能会说这样还是慢。不过这样辅助信息很少。当然如果必要我们也可以单链表化嘛。任意e(x,y)存储的位置，存在个链表，指向 e(MAX(z),y)  z > y ，z < x

转载于: