2026-03-11T22:46:44Z https://u-ryukyu.repo.nii.ac.jp/oai

oai:u-ryukyu.repo.nii.ac.jp:02006896 2022-10-31T03:11:08Z 1642837622505:1642837933579:1642837935335 1642838403551:1642838406845

Theorems on number of "trees" with a given number of "knots" or "branches" and on "spanning graphs" 与られた数の｢節｣や｢枝｣をもった｢木｣の数および｢包括図｣に関する諸定理 Inami, Tadao 伊波, 直朗 open access この論文では、n個の｢枝｣またはｍ個の｢節｣をもったトポロギー的に異なる｢木｣の数、α,β,γ,･･･とレッテルをはってあるn個の｢節｣をもったトポロギー的に異なる｢木｣の数、n個の｢枝端｣をもったトポロギー的に異なる｢木｣の数、多演算子とレッテルばり木の数との関係、n個の｢枝端｣をもったトポロギー的に異なる｢分岐木｣の数、｢包括図｣、｢最大図｣、｢最小図｣、｢森｣に関する諸定理を提起、証明した。n個の｢杖｣をもったトポロギー的に異なる｢木｣の数A＿nおよびn個の｢節｣をもったトポロギー的に異なる｢木｣の数C’＿nは、それぞれ次の｢生成函数｣a(x),C(x)によってあらわすことができる。　a(x)-A＿0+A＿1x+A_2x^2+･･･-=(1-x)^<-1>(1-x^2)^<-A1>(1-x^3)^<-A2>･･･　C(x)=C_1x+C_2x^2+C_3x^3+･･･=x(1-x)^<-C_1>(1-x^2)^<-C_2>(1-x^3)^<-C_3>･･･　すなわち、n=1,2,3,･･･,12に対するA_nの値は,1,2,4,9,20,48,115,286,719,1842,4766,12486で、C_nの値は,1,1,2,4,9,20,48,115,286,719,1842,4766である。n個の｢枝端｣をもったトポロギー的に異なる｢木｣の数B_nは次の｢生成函数｣b(x)によってあらわすことができる。　b(x)=(1-x)^<-1>(1-x^2)^<-B_2>(1-x^3)^<-B_8>=1+x+2B_2x^2+2B_3x^3+･･･　すなわち、n=1,2,3,･･･,9に対するB_nの値はそれぞれ0,1,2,5,12,33,90である。n個の｢枝端｣をもったトポロギー的に異なる｢分岐木｣の数D_nは次の｢生成函数｣d(x)によってあらわすことができる。　d(x)=D_1+D_2x+D_3x^2+･･･=(1-√<1-4x>)/(2x)　すなわち、n=1,2,3,･･･,7に対するD_nの値は1,1,2,5,14,42,132である。｢図｣の全頂点を含む｢部分図｣はその図を｢包括する｣という。同一種類のそれより大きな｢図｣に含まれない｢図｣は｢最大｣であるという。同一種類のそれより小さな｢図｣を含まない｢図｣は｢最小｣であるという。ループを含まない｢図｣を｢森｣という。上の定義にしたがえば、次の定理が成立する。定理1　 もしGがn個の頂点をもつ連結した｢図｣であり、TがGの部分図であれば、次の条件は等価である。(a) TはGの包括木である。(b) TはGの最大森である。(C) TはGの最小連結包括図である。(d) Tはn-1個の枝をもった森である。(e) Tはn-1個の枝をもった連結包拓図である。定理2　 Gの彼が全部ちがった良さであれば耐定理の条件を満足するTは一意的にさだまる。このときTはGの任意の最短包拍木である。Gの最短包括木を作るに当っての実際的な方法も示してある｡ 紀要論文 琉球大学農家政工学部 1961-06 eng departmental bulletin paper NA http://hdl.handle.net/20.500.12000/23292 http://hdl.handle.net/20.500.12000/23292 https://u-ryukyu.repo.nii.ac.jp/records/2006896 0485-7828 AN00250570 琉球大学農家政工学部学術報告 The science bulletin of the Division of Agriculture, Home Economics & Engineering, University of the Ryukyus 8 349 354 https://u-ryukyu.repo.nii.ac.jp/record/2006896/files/No8p349.pdf