• 検索結果がありません。

〈論文〉標識グラフの数え上げ問題についての一考察

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "〈論文〉標識グラフの数え上げ問題についての一考察"

Copied!
5
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 5 ページ )

全文

(1)標 識 グ ラ フの数 え上 げ 問題 につ い て の一 考 察. 標 識 グ ラ フ の 数 え上 げ 問 題 に つ い て の 一 考 察. 田澤. An Enumeration. 新成. of Labeled. Shinsei. Graphs. TAZAWA. This paper considers figures with vertices and edges as components, there are, with the aim of classifying. and discusses how many figures. them. These figures are called graphs. Graphs have been classified. for many years on the basis of their various attributes.. In this context,. counting. In graph theory, this problem has been called. the number of graphs with the given properties.. the enumeration. problem. This paper considers an enumeration. a simple, beautiful. equation on an enumeration. we encounter. the problem. of. of labeled graphs. Riddell (1951) derived. of labeled graphs. This paper shows a broad application. of this equation.. 1序. にす る。 空 で な い 有 限 集 合 レ を 取 り、yの 元 の 対 の. 点 と辺 を構 成 要素 に す る 図形 を取 り扱 い 、考 え られ る 図 形 が何 通 りあ る か を 考 察 す る 。 これ. 集 合(2)一. 塒}⊂ylゼ. ≠ ブ}を 定 め ・N-{q. l・a・ ・」 に 対 し・yと. 写 像 Φ ・(2)-Nと. の. は 、 図 形 の 分類 に 通 ず る 。 図形 は こ こで は グ ラ フ と呼 ば れ る 。 グ ラ フが もっ て い る種 々 の属 性 に基 づ き、 グ ラ フ を分 類 す る こ とが 長年 行 わ れ て きて い る 。 この 中 で 、与 え られ た性 質 を もつ グ ラ フは い くつ あ る か とい う問題 が あ る 。個 数 を求 め る 問題 が グ ラ フ論 で は 、 グ ラ フの 数 え上 げ 問題 とい わ れ て い る 。 一 方 、 グ ラ フの基 本 的 構 成 要 素 と して 点 の個 数 が 十分 大 きな場 合 の グ. 組(レ 『,Φ)をyの. 元 に標 識 づ け られ た グ ラ フ、. また は 単 に レ 上 標 識 グ ラ フ と呼 ぶ 。 混 乱 の な い 限 り、 「レ 上 標 識 」 を 省 略 す る こ と が し ば し ば あ る 。 グ ラ フ0-(y,Φ)に. つ い て 、yの. 要. 素 を点 と よ び 、 含 ま れ る 点 の 個 数 を θ の 位 数 と い い 、 ・(θ)で 表 す 。 ま た 、 Σ   (y)Φ ω を0の. 大 き さ と い い 、g(G)で. 表 す 。 η(0)-1,. ラ フの 数 え 上 げ 問題 は グ ラ フ論 で は グ ラ フの極. 9(G)=0な. る グ ラ フGは. 自明 な グ ラ フ と呼 ば. 値 問題 とい わ れ て い る 。本 稿 で は 、 点 の個 数 が. れ る 。 グ ラ フG-(レ,Φ)に. お い て 、 Φ 各{歪,ブ}. 与 え られ た場 合 で の グ ラ フの 数 え上 げ 問題 に 焦. ∈(y2)に. ㈲1こ. 点 を絞 っ て論 じる こ と とす る 。. 度 と い い 、 Φ({￠,ブ})≧1の. 対 し Φ ㈹})を. の 辺 と い う 。{z,ノ}が0の. 2グ. ラ フ の定 義. は 辺{z,フ}に し、. まず 、 グ ラ フ とは どん な もの で あ る か とい う こ と を含 め て 少 し広 くグ ラ フ の 定 義 を す る こ と. 一49一. の とき. と き 、{∫,ブ}を. θ. 辺 で あ る と き、 点 ゼ. 接 続 し て い る と い わ れ る 。 ゴに 対. Σ グ.照 ≠ゆ({∫,ブ})を. す べ て の{z. お け る重 複. ,ノ}∈. 、(玩. Φ)は. (レ2)に 対. 点 ゼの 次 数 と い う 。. し、 Φ({乞,ブ})≦1. 単 純 グ ラ フ とい う 。.

(2) 総合 社 会 学 部紀 要. 単 純 グ ラ フGに Φ({ゼ,ブ})-1}と E)と. 第1巻. 第1号. つ い て 、酬{〃}∈(y)1 書 く と 、0はyとEの. qω. 考 え て も よい。. 01と02は. つ Φ1一 Φ2が 成 り立 つ と き. 同 等 で あ る と い い 、Ol-02と. 点 ゼ,ブ ∈yに.   θω. ー乞1,ゼ2,…,. の 係 数 とす. の. 一 Σ2(η2)夷1(32) η=1. で あ り、0(の. 「{乞 ￠,∫2-十 一1}∈E,2-1,2,…,. ん一1」 を 満 た す と き 、PをGの. η!. る 指 数 型 母 関 数G@)は. お い て 、 ∫,ブ ∈ レ,G. ≠カ に 対 し、 異 な っ た 点 の 列P:ゼ 娠一ブが 条 件. ∬η. の 個 数 を 表 し て い る 。G。(1)を 書 く。. こ こで は 、 単純 グ ラ フの み を扱 う。 単 純 グ ラ フ θ=(y『,E)に. 一(1+灘)・(31). 1糞 籠q穐 臨 簸 擁∴. 2つ の グ ラ フG1-(y1,Φ1),G2-(y2,Φ2に つ い て 、y『1-y2か. 一 名(祝9)〆. 対(γ,. は標 識 グ ラ フ の 指 数 型 母 関 数 と. い わ れ る。. 道 と い う 。2. 対 し、 ゴと ブの 問 に 道 が 存 在 す る と. き 、 ゴと ブ は0に. お い て 連 結 し て い る と い う。. θ の ど の2点. も連結 して い る と き、θ は 連結. グ ラ フ とい わ れ る 。 自明 な グ ラ フは 連結 グ ラ フ と 定 め る 。0の. 部分 グ ラ フの うち 、 連結 とい う. 性 質 で の 極 大 な も の をGの(連. 結)成. 分 とい. う。 本 論 で は 、 互 い に 同等 で な い標 識 グ ラ フの個. 4連. 結 な標 識 グ ラ フ. この節 で は い ろ い ろ な種 類 の グ ラ フ の数 え上 げ を考 察す る。 この考 察 に とて も大 きな力 を発 揮 す る補 題 を用 意 す る。 グ ラ フ を観 察 す る と、 い ろ い ろ な 性 質 が 見 ら れ る 。 性 質Pを 考 え よ う。α.を性 質Pを. もつ 位 数 η の す べ て の グ ラ. 数 を考 察 す る こ とに す る 。 この ア プ ロ ー チ を標. フ を η個 の 名 前 の 組 か ら標 識 づ け る 仕 方 の 数. 識 グ ラ フ の 数 え 上 げ と 呼 ぶ 。Riddell[2]は. を表 す もの と し、指 数 型 母 関数. 標. 識 グ ラ フの 数 え 上 げ の 考 察 に1つ の た いへ ん 美 しい シ ンプ ル な方 程 式 を編 み 出 した。 こ こで 、 この 方程 式 の 適用 の広 さを観 察 して み た い 。.  . ・ω. れ. 一 Σ 砺 夷!・ η=1. を考 え る。 グ ラ フのサ イ ズ を考 慮 に入 れ る場 合 は 次 の指 数型 母 関数 が 考 え られ る。. 3標. 識 グ ラ フ の母 関数.  . ・(∬,〃)一 Σ. れ. 砺ω. 蒐!・. η=1. 点 集 合y-{ゴ1,ゴ2,…,帰 う ち 、 大 き さgの. (2)に は ω. 上 の標 識 グ ラ フ の. 標 識 グ ラ フ の 個 数 を考 え る。. 個の元があ るか ら・(ζ)か ら9. 個 の 元 を取 り出 しグ ラ フを構 成 す る 。構 成 され た こ の グ ラ フ は大 き さgのy上. こ こ で 、 δ。(〃)のプ の 係 数 は 性 質Pを. もつ位. 数 η、 サ イ ズgの 標 識 グ ラ フ の個 数(η 個 の 名 前 の 組 か ら標 識 づ け る 仕 方 の 数)を. 表す 高 々. ω 次の多項式であ る・. 標 識 グ ラフで. あ り、 取 り出 した σ個 の 組 が 異 な る と対 応 す. 補 題1. ∬η. る標 識 グ ラ フは 異 な っ た もの に な る 。 した が っ つs個. ∴噂 漁 二. の 係 数 は 、 性 質Pを も(1)α ∫(∬)に お け る η! の グ ラ フ01,02,…,0、 を並 べ た組. (θ1,G2,…,G、)の. うち これ らの グ ラ フが 互. い に共 通 な点 を持 た な く、 かつ. η(01)+η(02)+…+η(G。)一. ηを満 たす組 を. 1か ら η ま で の ラ ベ ル で 標 識 づ け る 仕 方 の 数 を. 項 式G。@)は. 標識 グラ フの数 え上 げ通常 型母. 関 数 とい わ れ 、 そ れ は. 一50一. 与 え る。.

(3) 標 識 グ ラ フの数 え上 げ 問題 につ い て の一 考 察. 二じη. (2)αs(偽 〃)に お け る ガ を も つs個. η!. の 係 数 は 性 質P. の グ ラ フOl,02,…,0、. た 組(θ1,θ パ. 定 理1.(Riddell[2]) 1十 θ(∬)一 θc(∬)(4.3). を 並 べ. ・・,G、)の う ち こ れ ら の グ. そ こ で 、(4.3)の. 形 を し た 式 をRiddell型. 方. ラ フ が 互 い に 共 通 な 点 を 持 た な く、 か つ. 程 式 と呼 ぶ こ と に す る 。(4.3)か. η(01)+η(02)+…+π(0。)一. 求 め る こ と は 困 難 で あ る。 そ こ で、 た い へ ん. η を 満 た し、. g(Gl)+g(G2)+…+g(G、)-gを を1か. 満 た す組. ら η ま で の ラベ ル で 標 識 づ け る 仕 方. 有 効 な 道 具 を 述 べ る 。 次 の 補 題 はHararyand Palmer[1]に. 見 られ る もの で あ る。 OQ. の 数 を与 え る 。. Σ ・!. oo. 補 題1に. お け る ∫個 の グ ラ フ の 組 の 中 に 並. 補 題2.. Σ 且ボ. べ る 順 序 を 考 え な い と す る な ら ば 、 α8(の あ る.   κ ル. 調 肱. 辮. で 表 さ れ、 ま た. ルΣ レ. 1. く. ・-1s!. 隅. Σ 。 。 αs(∬,〃) が あ. 対 して 、 篇. が あ る 指 数 型 母 関 数F(の. 芸郵). 現 α. ・!で割 れ ば よ ・・。 Σ ∵. な ら ば、. ー ・-1. 珊=0. 7η ≧1に. い は 鵡)を. ら 直 接 各C.を. が 成 り立 つ 。 る 指 数 型 母 関 数F(∬,〃)で 補 題2に. 表 され る もの とす る 。 す な わ ち. お い て、 塩. 一2㈲. 砺 一C規/辮!と お き、 等 式(4.3)に. 伽!お. よ び. 注 意 して 漸. 化式. Fω 一二 α芸1) s=1. ら 一2(2)一 ÷ Σ ん(鴛)挑(44) κ=1. F(偽 〃)一 望(脅!"). を 得 る 。(4.4)を. s=1. こ の2つ. の初 め の い く. つ か の 項 を求 め る と. の式はそれぞれ 一2αω. (4.1). 1+-F(偽 写)一θ礁"). (4.2). 1+Fω. 利 用 し てC(の. ∬)一. 十. と書 か れ る 。. ∬ 十. 灘24∬338」 十. じ4728∬5C( 十2!3!4! 5!. 十. 26704」 じ61866256灘7251548592二 十 十. じ8. 6!7!8!. Riddell[2]は. 連 結 と い う 性 質 を も っ た. 十. 66296291072∬934496488594816∬lo 十 10!9!. 標 識 グ ラ フ の 数 え 上 げ を 行 っ た 。C(∬)一. Σ 卿1蝶. を連 結 な灘. グ ラ フに対 す る母. 関 数 と す る 。 こ こ で 、C.は 位 数 η の 連 結 な 標 識 グ C5ω ラ フ の 個 数 で あ る 。 こ の と き、 は s! ち ょ う どs個. の成 分 を もつ標 識 グ ラ フ に対 す る. 指 数 型 母 関 数 で あ る 。 す な わ ち 、 この指 数型 母. 十 。。・(4.5). た と え ば 、C(∬)に. ∬4. お い て4! の 係 数38は. 4の 連 結 な 標 識 グ ラ フ が38通 し て い る 。 定 理1は. 位数. りあ る こ と を示. 点 の個 数 をパ ラ メ ー タに し. て連 結 標 識 グ ラ フを数 え上 げ て お り、 そ こでサ イ ズ もパ ラ メ ー タ に 含 め て の 連 結 標 識 グ ラ フ の. 」 じη. 関数 の. の 係 数 はs個. の 成 分 を もつ 位 数 η の. η! 標 識 グ ラ フの個 数 で あ る 。 この 指 数 型母 関 数 を s-1,2,3,…. に わ た っ て の和 は標 識 グ ラ フ の 指. 数 型 母 関 数0(の((3.2)で 与 え ら れ て い る)に 一致するはずであ る 。(4.1)に お い て 、F(の を θ(の 、 α(の をC(⑳. と置 き換 え て、 次 の 定 理. が 得 られ る 。. 数 え 上 げ を 考 え て み る 。 こ の 場 合 は2変. 母 関 数 の 考 察 に 通 じ る 。 母 関 数C(∬,雪)= 。。. ΣC。 れコユ. 」じ η. ω. 刎. を 考 え る 。 こ こ で 、C。(〃)の. ♂. の 係 数 は 位 数 η、 サ イ ズgの 連 結 な 標 識 グ ラ. 逗 響雛 菱腔   準 査 ち ょ う どs個. の 成 分 を もつ 標 識 グ ラ フ に 対 す る. 母 関 数 で あ り、 こ れ をs-1,2,3,…. 一51一. 数. にわた って.

(4) 総合社会学 部紀 要. 第1巻. 第1号. の和 は  . θ(鋤)一. れ. Σ(ち ω. 夷!. κ=1. に 等 れ. し い 。 こ こ で 、0。(〃)は(3.1)で. る 。(4.2)に. お. α(∬,〃)をC(∬,〃)に Riddell型. い 置. 与. え ら. てF(∬,〃)を0(∬,写)に き 換. 、. え る こ と に よ. り、. 方 程 式 が 得 られ る。. で与 え られ る。 d個. の 奇 点 を も つ 位 数 η、 サ イ ズgの. 連結 な. 標 識 グ ラ フ の 個 数 を 〆 〃d匂 の 係 数 に す る 母 関. 定 理2.. 数 をC。(∬,〃)と し、 指 数 型 母 関 数. 1+0(∬,写)=θc叫.  . 補 題2を. 用 い て漸 化 式. 傭)一. 傭)一. c(灘,〃,9)一.   コ. 謬. ん(ん)傭)q.、. ω. κ=1. を 考 え る 。[3]に. り. Σ(㌦(偽. 〃)1!.  . お い て 、C。(偽 〃)は 若 干 複 雑. な 方 法 で導 か れ た。 こ こで は、Riddel1型 方 程. を 得 る 。Cl(∬)=θ1(∬)=1で. あ る か ら、. 式 に視 点 をお い てC。(∬,〃)を導 く簡 単 な手 法 が あ る とい う こ とを紹 介 す る。 定 理3に 基 づ き新 た に指 数型 母 関 数 を定 義 す る。 す な わ ち 9η. ω。(∬,〃)を の係 数 にす る指 数 型 母 関数 η!  . ω(灘,〃,9)一. Σ 砺(偽. れ. 〃)1!. η=1. を 考 え る 。 ω(灘,〃,9)とC(∬,解)の て 、 再 びRiddell型. 定 理4.. が 得 ら れ る 。 た と え ば 、C4(∬)に 係 数6は. 位 数4、. サ イ ズ5の. お い て ゴ の. 連結 な標識 グラ フ. の 個 数 を示 し て い る 。 ま た 、C4(1)-38は(4.5) ∬4. に 見 られ るC(の. の4!の. 係 数 に一 致 す る 。. も う少 し微 細 に グ ラ フ の 分 類 を 考 察 して み る。点 に接続 す る辺 の個 数が その 点の 次数 で あ り、 次 数 が 奇 数 で あ る 点 を 奇 点 と よぶ 。 グ ラフの奇 点の個 数 はつ ねに偶 数で あ る ことは よ く知 られ て い る 。 次 の 定理 がTazawaand Shirakura[3]に. 定 理3.d個. よ っ て与 え られ た。. の 奇 点 を もつ 位 数 η、 サ イ ズg. の 標 識 グ ラ フ の 個 数 を ♂ ♂+9の 係 数 にす る母 関数は. 関係 につ い. 方程 式 が得 られ る 。.

(5) 標 識 グ ラ フの数 え上 げ 問題 につ い て の一 考 察. と書 き直 さ れ る 。 し た が っ て 、 位 数4の. 連結 な. 標 識 グ ラ フに つ い て 、 次 の表 が 示 され る。. ま た 、C4(1,1)=38で. あ. り 、 こ れ は(4.5)に. 見. ∬4. ら れ るC(∬)の. の 係 数 に 一 致 す る 。4!. 参考文献 L1] F. Harary and E.M. Palmer, Graphical Enumeration, Academic Press, New York and London, 1973. [2] R.J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951. [3] S. Tazawa and T. Shirakura, Enumeration of labelled graphs in which the number が 得 ら れ る 。 た と え ば 、C4(∬,〃)を うoC4(∬,〃)1よ. 考 え て み よ. of oddvertices. given, Kobe Journal 10(1993) 71-78.. and the size are of Mathematics.

(6)

参照

今ダウンロードする ( PDF - 5 ページ - 686.46 KB )

関連したドキュメント

マレーシアにおける障害のある人の権利確立に関す る研究

Denison Jayasooria, Disabled People Citizenship & Social Work,London: Asean Academic Press

雑誌名 金沢大学人間社会研究域学校教育系紀要

現実感のもてる問題場面からスタートし，問題 場面を自らの考えや表現を用いて表し，教師の

書評 本康宏史著『軍都の慰霊空間 : 国民統合と戦 死者たち』

する議論を欠落させたことで生じた問題をいくつか挙げて

① 曲面上のグラフの彩色について

（Robertson, Sanders, Seymour, Thomas,

② 曲面上のグラフの彩色について

Robertson-Seymour の結果により，左図のように disjoint

③ 曲面上のグラフの彩色について

変形を 2000 個準備する

New York Journal of Mathematics New York J. Math.

Proc. Studies in Logic and the Foundations of Mathematics, 73. North-Holland Publishing Co., Amsterdam- London; American Elsevier Publishing Co., Inc., New York, 1973..

Recent Advances in the Field of the Lactam Ring Formation Reaction from the Aspect of the Synthetic Chemistry. Koichi HIRAI * Recent advances in the f

Ulrich : Cycloaddition Reactions of Heterocumulenes 1967 Academic Press, New York, 84 J.L.. Prossel,