歐拉韁繩理論

F=fe^kα

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

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

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

釋義：1. 系馬的繩索。

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

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

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

【示例】：

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

柳青 《銅墻鐵壁》第一章：“正說著，吳忠趕上來了，從首長手里接去騾子的韁繩，就拉著下山?！?

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

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

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

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

一個有向圖存在歐拉回路，所有頂點的入度等于出度且該圖是連通圖。

混合圖存在歐拉回路條件

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

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

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

無向圖歐拉回路解法

求歐拉回路的一種解法

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

C語言代碼，不全，請不要直接粘貼。

intnum=0;//標(biāo)記輸出隊列
intmatch[MAX];//標(biāo)志節(jié)點的度，無向圖，不區(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代碼:

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

programeuler;
constmaxn=10000;{頂點數(shù)上限}
maxm=100000;{邊數(shù)上限}
typetnode=^tr;
tr=record
f,t:longint;{邊的起始點和終止點}
al:boolean;{訪問標(biāo)記}
rev,next:tnode;{反向邊和鄰接表中的下一條邊}
end;
varn,m,bl:longint;{頂點數(shù)，邊數(shù)，基圖的極大連通子圖個數(shù)}
tot:longint;
g:array[1..maxn]oftnode;
d:array[1..maxn]oflongint;{頂點的度}
fa,rank:array[1..maxn]oflongint;{并查集中元素父結(jié)點和啟發(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);{合并后，基圖的極大連通子圖個數(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ā)點尋找歐拉回路}
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;{主過程}
vari:longint;
begin
o:=false;
fori:=1tondo
ifd[i]=0thendec(bl);{排除孤立點的影響}
ifbl<>1thenexit;{原圖不連通，無解}
fori:=1tondo
ifodd(d[i])thenexit;{存在奇點，無解}
o:=true;
fori:=1tondo
ifd[i]<>0thenbreak;
tot:=m;
search(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中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。

求歐拉回路的思路：

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

具體步驟：

1。如果此時與該點無相連的點，那么就加入路徑中

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

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

4。這個其實是個遞歸過程。

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