求图论及其应用的题目.

离散数学图论证明题第四题,麻烦详细一点

haoyaner1年前2

sphinxisme 共回答了16个问题 | 采纳率87.5%

根据握手定理,所有点的度数之和等于边数的2倍,即2e.
每一个点的度数都大于等于δ,小于等于△,所以所有点的度数之和大于等于vδ,小于等于v△,所以vδ≤2e≤v△,即δ≤2e/v≤△.

1年前查看全部

图论中parity subgraph什么意思

终点是起点1年前0

共回答了个问题 | 采纳率

查看全部

一道图论题求证：在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.

昨天的茄子1年前3

无相无我99 共回答了18个问题 | 采纳率88.9%

我用反证法来证明.事实上要满足“任何两人都刚好只有一个共同认识得人”这个条件的这群人必须是奇数.
首先用一个点来代表一个人,如果A认识B,就在AB间连一条线,这样整个关系生成一个无向图G.
那么由“任何两人都刚好只有一个共同认识得人”,能得出G中没有4边形,即不存在4点A,B,C,D使得,A与B,B与C,C与D,D与A之间均有线相连.
设连线最多的点为P,与它相连的点为Q1~QK,不与它相连的点为R1~RL(L>0).
1.根据P与Q1~QK中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出Q1~QK这K个点必满足K
为偶数且这些点之间的连线情况必定是分为K/2个组,每组2个点它们之间有连线,除此之外Q1~QK间无其它连线；否则会有某对点的“共同认识得朋友”超过1个.
2.根据P与R1~RL中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出每个R1~RL中的点只与
P1~PK中的一个点有连线；否则会有某对点的“共同认识得朋友”超过1个.
3.根据Q1~QK中每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1与2的结论可以得出Q1~QK中的每个点都与R1~RL中的点有
连线；否则会有某对点的“共同认识得朋友”超过1个.
4.再取Q1~QK中按照1分组的其中两组中的每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1,2,3的结论,就能得出存在
某对点的“共同认识得朋友”超过1个的结论,矛盾!

1年前查看全部

hyper graph是什么图论中超图（hypergraph）怎么理解楼上的不要乱搞。超图是图论中概念。你不要随便搜搜就

hyper graph是什么
图论中超图（hypergraph）怎么理解
楼上的不要乱搞。超图是图论中概念。
你不要随便搜搜就贴上来

islameversky1年前1

313956314 共回答了472个问题 | 采纳率

超图
开放分类： IT、GIS
今年的GIS大会上，超图公司一时风光无限，地理信息技术从来没有像现在一样，得到社会广泛的认同和接受。我国国民经济和社会发展‘十一五’规划纲要明确提出发展地理信息产业，国家中长期科技发展规划纲要也明确要发展地理空间信息的新技术和新方法。几年前，GIS作为信息产业中比较小的一块，还不为人所关注，直至近两年，作为数字城市之基础的GIS大规模应用越来越为人...

1年前查看全部

离散数学图论的一个小问题

王海岛1年前1

匡宇飞 共回答了18个问题 | 采纳率94.4%

因为问题是G中至少有几个顶点
至少！
所以不考虑1度的
不懂请追问，有帮助请采纳，谢谢！

1年前查看全部

acm 图论吃豆豆 Time Limit:1000 MS Memory Limit:32768 K Total Subm

acm 图论
吃豆豆
time limit:1000 ms
memory limit:32768 k
total submit:25 (16 users)
total accepted:15 (15 users)
special judge:no
description
一天woods和他的grilfriend（gf）来到了一个童话王国的小镇里,镇上有许多豆豆（如下图中的每个圆形为一个豆豆）,每个豆豆有通向东,南,西,北,东南,东北,西北,西南八个方向的道路.其中直线道路的距离为1米,斜线道路的距离为根号2米.gf一看见吃的就饿了……你能算出吃且只吃所有豆豆一次,最后回到起点的最短路程吗?
如图所示为一个2
x 3的图,最短距离（如***所示）为6米.
input
多组测试数据.每组测试数据一行,包括两个整数n,m（1 < m < 50 and 1 < n <
50.）,代表图的大小为n行m列.
output
对于每组数据输出一行,输出吃且只吃所有豆豆一次,最后回到起点的最短路程.（精确到两位小数）.
sample input
2 2
2 3
sample output
4.00
6.00
hint

一山一水一湾1年前1

menshan 共回答了19个问题 | 采纳率89.5%

最小生成树题目POJ：1251 1258 2395 2485 2560
最短路径POJ：1797(易） 1062（难）1125（难)
我也是在hdoj上做题的 不过练习图论的时候在poj上做的
hdu1102,1233 这俩是hdu的,后来随便做题的时候碰到的
希望对你能有所帮助.

1年前查看全部

图论里面的K5,K33这样的符号指什么图?

图论里面的K5,K33这样的符号指什么图?
例如,K5是什么?特指完全图吗,也就是5个顶点,两两之间都有边的图?
那么K3,3又是什么?特指2部图吗?

sdfsdfddsadf1年前1

梯梯 共回答了14个问题 | 采纳率85.7%

K5是5阶完全图,每一顶点与其他所有顶点都有边.
k3,3是2步图.上下顶点分别为3.

1年前查看全部

为什么 在图论这部分中 各种书对路 回路 通路 初等回路等等定义都不相同呢

为什么 在图论这部分中 各种书对路 回路 通路 初等回路等等定义都不相同呢
谁能给一个比较准确的定义啊

zxylove0081年前1

俄日i图 共回答了13个问题 | 采纳率92.3%

不要纠结于表象,抓住本质就行了.就连自然数的定义,从小学到大学还一直在变呢（不能说后来的定义一定比之前的定义更准确,只是基于的理论体系不同）,每一种定义方式都有其出发点,易于你理解的就是对你更准确的,多看几本经典比较比较,有些定义只是文字描述上不同,而另一些则是整个理论体系有区别,但目的都是为了解释同样的问题.当你意识到不同定义之间的真正差别时,你就不需要大家来回答这个问题了.

1年前查看全部

管理运筹学的图论中最小部分树有哪几种求解方法?

gfhgty54gh1年前1

心融化 共回答了21个问题 | 采纳率90.5%

1、破圈法 2、避圈法 3、顺序生枝法

1年前查看全部

求 大学数学体系、结构图比如说,数论,复变函数,概率论,数理统计,计算几何,线性代数,运筹学,复分析,实分析,图论,代数

求 大学数学体系、结构图
比如说,数论,复变函数,概率论,数理统计,计算几何,线性代数,运筹学,复分析,实分析,图论,代数,博弈论,拓扑学等等等等.
希望得到一个答案能够说清楚这些分支（包括我还没有列出来的分支）之间的关系,是学习其他分支的基础的关系,还是并列的关系,或是包含关系,或是其他的关系.
最好有一张结构图.

这么不开心1年前1

穿JACKJONESww 共回答了30个问题 | 采纳率96.7%

你这张图太杂,不同专业选学不同模块.不过最先学的是高等数学（里面包括微积分、解析几何初步和常微分方程基础）、线性代数（这是代数中的一块内容,主干内容是解线性方程组,代数的研究范围就更广、更抽象了）、概率论和数理统计.
然后再学其他的,有了上述基础,其他的就可以并列、交叉学了.
看你列举出高等数学而不是数学分析,说明你不是数学专业的学生,那么很多分支是你不用学的,先学好最基本的吧.另外,你说的“具体数学”是什么东东?没听说过

1年前查看全部

图论问题：证明最小度大于一的图必含回路,反之成立吗

edwardamp1年前3

江民杀毒王 共回答了24个问题 | 采纳率75%

反之肯定不对,如果一个图不止有环还有割点或割边呢,或者甚至有个孤立点.
额,你自己都说了是图论的问题,那当然就是图论啦,囧.应该不管什么图论书这都是第一章的内容.

1年前查看全部

图的最短路径条数?此题需要大家对图论的基本概念熟悉.不包含环的路径,称为简单路径.最短路：在起点和终点之间的所有简单路径

图的最短路径条数?
此题需要大家对图论的基本概念熟悉.
不包含环的路径,称为简单路径.
最短路：在起点和终点之间的所有简单路径中,长度最短的路径.
路径的不同性：如果两条简单路径不包含相同的边,则称这两条路径不相同.
现在给你一个有向加权图,起点和终点,让你求出这两点之间有多少条不同的最短路.
Input
多组测试数据.
每组数据的第一行是一个整数N（2

509522031年前1

wzh89898989 共回答了19个问题 | 采纳率89.5%

个人感觉用dijstra方法,由于是贪心,有可能在扩展的时候存在多条距离相同的边.我把它抽象为一棵树,由当前状态可以选择几条路径,就由其节点扩展为几个儿子.这样下来,最后得到的树有几个叶节点就有几条最短路径.
只是个想法,好像见过类似的题目,忘了怎么做了.感兴趣的话还可以研究一下求图有多少最小生成树和有多少生成树,两种完全不同的做法.

1年前查看全部

一道关于离散数学中图论部分的问题

一道关于离散数学中图论部分的问题
证明：若边e在G的某一闭迹中,则e在G的某一圈中

乐队和评委1年前1

liandxu 共回答了20个问题 | 采纳率85%

闭迹可分解成若干圈,所以e在某圈中.

1年前查看全部

一道高中数学竞赛图论题一个国际社团的成员来自六个国家,共有成员1978人,用1,2,3,到1977,1978编号,请证明

一道高中数学竞赛图论题
一个国际社团的成员来自六个国家,共有成员1978人,用1,2,3,到1977,1978编号,请证明,该社团至少有一个成员的顺序号数,与他的两个同胞的顺序号之和相等,或是一个同胞的二倍.

猥糟猫1年前0

共回答了个问题 | 采纳率

查看全部

求图论的生成子图算法,要求生成尽可能多的子图

求图论的生成子图算法,要求生成尽可能多的子图
有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽可能的多.
感觉应该就是图论的问题：把人看做节点,相互认识的两人就是联通的两点,问题就是尽可能多的找出包含4个节点的完全生成子图.
哪位高手能够给出应该用什么算法解决,或者给出思路也可,谢过!

落雨载歌1年前1

喻钊文 共回答了15个问题 | 采纳率80%

连通图的特点是图中任意两点都是连通的,也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图,否则就是不连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理：
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边（线段）定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如（v0,v3）(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点（1个或多个）取出,并加入到新数组CONPOINT中,并作未读标记（如果已有该点则不作插入）
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图

1年前查看全部

图论有哪些算法?除了floyd Dijkstra之外,具体点

hzlai20051年前1

mcuos 共回答了9个问题 | 采纳率88.9%

A.Prim算法、Kruskal算法、Floyed算法、Dijkstra 算法&amp和遗传算法等

1年前查看全部

图论中minors的问题书上说a contraction of an edge uv in graph G result

图论中minors的问题
书上说a contraction of an edge uv in graph G results in a graph G' where
the two vertices u,v are identified into a single vertex z,where z is
adjacent to all neighbours of u and v in G.

光子01年前1

ftruth 共回答了13个问题 | 采纳率100%

在图G中uv边缩减形成G'图,它的u,v两顶点合成一个顶点z,顶点z与G图中所有u,v的邻接点相邻

1年前查看全部

数学图论难题求解答设无向图G=={v1.v2.v3.v4.v5.v6}$={

十字芒果1年前1

shootv 共回答了18个问题 | 采纳率88.9%

难题?你可能不知道基本定义吧.
d(v1)=3,d(v2)=4,d(v3)=3,d(v4)=3,d(v5)=1,d(v6)=0,奇结点4个,偶结点2个.
过程就是数出来的,把G画出来就能说明了.

1年前查看全部

求教一道图论题!参加某次学术讨论会共有263个人,已知每个人至少和三位会者讨论过问题,证明至少有一个人和四位或四位以上的

求教一道图论题!
参加某次学术讨论会共有263个人,已知每个人至少和三位会者讨论过问题,证明至少有一个人和四位或四位以上的学者讨论过问题.

DJ哭了1年前1

亦咏 共回答了18个问题 | 采纳率94.4%

假设人为点,讨论过的两人之间连一条边、
则边数=每个人讨论过的人数之和/2
反证
假设每个人只和三位会者讨论过问题
按上面公式应有789/2条边,不可能
所以必定有一个人和四位或四位以上的学者讨论过问题.

1年前查看全部

图论：证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足：d(u)+d(v)>=n-1,则G有Hanmilton路

图论：证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足：d(u)+d(v)>=n-1,则G有Hanmilton路.

独孤野侠1年前1

10666666 共回答了22个问题 | 采纳率86.4%

http://web.nuist.edu.cn/courses/lssx/longtime/part4/chapter15/15_02_03_01.htm
记得采纳啊

1年前查看全部

什么是图论中的平凡图请通俗一点

狼格格1年前2

天山上的仙女 共回答了19个问题 | 采纳率94.7%

只有一个顶点的图

1年前查看全部

一道离散数学 图论的题目,含有5个结点,3条边的不同构的简单图有___个.A 2 B 3 C 4 D 5PS:有什么公式

一道离散数学 图论的题目,
含有5个结点,3条边的不同构的简单图有___个.
A 2 B 3 C 4 D 5
PS:有什么公式可以套公式直接算出来么?有的话请把公式告知.
没有公式的话请详细说下思路,主要是我不知道什么叫不同构,迷糊.要思路,怎么想的,别光给答案.
初学,知道的朋友帮助下,

拖鞋2006的hh三1年前1

书涵 共回答了17个问题 | 采纳率94.1%

简单图：无环、无多重边的图.
同构图：两个同阶图（点数为图的阶）,若定点集合与边集合之间在保持关系性质条件下一一对应,则为同构.
公式不知道,但是思路个人认为是列举法.
一共5点3边,且为简单图故必有一点有两边（及此点次为2）：
一是有一点次为3,故每点有2种可能,共10.（但是若题意是将各点视为同样则为1种）.
二是有一点次为0切无次为3的点,则每点仅有1种可能,共5.（但是若题意是将各点视为同样则为1种）.
三是有一点此为2,其余全是1,则每点仅有1种可能,共5.（但是若题意是将各点视为同样则为1种）.
故答案为B

1年前查看全部

证明!图论!证明：图G是连通的平面图,其点数为n,边数为e,则n-e+f=2

hbblxs1年前3

shoushou81 共回答了17个问题 | 采纳率94.1%

可以用归纳法证明.假设归纳面数f,
f=1,就是一个简单只有一个面的情况,好证明.
假设f>=3,想象平面图里最外的一个面F,它有一部分连续的边e1-n1-e2-n2-...-n_(p-1)-e_p（这里e代表边的编号,n代表点的编号,可以看出这个串里,边数比点数多1）.如果去掉这部分的话,将抹去这个面F（和外部打通）.假设抹掉这些边,在这个情况下,显然f减去了1.而n-e增加了1,所以n-e+f的值不变,可以继续用归纳假设.n-e增加1是因为这些连续边的两个端点留着,当中的点n被抹掉,而当中的边e也被抹掉,所以n-e是增加了1.可以不太容易讲清楚,但是就是这个意思,用归纳法,希望有用.

1年前查看全部

离散数学中树的概念问题离散数学中图论那章里有树的定义,说连通的无回路的无向图就是树,我不解,既然是连通的,怎么可能无回路

离散数学中树的概念问题
离散数学中图论那章里有树的定义,说连通的无回路的无向图就是树,我不解,既然是连通的,怎么可能无回路呢?万分感激!

xiaweicao1年前0

共回答了个问题 | 采纳率

查看全部

图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L.

图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L.
证明（1）L大于等于3（2）e小于等于[L/(L-2)]*(v-2)

ID都有人取了1年前2

风流才子s 共回答了14个问题 | 采纳率92.9%

此题应该已经不需要解答了吧

1年前查看全部

离散数学中有关图论中的极大连通子图的概念理解

离散数学中有关图论中的极大连通子图的概念理解
我看书上说 “任意增加结点或边所得的子图都是不连通的.”这句话不理解 谁能画图举例说明呀?

我是东天1年前1

lylt 共回答了18个问题 | 采纳率94.4%

一个图可能是不连通的,它的极大连通子图实际上就是一个连通分支.

1年前查看全部

图论中常见的最短路径算法有几种?都是什么?

图论中常见的最短路径算法有几种?都是什么?
只要列出有几种，分别是什么就行啦，嘻嘻~

风筝翱翔蓝天1年前2

巴黎的猪 共回答了27个问题 | 采纳率85.2%

主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

1年前查看全部

图论 最小部分树电信公司准备在v1…v7这7个城市之间架设光缆线,问如何架设使其光缆线路最短?下图给出了交通图.

图论 最小部分树
电信公司准备在v1…v7这7个城市之间架设光缆线,问如何架设使其光缆线路最短?下图给出了交通图. 最小部分树

轻舞的我1年前1

yxmjy1984 共回答了20个问题 | 采纳率95%

要求好像不明确?

1年前查看全部

33届IMO 3题 是图论还是组合几何类型题?若是组合几何,用的何种方法技巧来解.

33届IMO 3题 是图论还是组合几何类型题?若是组合几何,用的何种方法技巧来解.
给定空间中的9个点,其中任意4点都不共面,并在每一对点之间都加一线段.试求出最小值 ,使得在全部所连线段中任意取出 条,并将这 条中的每一条任意地染为红色或蓝色,则在这 条染色线段中必定有同色的三条线段构成一个三角形.

易惊人1年前1

rsqtxl 共回答了18个问题 | 采纳率88.9%

Ramsey定理

1年前查看全部

离散数学的图论中,为什么以v为头的弧的数目叫做入度,以v为尾的叫做出度呢.总是记不住为头的的叫入度

离散数学的图论中,为什么以v为头的弧的数目叫做入度,以v为尾的叫做出度呢.总是记不住为头的的叫入度
总是记不住为头的的叫入度还是出度.

麻叶层层1年前2

xiaocui2 共回答了21个问题 | 采纳率95.2%

对于有向图,以v为头的弧就是指向v的弧,其数目是入度；以v为尾的弧实际上是从v发出的弧,其数目是出度.
有向图中的弧头是该边所指向的一侧端点,可以理解为箭头.

1年前查看全部

图论 根数的表示如题

单身禽哥1年前0

共回答了个问题 | 采纳率

查看全部

图论一般图的定义是什么按照书上说的定义是若允许图中有环,即允许有形如{x,x}的边,使一个顶点自邻接,则这样的图叫做一般

图论一般图的定义是什么
按照书上说的定义是
若允许图中有环,即允许有形如{x,x}的边,使一个顶点自邻接,则这样的图叫做一般图
但是,在顶点的度数的定义中,有一个条件是在一般图G中,与顶点x相关联的边的数目叫做该顶点的度数,到底什么事一般图的定义

wangjingqi1年前2

Iamnew 共回答了17个问题 | 采纳率94.1%

一般图就是图,只是相对于特殊的图[诸如：简单图,二分图等]特别强调一下.
“顶点x相关联的边的数目叫做该顶点的度数”,这个不准确
The degree of a vertex is the number of edges that connect to it,where an edge that connects to the vertex at both ends (a loop) is counted twice.
就是说(x,x)这样的边要统计两次.

1年前查看全部

图论中有没有定义一种每一个点有且仅有两条边的图?

LCY56361年前1

巴哈鱼121 共回答了20个问题 | 采纳率85%

那就是每个点的度数是2的图,是2正则图,通常称为圈.

1年前查看全部

图论中"基于邻居的"是什么意思

hyshen宝仔1年前1

wm1113 共回答了17个问题 | 采纳率76.5%

邻接点
和数据结构中的一样

1年前查看全部

关于图论里人互相认识的问题是《图论与代数结构》里的第一章练习题第6题.证明9个人中若非至少有4个人互相认识,则至少有3个

关于图论里人互相认识的问题
是《图论与代数结构》里的第一章练习题第6题.
证明9个人中若非至少有4个人互相认识,则至少有3个人互相不认识.
如果说4个人互相认识，反映在图上，应该是把连接4个点的道路或者回路还是K4图啊？这个问题没搞清楚……

第十放映室1年前1

zixiao__520 共回答了23个问题 | 采纳率91.3%

这是由一道数学竞赛题改编过来的.
第一种情况：存在三人相互不认识,很显然结论是成立的.
第二种情况：任意三人中至少有两人认识.（这种情况就是原题）
抽象成点,全部连接,若认识边染成红色,否则染成蓝色.
由假设,这个图中没有蓝色三角形.
分两种情况.1,若某个顶点发出的蓝边至少有四条（以四条为例）,那么分析就可知道存在存在红色的完全图K4；
2,若任一顶点发出的蓝线至多三条,那么存在某个顶点A的发出了（至少）六条边,然后在考察这六个顶点,在运用拉姆塞定理（二染色的K6中存在同色三角形）,知道这六个顶点中存在红色的三角形.这三点再加A就是完全认识的人了.
以上就是问题解答的核心部分,细枝末节你就自己添加吧.

1年前查看全部

为什么 在图论这部分中 各种书对路 回路 通路 初等回路等等定义都不相同呢

为什么 在图论这部分中 各种书对路 回路 通路 初等回路等等定义都不相同呢
谁能给一个比较准确的定义啊

六月妹妹1年前1

haoKY 共回答了20个问题 | 采纳率85%

不要纠结于表象,抓住本质就行了.就连自然数的定义,从小学到大学还一直在变呢（不能说后来的定义一定比之前的定义更准确,只是基于的理论体系不同）,每一种定义方式都有其出发点,易于你理解的就是对你更准确的,多看几本经典比较比较,有些定义只是文字描述上不同,而另一些则是整个理论体系有区别,但目的都是为了解释同样的问题.当你意识到不同定义之间的真正差别时,你就不需要大家来回答这个问题了.

1年前查看全部

图论问题无向图G中恰好只有2个度数为奇数的顶点证明:这两个顶点间必定存在一条路

◤创造晴天◢1年前1

adsp 共回答了17个问题 | 采纳率88.2%

若不然,则这两个顶点将分别属于两个简单图,也即G中包含两个简单图,每个简单图都只有一个奇顶点,这显然是不可能的.

1年前查看全部

关于图论中完全匹配的一道题目一道图论题目：设R是A到B的一个关系且|A|=|B|=n,证明：如果在A,B和R相对应的网络

关于图论中完全匹配的一道题目
一道图论题目：设R是A到B的一个关系且|A|=|B|=n,证明：如果在A,B和R相对应的网络中,每一个节点的度数至少是n/2,那么对于A,B和R,存在一个完全匹配.提示是利用哈密尔顿回路回路存在性的一个定理：如果n个顶点的连通图每个顶点的度数至少为n/2,那么该图必定存在一条哈密尔顿回路.

shayangnono1年前1

www20020110 共回答了16个问题 | 采纳率100%

我将所述之图理解为一个二部图,记为G,部集为A和B,关系R则是边集.由于图中存在一条Hamilton回路,记此回路为H,则H为G的生成子图.在H中,因点集A中的点之间没有边相连,且每个点的度数为2 (对于B也一样),故H是一个2正则的二部图.由于“任意 r 正则二部图(r≥1)均有一个完美匹配.”故H含有一个完美匹配,因H是G的生成子图,当然H的完美匹配亦是G的完美匹配,从而完成证明.
注：定理“任意 r 正则二部图(r≥1)均有一个完美匹配.”之证明详见Gary Chartrand等著的《图论导引》第八章“匹配与分解”.
生成子图的定义是：如果图G的一个子图与G有相同的顶点集,那么该子图是图G的一个生成子图.

1年前查看全部

翻译啊 不要复制来的 谢谢图论不仅具有重要的理论研究价值，而且在计算机科学、网络理论、运筹学、物理、化学和生物学等领域都

翻译啊 不要复制来的 谢谢
图论不仅具有重要的理论研究价值，而且在计算机科学、网络理论、运筹学、物理、化学和生物学等领域都具有广泛的应用背景。其中，图的控制理论已成为图论研究中的一个重要的领域。图的控制问题在优化理论、通讯网络设计与分析、计算的复杂性和算法设计等方面得到了广泛的应用。本文主要综述广义Petersen 图的控制数问题。在图的控制理论中, 对给定的一个图或者一类图一个基本的问题是确定其控制数。目前在广义Petersen图P(n,k)控制数的研究方面主要集中在求上下界和对k取特定值时精确值的研究。在研究图的控制数问题中，完全确定了控制数的图类是很少的，但是我们可以确定一些特殊图类的控制数,许多研究工作是在特定条件下来确定一个图或某一类图的控制数。以此为背景，本人对广义Petersen图控制数领域内的主要贡献者研究成果进行归纳总结，并梳理其理论逻辑，力求从另一个侧面去理解广义Petersen图控制数，进而理解它们的实质。具体说，就是先引入广义Petersen图控制数的背景，再引入它们的概念性质内容。本文对文献的综述基本上按照广义Petersen图控制数历史发展进程展开，期望能为人们理解广义Petersen图控制数提供一些有益的视角。其中主要总结归纳评论付学良、齐登记及王浩丽等人的各种理论假说。尽管文献的视角各不相同，但大多数都是从广义Petersen图控制数理论起步的。

起个B名想半天啊1年前1

Agnes85 共回答了18个问题 | 采纳率88.9%

Graph theory not only has important theoretical research value, but also in computer science, network theory, operations research, physics, chemistry and biology, etc are a wide range of applications ...

1年前查看全部

求离散数学完整答案（左孝凌版)至少要到第七章图论，帮忙发到邮箱wthqqw@sina.com

夏天的小溪1年前1

jyj332 共回答了24个问题 | 采纳率91.7%

已发送，请查收。
是PDF格式的。

1年前查看全部

什么是图论里生成树的生成子图请通俗一点

guagua04011年前1

罪恶天神 共回答了16个问题 | 采纳率75%

我就给你讲一下生成树吧~
生成树是指：如果G是一个图,这个图的生成子图T是树,那么可以说T为G的生成树.一个图有生成树当且仅当这个图连通.

1年前查看全部

图论中,duplicate edges 与 parallel edges 的区别是什么?

caobin20311年前1

pittchan 共回答了9个问题 | 采纳率100%

duplicate edges 是重复边（不一定平行）
parallel edges 是平行边

1年前查看全部

什么是图论中的连通分支请通俗一点

jshmjxx1年前1

江南快刀 共回答了20个问题 | 采纳率95%

一整块联通的点和边

1年前查看全部

图论中,什么是平凡树,什么是非平凡树呀?希望能通俗详细一点..

publicin1年前1

hbcdxlgjj 共回答了22个问题 | 采纳率95.5%

非平凡树至少有两片叶子

1年前查看全部

英语翻译摘要：二部图作为图论中的一个特殊模型,已广泛应用于诸如排课系统等实际应用中.本文主要研究汽车零配件供应商与汽车4

英语翻译
摘要：二部图作为图论中的一个特殊模型,已广泛应用于诸如排课系统等实际应用中.本文主要研究汽车零配件供应商与汽车4s店的关系,而在***汽车零配件供应商与汽车4s店的数目都非常巨大,关系也错综复杂,想要研究他们之间的关系是非常困难的.本文通过构造其二部图模型,分离出该二部图模型中的一个匹配来单独研究,并通过多个匹配的对比分析,很容易得出他们的关系.综合考虑多个汽车配件供应商与汽车4s店的关系,通过资源的重新整合,不仅可以降低汽车零配件的成本,提高汽车4s店的利润,也可以使普通车主得到更多实惠,从而实现双赢甚至多赢.
关键词：二部图；汽车配件供应商；汽车4s店；关系
忘了还有题目也要翻译,二部图在汽车配件供应商与4s店关系研究中的应用,

牛狼之鱼1年前1

skr0a 共回答了20个问题 | 采纳率85%

the application of Bipartite Graphs in the study of relations between automobile parts suppliers and automobile 4S shops
Summary:The Bipartite Graphs, as a special model in graph theory, has been widely used in practical applications such as Course Scheduling System. This paper studies the relations between automobile parts suppliers and auto 4S shops, it is a very difficult work to study because the number of national automobile parts suppliers and automobile 4S shops is very large and thier relations are very complex. In this paper,a bipartite graph model is established, then isolate some matching relations in the bipartite graph model for study, make comparison between several matching relations,to easily achieve their relations.
Considering the relationship among a number of automobile parts suppliers and auto 4S shops in a whole and making re-integration of resources, can not only reduce the cost of automobile parts, increase the profits of automobile 4S shops, but also make ordinary car owners get more benefits, to achieve a win-win relation.
Keywords:Bipartite Graphs ; automobile parts supplier; auto 4S shops; relation

1年前查看全部

如何利用数学上的图论推算出N+1个C原子的烷烃理论上有的异构体数

如何利用数学上的图论推算出N+1个C原子的烷烃理论上有的异构体数
已知N
这是我书上写的,胡宏纹主编的有机化学(上)2006年5月第三版 17页最上面 高教出版社的书

dsaadsa1年前2

先是贾琏 共回答了15个问题 | 采纳率80%

因为这个没有什么规律可言的东西,因为他涉及到的东西很多,并不是用简单数学可以计算的,如果你知道n或者n+1的具体数值的话,那么你就可以知道他有多少同分异构体了（n不太大,或者书上有记载）,但是没什么规律,这个化学家和数学家都研究过很久了.
那他给出答案了吗?我用的书和你的不一样

1年前查看全部

什么是图论生成树里的避圈法和破圈法

什么是图论生成树里的避圈法和破圈法
请通俗一点

tjarzt1年前1

骑猪天上飞 共回答了18个问题 | 采纳率83.3%

设图为G=（V,E）
避圈法: 以V上的空图为初始图进行加边操作,依次检查E的边,如果该边加到当前图上不产生圈则将该边加上,否则检查下一条未检查边直至所有边都被检查;
破圈法：以G为初始图进行去边操作,依次检查E的边,如果该边被当前图的某个圈包含则将该边去掉,否则检查下一条未检查边直至所有边都被检查.

1年前查看全部

图论 树有完备匹配的充要条件,不要给我说图的完备匹配的定理

不睡觉和你聊爱情1年前1

zhouxuej 共回答了17个问题 | 采纳率88.2%

无简洁的充要条件,一般还是用O(G-V0)

1年前查看全部

离散数学中,图论部分,同构的概念怎么理解,比较形象的说出来

78329531年前2

帅哥哥酷 共回答了19个问题 | 采纳率94.7%

两个图同构,实际上就是一个图,只是标号不同或画法不同而已.

1年前查看全部