1.6 图生成器
随机边方法
实现简单，但是可能生成自环和平行边。
随机图
考虑所有可能的边，并将每条边以一个固定的概率p加入到图中。
k-邻图
随机选取第一个定点v，再从某些顶点（这些顶点的索引与v的索引相差一个固定常数k）中选取第二个顶点。
欧几里得邻图
在平面上随机生成v个点，然后生成边（边所连接的是相距距离在d之内的两个点）。
事物图
如电话公司。
123 152
124 123
125 152
126 895
其中顶点定义为各个电话号码，而边定义为一个i-j对，其属性为i在某段固定时间内拨打过j的电话。
功能调用图
函数作为顶点，而当函数X调用函数Y时即有一条连接X和Y的边。
用静态函数调用来研究程序结构，而用动态函数来研究程序行为。
分离度图
顶点对应为子集的并集中的各个元素，如果两个顶点同时出现在某个子集中，则存在一条连接这两个顶点的边。
区间图
实线上v个区间的集合。顶点对应为各个区间，如果相应区间相交，则在相应顶点间存在边。
de Bruijn图
v是2的乘幂。顶点对应为小于v的各个非负整数，从顶点i到顶点2i和(2i+1)mod lgV间存在边。
在一个定长移位寄存器中，对于研究相应于一系列操作可能出现的值序列来说，这些图很有用。
1.7简单路径、欧拉路径和哈密顿路径
简单路径
深度优先。即依附于v的每条边v-t，是否存在从t到w的一条简单路径，而且不经过v。
属性1.2 在一个图中，可以在线性时间内找到一条连接两个给定顶点的路径。
代码略。
哈密顿路
给定两个顶点，是否有一条将其连接的简单路径，而且该路径访问了图中的每个顶点一次且仅访问一次？
属性1.3 哈密顿周游路径的递归搜索可能需要花费指数时间。
NP难问题，可以利用自顶向下的动态编程方法得到显著改进。
代码略。
欧拉路径
是否存在一条路径连接了两个给定顶点，同时用到了图中的每一条边一次且仅用到一次呢？
如果是从自身回到自身，则称之为“欧拉周游路径”。
哥尼茨堡桥问题。
属性1.4 一个图有一条欧拉周游路径，条件是当且仅当它是连通的，而且所有定点都有偶数度数。
推论 一个图有一条欧拉路径，条件是当且仅当它是连通的，而且只有两个顶点有奇数度数。
1.欧拉路径的存在性
|
template <class Graph> class ePATH
{
Graph G;
int v,w;
bool found;
STACK <int> S;
int tour(int v);
public:
ePATH(const Graph &G,int v,int w) : //欧拉路径存在性
G(G),v(v),w(w)
{
DEGREE<Graph> deg(G);
int t = deg[v] +deg[w];
if((t%2)!=0)
{
found = false;
return;
}
for(t=0;t<G.V();t++)
if ((t!=v) && (t!=w))
if((deg[t]%2)!=0)
{
found=false;
return;
}
found = true;
}
bool exists() const
{
return found;
}
void show();
}
|
2.线性时间的欧拉路径
|
template <class Graph>
int ePATH<Graph>::tour(int v)
{
while(true)
{
typename Graph::adjIterator A(G,V);
int w=A.beg();
if(A.end())
break;
S.push(v);
G.remove(Edge(v,w));
v=w;
}
return v;
}
template <class Graph>
int ePATH<Graph>::show()
{
if(!found)
return;
while(tour(v)==v && !S.empty())
{
v=S.pop();
cout<<"-"<<v;
}
cout<<ednl;
}
|
属性1.5 若一个图中存在一条欧拉路径，则可在线性时间内找到它。
其实，我们通常使用深度优先搜索来研究图。
阅读(635) | 评论(0) | 转发(0) |
