图论介绍

本文概述

• 顶点度
• 路径

图G由两部分组成：

1.一组V = V（G）, 其元素称为G的顶点, 点或节点。

2.称为G的边的无序对不同顶点对的集合E = E（G）。

3.我们用G（V, E）顶点表示这样的图, 如果存在边e = {u, v}, 则称u和v相邻。

4.在这种情况下, u和v称为e = {u, v}的端点, 并且说e连接了u和v。

顶点度

顶点的度数是入射在顶点v上的边数。自循环计数两次。顶点的度数由d（v）表示。

例1：考虑图5所示的曲线图G。确定每个顶点的程度。

解决方案：每个顶点的度如下：

d（a）= 3； d（b）= 5； d（c）= 2； d（d）＝ 2。

例2：验证所有顶点的度之和对于图所示的图是偶数：

解决方案：所有顶点的度数之和为：

= d（v1）+ d（v2）+ d（v3）+ d（v4）+ d（v5）+ d（v6）+ d（v7）+ d（v8）= 2 + 3 + 3 + 3 + 3 + 4 + 2 + 2 = 22, 是偶数。

示例3：验证在图所示的图中有偶数个奇数度的顶点：

解决方案：奇数度的顶点数为8, 并且在上图中每个度数为3。因此, 我们有奇数个顶点的偶数个。

路径

长度为n的路径是图的n + 1个顶点的序列, 其中每对顶点是图的边。

1. 简单路径：如果路径中没有重复边缘, 则该路径称为简单路径, 即, 除了第一个顶点等于最后一个顶点之外, 所有顶点都是不同的。
2. 基本路径：如果路径中没有重复顶点, 即所有顶点都不同, 则该路径称为基本路径。
3. 电路或闭合路径：电路或闭合路径是在相同顶点处开始和结束的路径, 即v0 = vn。
4. 简单电路路径：简单电路是一条简单路径, 即一条电路。

示例：考虑图中所示的图形：给出以下示例：

1. 从V1到V6的简单路径。
2. 从V1到V6的基本路径。
3. 从V1到V6的基本路径不是基本路径。
4. 从V2开始的路径并不简单。
5. 从V1开始的简单电路
6. 从V2开始的电路并不简单。

解：

1. 从V1到V6的简单路径。 V1, V2, V3, V4, V5, V6。
2. 从V1到V6的基本路径。 V1, V2, V3, V5, V4, V6。
3. 从V1到V6的基本路径不是基本路径。 V1, V2, V3, V5, V2, V4, V6。
4. 从V2开始的路径并不简单。 V2, V3, V4, V5, V3, V4, V6。
5. 从V1开始的简单电路。 V1, V2, V4, V6, V5, V3, V1
6. 从V2开始的电路并不简单。 V2, V3, V1, V2, V5, V4, V2。

垂线顶点：度为1的顶点称为垂线顶点。

下垂边缘：唯一与下垂顶点有关的边缘称为下垂边缘。

奇数顶点：具有奇数阶的顶点称为奇数顶点。

偶数顶点：具有度数偶数的顶点称为偶数顶点。

事故边缘：一条称为顶点的事故与顶点相连。

相邻顶点：如果一条边链接, 则两个顶点称为相邻顶点。如果存在边（u, v）, 则可以说顶点u与顶点v相邻, 而顶点v与顶点u相邻。

示例：考虑如图所示的图形：

确定以下内容：

1. 在顶点期间
2. 在边缘
3. 奇数顶点
4. 顶点
5. 入射边缘
6. 相邻顶点

解：

1. 顶点V5是悬垂顶点。
2. 边缘（V4, V5）或e5是悬垂边缘。
3. 顶点V3和V5是奇数顶点。
4. 顶点V1, V2和V4是偶数顶点。
5. 边缘e1是V1和V2上的入射。边缘e2是V1和V3上的入射点。边缘e3是V2和V3上的入射。边缘e4是V3和V4上的入射点。边缘e5是V4和V5上的入射点。
6. 顶点V1与V2和V3相邻。顶点V2与V1和V2相邻。顶点V3与V1和V4相邻。顶点V4与V3和V5相邻。顶点V5与V4相邻。

自环：如果自环具有相同的端点, 则它是边e。

图中所示的图包含顶点b处的自环, 即e =（b, b）。

孤立顶点：度为0的顶点称为孤立顶点。

割集（Cut Set）：考虑一个图G =（V, E）.G的割集是边的最小集合, 因此移除该集会断开图的连接, 而移除该集的任何适当子集则会留下一个相连的子图。

示例：考虑图5所示的图形。确定该组的切割组。

解决方案：对于此图, 边集{（V1, V5）, （V7, V5）}是切割集。删除集合后, 我们留下了断开连接的子图。删除其任何适当的子集后, 我们留下了一个相连的子图。

切点或切点：考虑图形G =（V, E）。曲线图G的切点是顶点v, 因此G-v的连接分量比G或断开的分量多。

子图G-v是通过从图G删除顶点v并删除入射在v上的整个边而获得的。

示例：考虑图5所示的图形。确定子图

（i）G-v1（ii）G-v3（iii）G-v5

解：

1. 子图G-v1如图所示。
2. 子图G-v3如图所示。
3. 子图G-v5如图所示。

桥（切边）：考虑图G =（V, E）。图G的桥是边e, 因此G-e的连接组件比G多或断开。

示例：考虑图5所示的图形。确定子图

（i）G-e1（ii）G-e3（iii）G-e4

解：

1. 子图G-e1如图所示
2. 图G-e3所示
3. 图G-e4所示