什么是图论中的平凡图

平凡图

平凡图属于离散数学与图论的范畴。

平凡图的定义：

1.仅有一个结点的图的称平凡图。

2.平凡图又被称为平凡树。

4.平凡图是连通图、欧拉图、哈密顿图。

3.由孤立点组成的图叫做零图，由一个孤立点组成的图叫做平凡图，因而平凡图一定是零图。

平凡图存在桥的，连通且无回路的无向图称为无向树，或简称树，常用T表示树。平凡图称为平凡树。无向树中度数为1的顶点称为树叶，度数大于等于2的顶点称为分支点：若无向树T至少有两个连通分支，则称T为森林。也就是说，(无向)树是连通无回路的简单图，后面提到树时，如果没有特别说明都是指无向树，树的每一条边都是桥。

无向图对应的邻接矩阵出现的数不能大于1对不对

亲，这个是对的

在一个偏序关系中，某个子集如果存在唯一的极大元，那么这个极大元也是唯一的最大元

这个是错误的

非负整数列d等于（1,1,1,1,2）对应简单图G，则p（G）等于一对不对

这个是正确的

度数列d等于（4,3,2,4,1,1）对应的无向图G是一个半欧拉图对不对

这个是对的

非空集合A上的空关系具有什么性质

空关系一定指某非空集合A上的空关系,A上的关系R具有反自反性,要求对任意的A中的元素x,不属于R,空关系是没有任何序偶的关系,显然空关系具有上述特征,故空关系具有反自反性.

现有无完全简单图G，同时图G也是3-正则图，则图G的边数为多少

由于G是极大平面图，所以G为简单图，且无桥无环，所以G中无桥，所以G是2边-连通图。由于n≥ 4，G两个面至少有一条公共边，G为简单图，所以G每个面出现的次数为3，所以G每个顶点的边数为3，所以G*是3-正则图。

分享

评论

点赞

问题还没解决？快来咨询专业答主~

平凡图存在桥吗

在线

4180位答主在线答

服务保障

专业

响应快

马上提问

韩国化妆品价钱 一手货源 日韩化妆品代购 诚招代理加入

值得一看的韩国化妆品相关信息推荐

韩国化妆品价钱︱韩国-日本-香港直邮︱保证正品︱比专柜价格便宜50%︱可一件代发︱大牌美妆代购 ︱价格实惠︱应有尽有︱可防伪查询︱带购物小票︱

qianhu.wejianzhan.com广告

艺考学校哪家好，专注艺考培训25年，专业齐全，实力强劲!

艺考学校哪家好，天籁艺术学校，专注艺考25年。全专业开设美术，音乐，传媒，舞蹈等专业。课堂教学风格多样化，学习氛围浓厚。艺考学校哪家好，目前已输送10万余名艺术生进入大学。

热门课程

师资力量

校内设施

优惠活动

点击咨询了解更多详情

咨询

c.tianlaijiaoyu.com广告

环氧彩砂美缝剂的施工方法-淘宝综合购物平台，年终盛典，优惠不停!

水性环氧彩砂美缝剂填缝剂靓缝剂勾缝神器环保抗菌瓷砖地墙砖专用

￥32 元

水性环氧彩砂美缝剂环保瓷砖地砖专用桶装美缝剂防水填缝剂一公斤

￥43 元

环氧彩砂美缝剂水性瓷砖地砖专用防水填缝剂家用桶装美缝剂一公斤

￥28 元

环氧彩砂美缝剂瓷砖地砖专用填充缝隙美逢胶家用防水水性填缝彩沙

￥116 元

环氧彩砂美缝剂填缝剂哑光水性家用填缝剂瓷砖地砖专用防水防霉

￥197.5 元

simba.taobao.com广告

平凡图存在桥吗

解答专家小穆

活跃之星

平凡图不存在桥

2022-12-28

已解决3303人问题

— 为您推荐相似问答 —

lowara 水泵销售_ 洹水致远

值得一看的lowara水泵相关信息推荐

洹水致远（北京）科..广告

热水器增压泵适用于增压泵家用 自来水增压泵 小型家用全自动静音太阳能热水器管道加压水泵瞬子 标准款100W自动+标配

￥138 元￥3739 元

购买

京东广告

正在加载

电脑版 ©2023 Baidu

京ICP证030173号-1 京网文【2013】0934-983号

平凡图存在桥吗

历史：1736年 19世纪

应用：计算机科学、化学、运筹学、经济学、语言学等

内容：图的基本概念、包括 路径和环,欧拉回路，哈密尔顿回路/货郎担问题，图同构、平面图等。

①定义中的结点对可以是有序的，也可以是无序的，若边e所对应的结点对e i =<v i1 ,v i2 >是有序的，则称e i 是有向边，若边e所对应的结点e i =<v i1 ,v i2 >，i=1,2,…,n是无序的，则称e i 是无向边。

②有向边简称弧,v i1 称为弧e i 的始点, v i2 ,称为弧e i 的终点,统称为e i 的端点.无向边简称棱。

① 有限图: V,E 均为有限集。

② n 阶图: IVl=n.其中,IVI指的是结点集合V的结点的个数。

③ 零图: E=∅.即图中没有边,只有孤立点。

④ 平凡图: E=∅且IVI=1.即只有一个孤立点构成的图。

⑤ 多重图: 含平行边的图。

⑥ 简单图: 既不含平行边也不含环的图。

⑦ 完全图：

1、无向图结点的度数

设G=<V,E>为无向图,与顶点，关联的边的条数称为v的度,记作 deg(v)。

约定:每个环算两条边,则环的度数为2。

最大度:△(G)max{d(v)lv∈V} 最小度,δ(G) min{d(v)lv∈V}。

由定义可知零图中各点度数为0，完全图k n 各点的度数为n-1。

定理1

设图G是具有n个结点、m条边的无向图,具中结点集合为V={v 1 ,v 2 ,…,v n },则

即顶点度数之和等于边数之和的两倍

定理1是显然的,因为在计算各点的度数时,每条边都计算两次,于是图G中全部顶点的度数之和就是边数的2倍.

定理2

在任何无向图中，度数为奇数的结点必定是偶数个。

2、有向图结点的度数

设D=<V,E>为有向图,以顶点v为起始结点的弧的条数称为结点v的出度,记作 deg + (v).以顶点v为终止结点的弧的条数称为v的入度,记作 deg - (v).入度和出度之和称为顶点v的度,记作deg(v).显然有

定理3

在任何有向图中，所有节点的入度之和等于所有节点的出度之和，即

3、度数序列

设V={v 1 ,v 2 ,…,v n }为图G的顶点集，称{d(v 1 ),d(v 2 ),…d(v n )}为G的度数序列。

习题：P261 1,4,7,10,20,30

在有向图中,从顶点v 0 到顶点v n 的一条路径是图中的边的序列,其中每一条边的终点是下一条边的起点。

如果V(H)⊆V(G)且E(H)⊆E(G),则称H是G的子图，记作H⊆G。

若H是G的子图且V(H)=V(G)，则称H是G的支撑子图（或生成子图）

设图H=<V',E'>是图G=<V,E>的子图。若对任意结点u∈V'，v∈V'，如果(u,v)∈E,有(u,v)∈E',则H由V'唯一地确定，并称H是结点集合V'的点诱导子图,记作G(V')；如果H无孤立结点，且由E'所唯一确定，则称H是边集E'的边诱导子图，记作G(E')。

例： 图7.9中，图(b)与(c)均为(a)的子图，(c)为(a)的支撑子图，(b)为(a)的点诱导子图也是(a)的边诱导子图。

例：图7.10中，(a)--(f)都是(a)的子图，其中(a)--(d)为(a)的支撑子图，(e)为(a)的点诱导子图，(f)为(a)的边诱导子图。

1、无向图中两顶点的连通

在一个无向图G中，若从顶点u到v存在通路，则称u与v连通。

规定：u到自身总是连通的。

2、有向图中两顶点的可达

在一个有向图D中，若存在从顶点u到v有向通路，则称u可达v。

规定：u到自身总是可达的。

有向通路是有方向性的，所以在有向图中，若u可达v，但反之不成立 。

3、无向图的连通性

在无向图中，若从顶点v 1 到顶点v 2 有路径，则称顶点v 1 与v 2 是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图，否则称G是非连通图。

4、有向图的连通性

一个有向图D=(V,E)，将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图.如果一个有向图的基图是连通图，则有向图D是弱连通的，否则称D为非连通的.若D中任意两点u,v都有从u可达v，或从v可达u,则称D是单向连通的若D中每点u均可达其他任一点v,则称D是强连通的.

经过图G的每条边一次且仅一次,而且走遍每个结点的通类,称为欧拉通路。

经过图G的每条边一次且仅一次的回路,称为欧拉回路,具有欧拉回路的图称为欧拉图。

注:①欧拉回路要求边不能重复,结点可以重复.笔不离开纸,个里及地疋元所有的边且走过所有结点,就是所谓的一笔画.。

②凡是一笔画中出现的交点处,线一出一进总应该通过偶数条(偶度点),只有作为起点和终点的两点才有可能通过奇数条(奇度点).

习题：P271,1,4,13,21,22,34

定义 ：经过图中每个顶点一次且仅一次的通路(回路),称为哈密尔顿通路(哈密尔顿回路).存在哈密尔顿回路的图叫哈密尔顿图.

注意：欧拉图与哈密尔顿图研究目的不同,前者要遍历图的所有边,后者要遍历图的所有点。

虽然都是遍历问题,两者的困难程度却大不相同.欧拉图问题,欧拉已经解决了,而哈密尔顿问题却是一个至今仍未解决的难题,在大多数情况下,人们还是采用尝试求解方法来解决。

哈密尔顿图的判定定理1

设G是n(n≥3)阶无向简单图.

①若G中任何一对不相邻的顶点的度数之和都大于等于n-1,则G中存在哈密尔顿通路

②若G中任何一对不相邻的顶点的度数之和都大于等于n,则G是哈密尔顿图.

哈密尔顿图的判定定理2

在n(n≥2)阶有向图D=<V,E>中,如果所有有向边均用无向边代替,所得无向图中含生成子图K。,则有向图D中存在哈密尔顿通路.

推论n(n≥3)阶有向完全图是哈密尔顿图.

欧拉:每条边一次

哈密尔顿(H回路):每个节点一次可能有哈密尔顿回路，没有欧拉回路

哈密尔顿回路还没找到简单的判别条件

20节

---