梁學(xué)霸的活動(dòng)志衍，打卡第一天交作業(yè)：
今天讀了《1089》前三章聊替，重點(diǎn)重新梳理和學(xué)習(xí)了konisberg bridge problem（這個(gè)問題也稱為一筆畫問題）。
（1）這個(gè)問題是17世紀(jì)瑞士數(shù)學(xué)家Leonhard Euler使用reductio ad absurdum 來證明的春叫。
（2）基本概念理清：
1.度數(shù)：從一個(gè)點(diǎn)出發(fā)的線的條數(shù)；
2.偶點(diǎn)：度數(shù)為偶數(shù)的點(diǎn)价匠；
3.奇點(diǎn)：度數(shù)為奇數(shù)的點(diǎn)呛每；
4.歐拉半回路：經(jīng)過圖中每條線一次且僅一次晨横，不要求一定回到出發(fā)點(diǎn)的路；
5.歐拉回路：從圖中任意點(diǎn)出發(fā)颓遏，經(jīng)過圖中每條線一次且僅一次，再回到原來出發(fā)點(diǎn)的路線叁幢。
6.歐拉回路是歐拉半回路的特例曼玩。
（3）歐拉定理：
1.如果奇點(diǎn)的個(gè)數(shù)為0，則存在歐拉回路黍判。而且可以從任意一點(diǎn)出發(fā)顷帖。（起點(diǎn)即為終點(diǎn)）
2.如果奇點(diǎn)的個(gè)數(shù)為2，則存在歐拉半回路（不存在歐拉回路）榴嗅，這個(gè)半回路一定是從一個(gè)奇點(diǎn)出發(fā)陶舞，最后到達(dá)另一個(gè)奇點(diǎn)。
3.如果奇點(diǎn)的個(gè)數(shù)大于2唠粥，則不存在歐拉回路和半回路晤愧。也就是無法完成一筆畫。
補(bǔ)充：由偶數(shù)個(gè)奇點(diǎn)除以二便可算出此圖需要幾筆畫成养涮。
（4）證明過程：假設(shè)有可能走過每一座橋，而且每座橋只經(jīng)過一次懈凹。即從ABCD其中的一個(gè)區(qū)域出發(fā)介评，最后回到它們當(dāng)中的一個(gè)（有可能兩者都是同一個(gè)區(qū)域），而途中要通過每一座橋正好一次们陆。
? ? ? 緊接著就可推斷出坪仇，至少有兩個(gè)區(qū)域即非這趟步行的起點(diǎn)垃你，也不是終點(diǎn)惜颇。針對一個(gè)非起點(diǎn)也非終點(diǎn)的區(qū)域，我們到達(dá)那里幾次凌摄，就會(huì)從那里離開幾次锨亏，而且因?yàn)槊恳蛔鶚蛑荒茏哌^一次，所以器予，必定要有偶數(shù)座橋連接該區(qū)域劣摇。
? ? ? 但是末融，在這個(gè)圖示中，沒有一個(gè)區(qū)域有這樣的特性勾习，島A由5座橋連接懈玻，島BCD都是由3座橋連接。所以艺栈，證明無法走過這7座橋中的每一座湿右，一次且僅一次。
（4）悟：看起來很簡單的問題吭狡，實(shí)際上可能更復(fù)雜丈莺。但是缔俄，當(dāng)感覺很復(fù)雜困難的時(shí)候，可能有簡單有效的方法立馬就解決了牵现。
