[音乐] 嗨,欢迎回来。
接下来呢我们来讨论,图之间的关系。
那么图之间的关系呢会有哪些?首先呢是子图的关系。
那么所谓的子图呢,我们先定义两个图啊,G1和G2。
G1呢就当然就是V1,E1;G2呢是V2,E2。
那么如果说这个V1是V2的子集, 同时呢这个E1也是E2的子集的话,那么
我们就把这个G1就称之为G2的一个子图。
当然这个子图呢是通过子集这个关系来进行定义的,是吧?就很容易理解。
那比如说下边这个图,这个蓝色的和中间的这个红色的。
那么红色的呢,它是这个两个V呢它是相等的。
但是呢红色的这个边只有3条,然后左边这个蓝色呢,它的边呢,
有6条,那么所以呢,而且呢就是3条边是6条边的一个子集。
所以我们说 中间这个红色的图是左边这个蓝色的图的子图,这是一个 子图。
那么当然同样的,这个最右边这个绿色的这个图它也是
左边这个图的子图,但是呢它不是中间红色图的子图。
那么如果说这个G1不等于G2的话,
那么这个G1就称之为G2的一个真子图。
这个跟子集与真子集的 这个定义的差别是一样的。
然后接下来呢还有一个所谓的生成子图的概念。
那么什么是生成子图呢?就是说如果G1是G2的子图,而且呢是V1等于V2的话,
那么G1就称之为G2的一个生成子图。
那么所谓的生成也就是说,只要在G1当中, 添加若干条边,它不需要添加结点,
只需要添加若干条边就能够达到这个G2,就等于G2,那么这就是所谓的生成。
那当然这个中间这个红色的图是左边这个蓝色图的生成子图;
那么右边这个绿色的图也是左边这个蓝色图的生成子图。
然后呢,第二个关系呢, 图和图之间的关键就是所谓的补图的关系。
什么是补图? 那么我们把G1,G2呢互称为补图,它是这样子的,首先呢V1要等于V2。
然后其次接下来,它们的边集的交集要一定要为空。
第三个呢是说,把边集,两个边的集合做一个并集,
并集之后,再加上这个顶点集,它是一个完全图。
那么这样呢,我们就把这个G1,G2称之为互称,是叫做补图。
那么下面这个三个图的例子也是一样,最左边这个是一个作为对照,它是一个完全图。
对吧?是一个K5。
那么中间这个 红色的图呢,和右边这个绿色的图,
它们的这个边集,交集是为空。
然后呢,如果把这个两个图叠在一起,我们就会发现,它 正好等于K5。
所以呢,这红色和绿色图这两个图呢,是 称之为互为补图。
这个呢也是两个图之间的一个关系。
那再进一步的,图和图之间的关系呢,
还有更加复杂的关系,这里头所谓的一个叫做图的同构, 图的同构。
那么同构呢,是由两个同样也是两个图之间的关系,我们就提出G1和G2。
G1呢是V1,E1;G2呢是V2,E2。
那么它首先要满足一个条件就是 V1,V2,E1,E2,它们的这个基数要相等。
也就是说,它们所包含的这个顶点的个数和边的条数, 是要一致的,对吧?这是首先一个条件。
那么其次呢, 它这是一个本质的条件。
就是说如果能够把这个V1当中的所有的结点 做一个重编码,就是一一对应的映射
置换成V2当中的一个结点的话。
那么我们知道如果这个进行了置换以后,那么随之呢,
这个E1它也会变成,自动地就会变成E2。
如果存在这样的一个一一对应, 那么我们就把这两个图呢,称之为是一个同构的图。
也就是说,在存在一个双射函数,对吧?双射函数。
双射函数呢,它把这个V1映射为V2,那么同时呢,
又能够把E1变成E2的话,那么就称之为这两个图是一个同构的图。
比如说这个下方的这个图,一个是五边形, 一个是五角星。
看起来它们好像很不一样, 但是呢,如果我们仔细地观察,把这个五角星
的这个顶点啊,最顶上这个顶点 最上面的顶点把它挪,挪到最下方。
然后把这个左边这个顶点,挪,挪到右下方的话,我们就会发现,如果经过这样的一个操作,
移动或者说叫做置换的话,那么它就会变成一个五边形了。
所以它们是一个 互为同构的图。
那么什么是不同构呢?当然我们可以举出很多不同构的图的例子,
当然在别的这个学科里头也会有更加生动的例子。
我们这边来看看化学当中的例子,我们学过化学呢, 都知道在高中化学里面都有一个叫做同分异构体。
也就是说它分子是相同,但是呢它们的这个分子的结构不同,这样呢会
引起说,它虽然它的分子量是一样的,但是会体现出完全不同的化学性质。
它是完全不同的两种物质。
我们有一个很 熟悉的例子,就是C2H6O,
2个碳原子,6个氢原子和1个氧原子, 这是一个分子式啊。
那么它有不同构的, 不同的构造就变成了像C2H5OH
的乙醇,这个很熟悉,我们就是称为酒精的这个东西。
它呢是有一个OH,也就是一个氢氧,有一个羟基。
然后呢, 有两个碳原子是,碳原子之间是直接相连的。
那么如果换一种结构,同样是
这些原子,同样地也是有这么多条这个 叫做分子键,那么它会变成另外一个东西。
把这个 氧原子放在中间,然后两端呢又接了两个甲基,
CH3OCH3,那这个呢就变成了甲醚。
那么一个是醇类,一个是醚类,当然它这个化学性质就完全就不一样了。
所以呢,我们就把这种分子式是相同,但是呢结构和化学性质都不一样的这个化合物之间
就互称为同分异构体。
那么这里头的分子式 相同,实际上就意味着这个我们在同构图里头那个条件V1等于V2,
对吧?那么既然在原子 它构成的这个原子都一样,根据这个化学键的原理,
那么它们所能够链接出来的这个边实际上也是一样的。
所以 E1的基数肯定是等于E2的基数,但是呢, 只是键不一样。
比如说这个在乙醇当中,碳和碳之间有一个连接, 在甲醚当中,碳和碳就没有连接,就是这样。
所以我们说在 这个同分异构体的这个概念之下,它们是两个不同 的图。
如果我们把每个原子都当做是一个结点, 而把这个化学键当做是一个边的话,那么
这同分异构体之间,它就是一个不同构的图。