S1图的基本概念图、连通图、赋权图1图图论中的图与几何图形的区别几何图形：强调几何要素（如长度、角度、面积、形状等）的准确性（如桥的准确位置、长度、岛的面积大小）图论中的图：不关注几何要素的准确性，强调点的数量及点之间关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥以及有几座桥）Aese2eie6BCDere3esB6两个图在图论中完全相同图的基本概念
6 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念 图论中的图与几何图形的区别 几何图形： 强调几何要素（如长度、角度、面积、形状等）的 准确性（如桥的准确位置、长度、岛的面积大小 ） 两个图在图论中完全相同 图论中的图： 不关注几何要素的准确性，强调点的数量及点之间 关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥 以及有几座桥） B C D e1 e2 e6 e5 e7 e3 e4 A A B C D
S81图的基本概念图、连通图、赋权图1图图的基本概念定义3-1：（图）对于点集V（非空）和边集E，如果任一边eEE对应于两个点u，VEV，则点集V和边集E的和集称为通常用点表示具体的或抽象的事物，而用边图，记作G=(V，E)。表示事物之间的某种联系，顶点：点集V中的点称为图的点。端点：边e对应的两个点u、v称为边eesDe6的端点，边e记作[u，v或[v，u]。关联边：边[u，v称为端点u、v的关联边。ea相邻点：有公共边的两个端点称为相邻e2B点。（与端点无异，多余）ei相邻边：有公共点的边称为相邻边。环：若边e的两个端点为同一点，则边e称为环7图的基本概念（续）
7 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念（续） 图的基本概念 顶点： 定义3-1： A D B C e2 e1 e3 e4 e5 端点： e6 关联边： 相邻点： 相邻边： 环： 通常用点表示具体的或抽象的事物，而用边 表示事物之间的某种联系
81图的基本概念图、连通图、赋权图1图图的基本概念（续）多重边：若两个点之间多于一条边，则这些边称为多重边。多重图：含有多重边的图称为多重图。简单图：无环无多重边的图称为简单图。esA图的阶：图中顶点的个数称为图的阶。顶点的度：以>为端点的边的条数称为点！ea的度，记作deg(v)或d(v)enBC偶点：ei度为偶数的点称为偶点。规定环计算两次奇点：度为奇数的点称为奇点。8图的基本概念（续）
8 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念（续） 图的基本概念（续） 多重图： 多重边： A D B C e2 e1 e3 e4 e5 e6 简单图： 图的阶： 顶点的度： 偶点： 奇点： 含有多重边的图称为多重图。 无环无多重边的图称为简单图。 图中顶点的个数称为图的阶。 以v为端点的边的条数称为点v 的度，记作 deg(v)或d(v) 度为偶数的点称为偶点。 度为奇数的点称为奇点。 规定环计算两次
S1图的基本概念图、连通图、赋权图1图图的基本概念（续）孤立点：度为零的点称为孤立点。E悬挂点：度为1的点称为悬挂点。eesDA悬挂边：与悬挂点关联的边称为悬挂边Fes所谓连通图，即图中任意两点都能通过一系e2B列顺序相连边通达，这一系列顺序相连的边C称为链。e192.连通图
9 §1 图的基本概念 一、图、连通图、赋权图 1. 图 2. 连通图 图的基本概念（续） 悬挂点： 孤立点： A D B C e2 e1 e3 e4 e5 e6 悬挂边： 度为1的点称为悬挂点。 与悬挂点关联的边称为悬挂边。 E F 度为零的点称为孤立点。 所谓连通图，即图中任意两点都能通过一系 列顺序相连边通达，这一系列顺序相连的边 称为链
S1图的基本概念一、图、连通图、赋权图2联通图2.连通图定义3-3（链、圈）：设u={v，e,，v,，e,，Vi, e,, v.为图G的一个点边交替序列（下标不一定是递增的顺序），若其中的每条边均满足e,=[v,，v」，则称这个序列μ为从点v,到v即各边顺序相连的一条链；若vi=v，则称μ为一个圈。以下概念也适用于圈V2V6简单链：所有边不重复的链车（即各边互不重复）。初等链：所有点不重复的简单链（即点边均不重复）。V3V5连通图：若图中任意两点之间至少存在一条链，则图称为连通图，否VV4则称为不连通图。10在不致引起混淆的情况下，可将链u简记为u=enen,e或u=i,n，"。3.赋权图
10 §1 图的基本概念 一、图、连通图、赋权图 2.联通 图 3. 赋权图 2. 连通图 定义3-3（链、圈）： 简单链：所有边不重复的链（即各边互不重复）。 v1 v2 v3 v4 v5 v6 v7 即各边顺序相连 以下概念也适用于圈 初等链：所有点不重复的简单链 （即点边均不重复）。 连通图：若图中任意两点之间至少存在 一条链，则图称为连通图，否 则称为不连通图