歐拉韁繩理論起源

18世紀(jì)，著名的數(shù)學(xué)家歐拉曾經(jīng)研究過(guò)摩擦力跟繩索繞在柱子上的圈數(shù)之間的關(guān)系。得出了著名的“歐拉韁繩理論”

F=fe^kα

在這個(gè)公式里，f代表我們所用的力，F(xiàn)代表我們所要對(duì)抗的力。E代表數(shù)2.718……（自然對(duì)數(shù)的底），k代表繩索和樁子之間的摩擦系數(shù)。α代表饒轉(zhuǎn)角，也就是繩索饒成的弧的長(zhǎng)度跟弧的半徑的比。

力學(xué)告訴我們，繞在樁上的繩子在滑動(dòng)的時(shí)候，摩擦力可以達(dá)到非常大的程度。繩索繞的圈數(shù)越多，摩擦力也就越大，摩擦力增長(zhǎng)的規(guī)律是：如果圈數(shù)按算術(shù)級(jí)數(shù)增多，摩擦力就按幾何級(jí)數(shù)增長(zhǎng)。所以就算是一個(gè)小孩子，只要能把繩索在不動(dòng)轆轤上繞幾圈，然后抓住繩頭，他的力量就能平衡一個(gè)極大的重物。

釋義：1. 系馬的繩索。

【出處】：《水滸傳》第五回：“原來(lái)心慌不曾解得韁繩，連忙扯斷了，騎著摌馬飛走?！?

釋義：2. 韁繩：牽牲口的繩子。

【出處】：《西游記》第五三回：“ 孫大圣前邊引路，豬八戒攏了韁繩?！?

【示例】：

《二十年目睹之怪現(xiàn)狀》第六九回：“我心中無(wú)限焦燥，只得拉著韁繩步行一程，再騎一程?！?

柳青 《銅墻鐵壁》第一章：“正說(shuō)著，吳忠趕上來(lái)了，從首長(zhǎng)手里接去騾子的韁繩，就拉著下山。”

以下判斷基于此圖的基圖連通。

無(wú)向圖存在歐拉回路的充要條件

一個(gè)無(wú)向圖存在歐拉回路，當(dāng)且僅當(dāng)該圖所有頂點(diǎn)度數(shù)都為偶數(shù),且該圖是連通圖。

有向圖存在歐拉回路的充要條件

一個(gè)有向圖存在歐拉回路，所有頂點(diǎn)的入度等于出度且該圖是連通圖。

混合圖存在歐拉回路條件

要判斷一個(gè)混合圖G（V,E）（既有有向邊又有無(wú)向邊）是歐拉圖，方法如下：

假設(shè)有一張圖有向圖G'，在不論方向的情況下它與G同構(gòu)。并且G'包含了G的所有有向邊。那么如果存在一個(gè)圖G'使得G'存在歐拉回路，那么G就存在歐拉回路。

其思路就將混合圖轉(zhuǎn)換成有向圖判斷。實(shí)現(xiàn)的時(shí)候，我們使用網(wǎng)絡(luò)流的模型?，F(xiàn)任意構(gòu)造一個(gè)G'。用Ii表示第i個(gè)點(diǎn)的入度，Oi表示第i個(gè)點(diǎn)的出度。如果存在一個(gè)點(diǎn)k，|Ok-Ik|mod 2=1，那么G不存在歐拉回路。接下來(lái)則對(duì)于所有Ii>Oi的點(diǎn)從源點(diǎn)連到i一條容量為(Ii-Oi)/2的邊，對(duì)于所有Ii 歐拉回路解法

無(wú)向圖歐拉回路解法

求歐拉回路的一種解法

下面是無(wú)向圖的歐拉回路輸出代碼：注意輸出的前提是已經(jīng)判斷圖確實(shí)是歐拉回路。

C語(yǔ)言代碼，不全，請(qǐng)不要直接粘貼。

intnum=0;//標(biāo)記輸出隊(duì)列
intmatch[MAX];//標(biāo)志節(jié)點(diǎn)的度，無(wú)向圖，不區(qū)分入度和出度
voidsolve(intx)
{
if(match[x]==0)
Record[num  ]=x;
else
{
for(intk=0;k<=500;k  )
{
if(Array[x][k]!=0)
{
Array[x][k]--;
Array[k][x]--;
match[x]--;
match[k]--;
solve(k);
}
}
Record[num  ]=x;
}
}

pascal代碼:

求無(wú)向圖的歐拉回路（遞歸實(shí)現(xiàn)）

programeuler;
constmaxn=10000;{頂點(diǎn)數(shù)上限}
maxm=100000;{邊數(shù)上限}
typetnode=^tr;
tr=record
f,t:longint;{邊的起始點(diǎn)和終止點(diǎn)}
al:boolean;{訪問(wèn)標(biāo)記}
rev,next:tnode;{反向邊和鄰接表中的下一條邊}
end;
varn,m,bl:longint;{頂點(diǎn)數(shù)，邊數(shù)，基圖的極大連通子圖個(gè)數(shù)}
tot:longint;
g:array[1..maxn]oftnode;
d:array[1..maxn]oflongint;{頂點(diǎn)的度}
fa,rank:array[1..maxn]oflongint;{并查集中元素父結(jié)點(diǎn)和啟發(fā)函數(shù)值}
list:array[1..maxm]oftnode;{最終找到的歐拉回路}
o:boolean;{原圖中是否存在歐拉回路}
procedurebuild(ta,tb:longint);{在鄰接表中建立邊(ta,tb)}
vart1,t2:tnode;
begin
t1:=new(tnode);
t2:=new(tnode);
t1^.f:=ta;
t1^.t:=tb;
t1^.al:=false;
t1^.rev:=t2;
t1^.next:=g[ta];
g[ta]:=t1;
t2^.f:=tb;
t2^.t:=ta;
t2^.al:=false;
t2^.rev:=t1;
t2^.next:=g[tb];
g[tb]:=t2;
end;
proceduremerge(a,b:longint);{在并查集中將a,b兩元素合并}
varoa,ob:longint;
begin
oa:=a;
whilefa[a]<>adoa:=fa[a];
fa[oa]:=a;
ob:=b;
whilefa[b]<>bdob:=fa[b];
fa[ob]:=b;
ifa<>bthenbegin
dec(bl);{合并后，基圖的極大連通子圖個(gè)數(shù)減少1}
ifrank[a]=rank[b]theninc(rank[a]);
ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;
end;
end;
procedureinit;{初始化}
vari,ta,tb:longint;
begin
fillchar(fa,sizeof(fa),0);
fillchar(rank,sizeof(rank),0);
fillchar(d,sizeof(d),0);
readln(n,m);
fori:=1tondofa[i]:=i;
bl:=n;
fori:=1tomdobegin
readln(ta,tb);
build(ta,tb);
inc(d[tb]);
inc(d[ta]);
merge(ta,tb);
end;
end;
proceduresearch(i:longint);{以i為出發(fā)點(diǎn)尋找歐拉回路}
varte:tnode;
begin
te:=g[i];
whilete<>nildobegin
ifnotte^.althenbegin
te^.al:=true;
te^.rev^.al:=true;
search(te^.t);
list[tot]:=te;
dec(tot);
end;
te:=te^.next;
end;
end;
proceduremain;{主過(guò)程}
vari:longint;
begin
o:=false;
fori:=1tondo
ifd[i]=0thendec(bl);{排除孤立點(diǎn)的影響}
ifbl<>1thenexit;{原圖不連通，無(wú)解}
fori:=1tondo
ifodd(d[i])thenexit;{存在奇點(diǎn)，無(wú)解}
o:=true;
fori:=1tondo
ifd[i]<>0thenbreak;
tot:=m;
search(i);{從一個(gè)非孤立點(diǎn)開(kāi)始尋找歐拉回路}
end;
procedureprint;{輸出結(jié)果}
vari:longint;
begin
ifnotothenwriteln('Nosolution.')elsebegin
writeln(list[1]^.f);
fori:=1tomdowriteln(list[i]^.t);
end;
end;
begin
init;
main;
print;
end.

注意record中的點(diǎn)的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過(guò)來(lái)輸出。

求歐拉回路的思路：

循環(huán)的找到出發(fā)點(diǎn)。從某個(gè)節(jié)點(diǎn)開(kāi)始，然后查出一個(gè)從這個(gè)出發(fā)回到這個(gè)點(diǎn)的環(huán)路徑。這種方法不保證每個(gè)邊都被遍歷。如果有某個(gè)點(diǎn)的邊沒(méi)有被遍歷就讓這個(gè)點(diǎn)為起點(diǎn)，這條邊為起始邊，把它和當(dāng)前的環(huán)銜接上。這樣直至所有的邊都被遍歷。這樣，整個(gè)圖就被連接到一起了。

具體步驟：

1。如果此時(shí)與該點(diǎn)無(wú)相連的點(diǎn)，那么就加入路徑中

2。如果該點(diǎn)有相連的點(diǎn)，那么就加入隊(duì)列之中，遍歷這些點(diǎn)，直到?jīng)]有相連的點(diǎn)。

3。處理當(dāng)前的點(diǎn)，刪除走過(guò)的這條邊，并在其相鄰的點(diǎn)上進(jìn)行同樣的操作，并把刪除的點(diǎn)加入到路徑中去。

4。這個(gè)其實(shí)是個(gè)遞歸過(guò)程。

歐拉─伯努利梁方程內(nèi)容描述了梁的位移與載重的關(guān)系：