[問題] 一筆劃成的圖形

[britneycafe (嘟嘟嘟)]

請問一下，給你各種圖形要怎麼判斷圖形可不可以一筆劃成呀？？

是判斷一個點連幾條線去分嗎？？一。一
         ‧
         │
         │
   ‧──‧──‧

 ......其他圖形我不會畫，畫了一個最簡單的　0rz



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.132.202.194

> -------------------------------------------------------------------------- <

作者: yonex (諸法皆空) 看板: tutor
標題: Re: [問題] 一筆劃成的圖形
時間: Thu Mar 23 12:18:36 2006

※ 引述《britneycafe (嘟嘟嘟)》之銘言：
: 請問一下，給你各種圖形要怎麼判斷圖形可不可以一筆劃成呀？？
: 是判斷一個點連幾條線去分嗎？？一。一
:          ‧
:          │
:          │
:    ‧──‧──‧
:  ......其他圖形我不會畫，畫了一個最簡單的　0rz



      1.  圖要連通

      （分裂的圖沒辦法一筆畫，筆一定要拿起來）


      2. 除了起點與終點（起終點可任選），
         每個『節點』所延伸出來的路徑，都要是偶數

      （想一想....要求逛完全部的大街小巷，路又不能重複走，
        除了起點與終點，其餘所以節點都要一進一出。不能進了出不去呀！）


     1.2.都要滿足，才可以一筆畫，在數學上這叫 Euler trial

     你那張圖，第二條件不滿足



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.67.107.200
※ 編輯: yonex           來自: 203.67.107.200       (03/23 12:19)

> -------------------------------------------------------------------------- <

作者: yonex (諸法皆空) 看板: tutor
標題: Re: [問題] 一筆劃成的圖形
時間: Thu Mar 23 21:38:49 2006

※ 引述《yonex (諸法皆空)》之銘言：
: ※ 引述《britneycafe (嘟嘟嘟)》之銘言：
: : 請問一下，給你各種圖形要怎麼判斷圖形可不可以一筆劃成呀？？
: : 是判斷一個點連幾條線去分嗎？？一。一
: :          ‧
: :          │
: :          │
: :    ‧──‧──‧
: :  ......其他圖形我不會畫，畫了一個最簡單的　0rz
:       1.  圖要連通
:       （分裂的圖沒辦法一筆畫，筆一定要拿起來）
:       2. 除了起點與終點（起終點可任選），
:          每個『節點』所延伸出來的路徑，都要是偶數
:       （想一想....要求逛完全部的大街小巷，路又不能重複走，
:         除了起點與終點，其餘所以節點都要一進一出。不能進了出不去呀！）
:      1.2.都要滿足，才可以一筆畫，在數學上這叫 Euler trial
:      你那張圖，第二條件不滿足

  多講幾句贅言好了...

  封閉的圖，一筆畫肯定起終點重合，那麼每個節點延伸的路徑都必須是偶數

  不封閉的圖，一筆畫肯定起終點不能重合，那麼僅能有兩個節點延伸的路徑為奇數
  其他節點都必須為偶數

  當然，圖都不可以分裂。

  條件1與2之聯集 為 一筆畫 之充分必要條件

  封閉的一筆畫稱為Euler circuit （歐拉迴圈？）
  不封閉的一筆畫稱為Euler trial （不知道怎麼翻譯）

  你可以解柯尼斯堡（Konigsberg）七橋問題了....


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 203.67.107.200

> -------------------------------------------------------------------------- <

作者: autopying (你有想過自己要的到底是ꐩ 看板: tutor
標題: Re: [問題] 一筆劃成的圖形
時間: Fri Mar 24 13:56:35 2006

※ 引述《yonex (諸法皆空)》之銘言：
: ※ 引述《yonex (諸法皆空)》之銘言：
: :       1.  圖要連通
: :       （分裂的圖沒辦法一筆畫，筆一定要拿起來）
: :       2. 除了起點與終點（起終點可任選），
: :          每個『節點』所延伸出來的路徑，都要是偶數
: :       （想一想....要求逛完全部的大街小巷，路又不能重複走，
: :         除了起點與終點，其餘所以節點都要一進一出。不能進了出不去呀！）
: :      1.2.都要滿足，才可以一筆畫，在數學上這叫 Euler trial
: :      你那張圖，第二條件不滿足
:   多講幾句贅言好了...
:   封閉的圖，一筆畫肯定起終點重合，那麼每個節點延伸的路徑都必須是偶數
:   不封閉的圖，一筆畫肯定起終點不能重合，那麼僅能有兩個節點延伸的路徑為奇數
:   其他節點都必須為偶數
:   當然，圖都不可以分裂。
:   條件1與2之聯集 為 一筆畫 之充分必要條件
:   封閉的一筆畫稱為Euler circuit （歐拉迴圈？）
:   不封閉的一筆畫稱為Euler trial （不知道怎麼翻譯）
:   你可以解柯尼斯堡（Konigsberg）七橋問題了....


1. 圖不可分裂==>這是第一個基本要求,例如品這個字的圖形為分裂圖
2. 節點延伸路徑這部分我有個些微不一樣的認知
   我的習慣是圖中所有的節點都先算出他的路徑數後
   只要節點的路徑數沒有奇數或兩個奇數時則此圖可一筆劃
                   ^^^^^^^^^^^^^^^^^^


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.29.179.118
推 yonex:你要不要先仔細看看我的文章  我寫兩篇喔
→ yonex:每個節點所延伸的路徑  就是deg(v_i) 只是我不想講專有名詞
→ yonex:所以胡亂發明這個名詞  你可以查一查那個中文叫什麼...
推 britneycafe:都很謝謝你們的回答。我懂了～^++++^
※ 編輯: autopying       來自: 203.204.136.94       (03/25 21:35)
→ autopying:我用認知不太一樣這句話不好~~對不起,其實你的意思我知
→ autopying:道,當然很正確,我只是想分享一下我比較白痴的解題思考
→ autopying:而已,如有錯誤,歡迎指教^^