88
G. Palma/Electronic Notes in Theoretical Computer Science 281
（
2011
）
85
以及它的一些特性第3节介绍了为求解PRPP而开发的算法实验结果和讨论在第4节
中完成。第5节介绍了工作的结论
第二章
农村有奖邮递员问题
在本节中，我正式定义了PRPP，并提出了一些在这项工作中使用的符号和定义
定义2.1设G（V
，
E）是一个无向图，具有一个可分辨的d，称为deposit，在R +中
的边集E上有两个函数，利润函数b 和成本函数c。问题的目标是找到一个循环C
，
使
e
∈
E
（
C
）
（
b
e
−
t
e
c
e
）（
1
）
其中C是G中通过d的圈，d不一定是简单的，
e
是边e在
C
中遍历的次数，E（
C
）是循环
C
的边集。
使用以下符号和其他定义。
V
（
H
）
：
子图
H
的顶点集。 如果
H
=
G
，则
V
（
G
）
=
V
。
E
（
H
）
：
子图
H
的边顶点。如果
H
=
G
，则
E
（
G
）
=
E
。
γ（S）：设S是一个集合，使得S ∈S∈V 我们记为γ（S）=
{
e
∈E|e =
{u
，
v}
，
u
，
v
∈
S}
是两个顶点都在
S
中的边集。
δ（S）：设
S
是一个集合，使得
S ∈
S
∈
V 我们记δ（S）
=
{
e
∈
E
|
e
=
{
u
，
v
}
，
u
∈
S
，
v
∈
V
\
S
}
=
δ
（
V
\
S
）
S
和
V
\
S
之间的割中的边。
对于单例集，我不使用方括号。 例如，以下表达式
是有效的
δ
（
v
）
<$
δ
（
{
v
}
）和
γ
（
v
）
<$
γ
（
{
v
}
）。
在图G的边e上定义下列函数：
•
e
=b
e
−c
e
。
当你第
一
次穿越一条边时，你得到的利润就是
•
e
=
b
e
− 2
c
e
。 当一条边被遍历两次时，你得到的利润就是利润。
边集分为三个集
P
=
{
e
∈
E
|
< R
=
{
e
∈
E
|
Q
=
{
e
∈
E
\
R
|
e
≥
0
}
定义2.2[偶图]偶图是所有顶点都是偶度的图。
我们用（G
，
d
，
b
，
c）表示PRPP实例，其中G是与问题相关联的图，d是存款顶
点，b是利润函数，c是成本函数。
G
R
：
G
R
（
V
（
R
）
d
，
R
）
is
是由边集
R
和存放
d
得到的子图。其中
V
（
R
）是与
R
型
边关联的顶点集。
C
k
：是图G R的连通分支，其中k∈ {0
，
...
，
n}。我们假设d∈C
0
。
剩余15页未读，继续阅读
cpongm
- 粉丝: 5
- 资源: 2万+
我的内容管理
展开
最新资源
- Vue实现iOS原生Picker组件：详细解析与实现思路
- Arduino蓝牙小车：参数调试与功能控制
- 百度Java面试精华：200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南：CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略：44步详解流程
- RecyclerView全面解析：替代ListView的新选择
- Android开发：自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发：BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0：Android事件总线详解与实战应用
- Android FileUtil：全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
