个性化阅读
专注于IT技术分析

图论介绍

本文概述

图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所示
图论介绍
图论介绍

赞(0)
未经允许不得转载:srcmini » 图论介绍

评论 抢沙发

评论前必须登录!