图论基础知识——顶点

通过上文的故事版和正经版的对比，可以很容易得看出，顶点也就是问题引入中的四块陆地——即，河的两岸，两个小岛。

那么，抛开这个问题，顶点又是什么呢？

顶点在上述问题中就是所谓的

顶点（vertex）的首字母是V，所以就理所当然的，用V来代表顶点。

顶点，毫无疑问，是一个点，这个点可以有一条边，也可以有n条边。

图论基础知识——边

既然已经讲到边了，那还是顺便也提一下边吧。

所谓边，也就是上面例子里提到的七座桥。

边（edge），因首字母为E，故简记为E。

在图论中，一般，我们用G来表示图，具体原因……还是因为图的英文首字母是G……

所以，一个图常常写作G=(V,E)。

我们可能还会见到这样的写法：

V={a,b,c……}

E={e1,e2,e3……}

这里就是集合的形式了，也就是把所有的顶点和边都分别装到两个分别叫V和E的塑料袋里

→一个图是一个有序的二元组<V，E>，记作G，其中：

(1)

是有限非空集合，称为顶点集，其元素称为顶点或结点。

(2)

是有限集合，称为边集，E中每个元素都有V中的结点对与之对应，称为边。

边e既可以是有向的，也可以是无向的。有向边与有序结点对

对应，这时称u为e的起点，v为e的终点。无向边与无序结点对

对应，u，v称为e的两个端点。

要注意：元素不能重复//感觉我在说废话

也就是同一个元素只能出现一次

手绘版的小鬼图遭到各种嘲笑，就不放这里了，后面用到再说╮(╯▽╰)╭

采用图这一名称，是因为他们可以用图形来表示，而这种图形表示有助于人们理解图的许多性质。图论中的大多数定义和概念是根据图形表示提出来的。如果顶点v是边e的一个端点，则称边e和顶点v相关联（Incident)，反之亦然。对于顶点u和v，若（u，v）∈E，则称u和v是邻接或相邻（Adjacent）的；若两条边有共同的顶点，则也称这两条边是相邻的。

两个端点重合的边（度=2），称为环（Loop），端点不重合的边称为连杆（Link）。关联于同一对顶点的两条或两条以上的边称为多重边（Multiple Edge）。

§有向图&无向图

问题引入

首先，请大家回忆一下高中的知识——向量，当时我们老师是这么解释的，向量就是有方向的量。

什么是有方向的量？直观感受就是带有箭头的线段，更直接的说法就是比起标量，向量多了方向。

再换个角度，看看向量的近义词——矢量。无论是高中物理还是初中物理都提到了一个概念——力，然后还有一种常见的入门题（受力分析）：

这里，那个带着箭头的G就是有向图（虽然只有两个顶点和一条边）。而我们常见的图形很多都属于无向图，比如上面提到的七桥问题。

如果还是觉得抽象，就联想一下单行道（只允许一个方向通行）——这个即为有向图，

那种双向N车道就可以称为是无向图的边（手动滑稽）

§度&图的同构

定理②：（握手引理），对每一个图G=（V，E），均有：

显然，任何图中所有顶点的度的和必为偶数。====》③

图的同构

什么是同构呢？

假设，我们有两张图G1和G2

G1=（V1，E1）

G2=（V2，E2）

    ①若V1 V2之间有一个双射（一一映射）θ

                  θ：

                              V1→V2

    ②满足x1,y1在G1中邻接←→x2,y2在G2中邻接

这样说似乎很抽象//就是很抽象好吗(╯‵□′)╯︵┻━┻

下面通过图片说明：

这就是一个同构的栗子

θ:

a→u

b→v

c→w

d→x

好了，我们再举一个例子：

我们还按照上面的方法构造

θ：

a→u

b→v

c→w

d→x

这个构造……(╯‵□′)╯︵┻━┻，什么鬼构造

如果按照

b→w

c→v呢

(＾Ｕ＾)ノ~ＹＯ==》这两个图还是同构的。

下面补充一个结论：

知乎：有什么算法能确定两图同构

感谢@今天不打怪捉虫