安定マッチングの最大数と安定結婚グラフについて

著者 宮下 奈央, 櫻本 篤司

雑誌名 福井大学教育地域科学部紀要

巻 4

ページ 81‑107

発行年 2014‑01‑10

URL http://hdl.handle.net/10098/8080

ٶԼɹಸԝ^*1 ɹɹᓎຊɹಞ࢘^*2

ɹ

ʢ2013೥9݄27೔ɹड෇ʣ ɹ

1 ^ংจ

҆ఆ݁ࠗ໰୊ͱ͸ɼෳ਺ͷஉੑͱঁੑ͕͍ͯɼͦΕͧΕҟੑʹର͠બ޷ॱংΛ͍࣋ͬͯΔͱ

͖ɼ͋Δछͷ҆ఆੑΛ࣋ͭϚονϯάʢஉঁͷ૊߹ͤʣΛٻΊΔ໰୊Ͱ͋Δɻ͜ͷ໰୊͸1962

೥ʹD. GaleͱL. S. ShapleyʹΑͬͯఏএ͞Εɼ൴Β͸҆ఆϚονϯάΛٻΊΔΞϧΰϦζϜ

(Gale-ShapleyΞϧΰϦζϜ)Λ։ൃ͠ɼͲͷΑ͏ͳ໰୊ʹରͯ͠΋ඞͣ҆ఆϚονϯά͕ଘࡏ

͢Δ͜ͱΛূ໌ͨ͠([5])ɻҰൠʹ҆ఆϚονϯά͸ෳ਺ଘࡏ͢Δ৔߹͕ଟ͘ɼGale-Shapley^Ξ ϧΰϦζϜͰٻΊΔ͜ͱ͕Ͱ͖ΔϚονϯά͸ɼஉੑ·ͨ͸ঁੑͷҰํʹͱͬͯ࠷΋ྑ͘ɼଞํ

ʹͱͬͯ͸࠷ѱͷϚονϯάͱͳ͍ͬͯΔɻͦ͜Ͱɼஉঁͷ૒ํ͕ೲಘ͢ΔϚονϯάΛٻΊΔ

ํ๏΍ɼϚονϯάͷධՁͳͲͷݚڀ͕ͳ͞Ε͍ͯΔɻ·ͨɼ҆ఆ݁ࠗ໰୊ʹ͸ଟ͘ͷछྨ͕͋

ΓɼஉঁͷϖΞͷΑ͏ͳ1^ର1Ͱ͸ͳ͘ɼݚमҩ഑ଐ໰୊ͳͲͷଟର1ͷϚονϯάΛٻΊΔ໰

୊΍ɼஉঁͷ2ͭͷάϧʔϓͰ͸ͳ̍ͭ͘ͷάϧʔϓͷதͰͷϚονϯάΛߟ͑Δ҆ఆϧʔϜϝ Πτ໰୊ͳͲ͕͋Γɼ࣮ੜ׆ͷ༷ʑͳ৔໘Ͱͦͷཧ࿦͕༻͍ΒΕ͍ͯΔɻ

ຊߘͰ͸ɼஉঁͷਓ਺͕ಉ਺ͷ҆ఆ݁ࠗ໰୊Λѻ͏ɻஉঁͷਓ਺͕ͱ΋ʹn^{ਓͰ͋Δ҆ఆ݁}

ࠗ໰୊ʢαΠζnͷ҆ఆ݁ࠗ໰୊ʣʹ͓͚Δ҆ఆϚονϯάͷ࠷େ਺Λf(n)ͱ͓͘ɻ͜ͷ࠷

େ਺f(n)ʹ͍ͭͯ΋ଟ͘ͷݚڀ͕ͳ͞Ε͍ͯΔɻn = 4ͷ৔߹͸D. E. Knuth[8]ʹΑΓ10 ݸͷ҆ఆϚονϯάΛ࣋ͭྫ͕ࣔ͞ΕɼD. Eilers͸ίϯϐϡʔλΛ༻͍ͯ͢΂ͯͷ҆ఆ݁ࠗ

໰୊ʹ͍ͭͯௐ΂Δ͜ͱͰf(4) = 10^{Ͱ͋Δ͜ͱΛࣔͨ͠}([4])^ɻn≥5^ͷ৔߹ͷf(n)^ͷਖ਼֬

ͳ஋͸·ͩಘΒΕ͍ͯͳ͍͕ɼ༷ʑͳධՁ͕ࣜಘΒΕ͍ͯΔɻҰൠʹn^͕2^{ͷྦྷ৐ͷ৔߹͸ɼ} g(1) = 1, g(2) = 2, g(2^m) = 3g(2^m−1)²−2g(2^m−2)^{2ʹΑͬͯఆ·Δ}g(2^m)^{Λ༻͍ͨԼ͔Βͷ} ධՁࣜf(2^m)≥g(2^m)^{͕ಘΒΕ͍ͯΔ}([7])ɻ҆ఆ݁ࠗ໰୊ʹ͓͍ͯɼબ޷ॱং͸҆ఆ݁ࠗάϥ ϑͱݺ͹ΕΔ༗޲άϥϑʹΑΓදݱ͢Δ͜ͱ͕ՄೳͰɼ͜ͷ҆ఆ݁ࠗάϥϑΛ༻͍ͯ͢΂ͯͷ҆

*1෱ҪେֶେֶӃڭҭֶݚڀՊڭՊڭҭઐ߈਺ֶڭҭྖҬ

*2෱Ҫେֶڭҭ஍ҬՊֶ෦ཧ਺ڭҭߨ࠲

宮　下　奈　央

　　櫻　本　篤　司

（2013年９月27日　受付）

ྫ 2.4. ^ྫ2.1ͷر๬ϦετͰ͸ɼϚονϯάM0={(h1, d1),(h2, d2),(h3, d3),(h4, d4)}^͸׬

શϚονϯάͰ͋Δɻ

ҎԼͰ͸ɼಛʹهड़͕ͳ͍ݶΓϚονϯά͸׬શϚονϯάΛࢦ͢΋ͷͱ͢Δɻ

ఆٛ 2.5. ^ϚονϯάM ʹ͓͍ͯɼϖΞΛ૊ΜͰ͍Δ૬खͷ͜ͱΛύʔτφʔͱݺͼɼஉੑh ͷύʔτφʔΛPM(h)^ɼঁੑd^{ͷύʔτφʔΛ}PM(d)^Ͱද͢ɻ

ྫ 2.5. ྫ2.4ͷϚονϯάM0Ͱ͸ɼPM0(h1) =d1,PM0(d2) =h2Ͱ͋Δɻ

ఆٛ 2.6. ϚονϯάM ʹ͓͍ͯɼҎԼͷ3ͭͷ৚݅(i),(ii),(iii)Λશͯຬͨ͢ϖΞ(h, d)Λ M ͷෆ҆ఆϖΞͱݺͿɻ

(i) (h, d)̸∈M, (ii) d <hPM(h), (iii) h <dPM(d).

ྫ 2.6. ^ྫ2.1ͷر๬ϦετͰ͸ɼϚονϯάM0ʹ͓͍ͯɼ

(h4, d1)∈/ M0, d1<h4d4=PM0(h4), h4<d1 h1=PM0(d1) Ͱ͋Δ͔Βɼ(h4, d1)^͸M0ͷෆ҆ఆϖΞͰ͋Δɻ

ఆٛ 2.7. ෆ҆ఆϖΞ͕ଘࡏ͠ͳ͍ϚονϯάΛ҆ఆϚονϯάɼෆ҆ఆϖΞ͕ଘࡏ͢ΔϚον ϯάΛෆ҆ఆϚονϯάͱݺͿɻ

ྫ 2.7. ^ྫ2.6^ΑΓM0 ={(h1, d1),(h2, d2),(h3, d3),(h4, d4)}^{͸ෆ҆ఆϖΞ}(h4, d1)^͕ଘࡏ͢

ΔͷͰෆ҆ఆϚονϯάͰ͋ΔɻͦΕʹରͯ͠ɼM1={(h1, d1),(h2, d4),(h3, d2),(h4, d3)}^͸ ෆ҆ఆϖΞ͕ଘࡏ͠ͳ͍ͷͰ҆ఆϚονϯάͰ͋Δɻ

ఆٛ 2.8. உੑू߹Hɼঁੑू߹D (H ∩D =∅,|H|=|D|=n)ʹ͓͍ͯɼ֤ਓ͕ҟੑશһ ʹରͯ͠બ޷ॱҐΛ͍࣋ͬͯΔͱ͖ɼ҆ఆϚονϯάΛݟ͚ͭΔ໰୊Λ҆ఆ݁ࠗ໰୊ͱ͍͏ɻ҆

ఆ݁ࠗ໰୊I͸உੑू߹Hɼঁੑू߹Dɼر๬ϦετLͷ3ͭ૊I= (H, D, L)ʹΑΓදݱ͞

ΕΔɻ

ఆٛ 2.9. ^{҆ఆ݁ࠗ໰୊}Iʹ͓͚Δ͢΂ͯͷ҆ఆϚονϯάͷू߹ΛM(I)^ͱද͢ɻ

ྫ 2.8. ^ྫ2.1ͷر๬ϦετͰ༩͑ΒΕΔ҆ఆ݁ࠗ໰୊ΛI^ͱ͢ΔͱɼM(I) ={M1, M2, M3} ͱͳΔɻͨͩ͠ɼ

M1={(h1, d1),(h2, d4),(h3, d2),(h4, d3)}, M2={(h1, d1),(h2, d2),(h3, d4),(h4, d3)}, M3={(h1, d4),(h2, d2),(h3, d3),(h4, d1)} Ͱ͋Δɻ

ఆϚονϯάΛٻΊΔ͜ͱ͕Ͱ͖ΔɻຊߘͰ͸ɼ҆ఆ݁ࠗάϥϑΛར༻ͯ҆͠ఆϚονϯάͷ࠷

େ਺f(n)ͷධՁࣜΛٻΊɼಘΒΕͨධՁࣜ΍҆ఆ݁ࠗάϥϑΛ༻͍ͨʢίϯϐϡʔλΛ࢖Θͳ

͍ʣٞ࿦Ͱf(3) = 3, f(4) = 10^Λࣔ͢ɻ

2 ^{҆ఆ݁ࠗ໰୊}

ఆٛ 2.1. nਓͷஉੑ͔ΒͳΔஉੑू߹H ={h1, h2,· · ·, hn}^ͱnਓͷঁੑ͔ΒͳΔঁੑू߹

D={d1, d2,· · ·, dn}͕ଘࡏ͠ɼ֤ਓ͸ҟੑશһΛಉҐͳ͠Ͱ޷͖ͳॱʹ1^{ྻʹฒ΂ͨબ޷ॱং}

Λ͍࣋ͬͯΔɻ͜ͷબ޷ॱংΛදͰදͨ͠΋ͷΛر๬Ϧετͱ͍͏ɻ

ر๬ϦετͰ͸ɼ֤ਓͷӈଆʹҟੑશһ͕ࠨ͔Βӈʹ޷͖ͳॱʹฒΜͰ͍Δɻ

ྫ 2.1. ر๬Ϧετ

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

͜ͷر๬ϦετͰ͸ɼஉੑh1ͷ޷͖ͳঁੑ͸ॱʹd2, d3, d1, d4Ͱ͋Γɼঁੑd4ͷ޷͖ͳஉ

ੑ͸ॱʹh1, h4, h3, h2Ͱ͋Δɻ

ఆٛ 2.2. ^உੑhͷબ޷ॱংʹ͓͚Δঁੑd^ͷॱҐΛrankh(d)^{Ͱද͠ɼঁੑ}d^{ͷબ޷ॱংʹ͓}

͚Δஉੑh^ͷॱҐΛrankd(h)^Ͱද͢ɻ

ྫ 2.2. ^ྫ2.1^{ͷر๬ϦετͰ͸ɼ}rankh2(d1) = 2,rankd3(h1) = 4^Ͱ͋Δɻ

ఆٛ 2.3. h, h^′ ∈H, d, d^′ ∈D^ͱ͢Δɻrankh(d)<rankh(d^′)^Ͱ͋Δͱ͖d <hd^{′ͱද͢ɻ·}

ͨɼrankd(h)<rankd(h^′)^Ͱ͋Δͱ͖h <dh^′ͱද͢ɻ

ྫ 2.3. ^ྫ2.1^{ͷر๬ϦετͰ͸ɼ}rankh1(d3) = 2,rankh1(d4) = 4^Ͱ͋Δ͔Βɼd3<h1 d4Ͱ

͋Δɻ·ͨɼrankd2(h2) = 1,rankd2(h4) = 3Ͱ͋Δ͔Βɼh2<d2 h4Ͱ͋Δɻ

ఆٛ2.4. Hʹଐ͢Δ1ਓͷஉੑͱDʹଐ͢Δ1ਓͷঁੑͷ૊ΛϖΞͱ͍͍ɼஉੑhi(∈H)ͱ

ঁੑdj(∈D)ͷϖΞΛ(hi, dj)ͱද͢ɻϖΞ͸H×DͷཁૉͰ͋Δɻ

H×D^{ͷ෦෼ू߹Ͱɼ୭΋͕}2ͭҎ্ͷϖΞʹଐ͞ͳ͍΋ͷΛϚονϯάͱ͍͏ɻϚονϯ ά͕n૊ͷϖΞΛؚΉͱ͖ɼͭ·Γ୭΋͕ϖΞʹଐ͍ͯ͠Δͱ͖ɼ͜ͷϚονϯάΛ׬શϚον ϯάͱ͍͏ɻɹ

ྫ2.4. ^ྫ2.1ͷر๬ϦετͰ͸ɼϚονϯάM0={(h1, d1),(h2, d2),(h3, d3),(h4, d4)}^͸׬

શϚονϯάͰ͋Δɻ

ҎԼͰ͸ɼಛʹهड़͕ͳ͍ݶΓϚονϯά͸׬શϚονϯάΛࢦ͢΋ͷͱ͢Δɻ

ఆٛ 2.5. ^ϚονϯάM ʹ͓͍ͯɼϖΞΛ૊ΜͰ͍Δ૬खͷ͜ͱΛύʔτφʔͱݺͼɼஉੑh ͷύʔτφʔΛPM(h)^ɼঁੑd^{ͷύʔτφʔΛ}PM(d)^Ͱද͢ɻ

ྫ2.5. ྫ2.4ͷϚονϯάM0Ͱ͸ɼPM0(h1) =d1,PM0(d2) =h2Ͱ͋Δɻ

ఆٛ 2.6. ϚονϯάM ʹ͓͍ͯɼҎԼͷ3ͭͷ৚݅(i),(ii),(iii)Λશͯຬͨ͢ϖΞ(h, d)Λ Mͷෆ҆ఆϖΞͱݺͿɻ

(i) (h, d)̸∈M, (ii) d <hPM(h), (iii) h <dPM(d).

ྫ2.6. ^ྫ2.1ͷر๬ϦετͰ͸ɼϚονϯάM0ʹ͓͍ͯɼ

(h4, d1)∈/ M0, d1<h4 d4=PM0(h4), h4<d1 h1=PM0(d1) Ͱ͋Δ͔Βɼ(h4, d1)^͸M0ͷෆ҆ఆϖΞͰ͋Δɻ

ఆٛ2.7. ෆ҆ఆϖΞ͕ଘࡏ͠ͳ͍ϚονϯάΛ҆ఆϚονϯάɼෆ҆ఆϖΞ͕ଘࡏ͢ΔϚον ϯάΛෆ҆ఆϚονϯάͱݺͿɻ

ྫ2.7. ^ྫ2.6^ΑΓM0={(h1, d1),(h2, d2),(h3, d3),(h4, d4)}^{͸ෆ҆ఆϖΞ}(h4, d1)^͕ଘࡏ͢

ΔͷͰෆ҆ఆϚονϯάͰ͋ΔɻͦΕʹରͯ͠ɼM1 ={(h1, d1),(h2, d4),(h3, d2),(h4, d3)}^͸ ෆ҆ఆϖΞ͕ଘࡏ͠ͳ͍ͷͰ҆ఆϚονϯάͰ͋Δɻ

ఆٛ 2.8. உੑू߹Hɼঁੑू߹D (H∩D =∅,|H|=|D| =n)ʹ͓͍ͯɼ֤ਓ͕ҟੑશһ ʹରͯ͠બ޷ॱҐΛ͍࣋ͬͯΔͱ͖ɼ҆ఆϚονϯάΛݟ͚ͭΔ໰୊Λ҆ఆ݁ࠗ໰୊ͱ͍͏ɻ҆

ఆ݁ࠗ໰୊I͸உੑू߹Hɼঁੑू߹Dɼر๬ϦετLͷ3ͭ૊I= (H, D, L)ʹΑΓදݱ͞

ΕΔɻ

ఆٛ2.9. ^{҆ఆ݁ࠗ໰୊}Iʹ͓͚Δ͢΂ͯͷ҆ఆϚονϯάͷू߹ΛM(I)^ͱද͢ɻ

ྫ2.8. ^ྫ2.1ͷر๬ϦετͰ༩͑ΒΕΔ҆ఆ݁ࠗ໰୊ΛI^ͱ͢ΔͱɼM(I) ={M1, M2, M3} ͱͳΔɻͨͩ͠ɼ

M1={(h1, d1),(h2, d4),(h3, d2),(h4, d3)}, M2={(h1, d1),(h2, d2),(h3, d4),(h4, d3)}, M3={(h1, d4),(h2, d2),(h3, d3),(h4, d1)} Ͱ͋Δɻ

ఆϚονϯάΛٻΊΔ͜ͱ͕Ͱ͖ΔɻຊߘͰ͸ɼ҆ఆ݁ࠗάϥϑΛར༻ͯ҆͠ఆϚονϯάͷ࠷

େ਺f(n)ͷධՁࣜΛٻΊɼಘΒΕͨධՁࣜ΍҆ఆ݁ࠗάϥϑΛ༻͍ͨʢίϯϐϡʔλΛ࢖Θͳ

͍ʣٞ࿦Ͱf(3) = 3, f(4) = 10^Λࣔ͢ɻ

2 ^{҆ఆ݁ࠗ໰୊}

ఆٛ2.1. nਓͷஉੑ͔ΒͳΔஉੑू߹H ={h1, h2,· · · , hn}^ͱnਓͷঁੑ͔ΒͳΔঁੑू߹

D={d1, d2,· · ·, dn}͕ଘࡏ͠ɼ֤ਓ͸ҟੑશһΛಉҐͳ͠Ͱ޷͖ͳॱʹ1^{ྻʹฒ΂ͨબ޷ॱং}

Λ͍࣋ͬͯΔɻ͜ͷબ޷ॱংΛදͰදͨ͠΋ͷΛر๬Ϧετͱ͍͏ɻ

ر๬ϦετͰ͸ɼ֤ਓͷӈଆʹҟੑશһ͕ࠨ͔Βӈʹ޷͖ͳॱʹฒΜͰ͍Δɻ

ྫ2.1. ر๬Ϧετ

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

͜ͷر๬ϦετͰ͸ɼஉੑh1ͷ޷͖ͳঁੑ͸ॱʹd2, d3, d1, d4Ͱ͋Γɼঁੑd4ͷ޷͖ͳஉ

ੑ͸ॱʹh1, h4, h3, h2Ͱ͋Δɻ

ఆٛ2.2. ^உੑhͷબ޷ॱংʹ͓͚Δঁੑd^ͷॱҐΛrankh(d)^{Ͱද͠ɼঁੑ}d^{ͷબ޷ॱংʹ͓}

͚Δஉੑh^ͷॱҐΛrankd(h)^Ͱද͢ɻ

ྫ2.2. ^ྫ2.1^{ͷر๬ϦετͰ͸ɼ}rankh2(d1) = 2,rankd3(h1) = 4^Ͱ͋Δɻ

ఆٛ2.3. h, h^′ ∈H, d, d^′ ∈D^ͱ͢Δɻrankh(d)<rankh(d^′)^Ͱ͋Δͱ͖d <hd^{′ͱද͢ɻ·}

ͨɼrankd(h)<rankd(h^′)^Ͱ͋Δͱ͖h <dh^′ͱද͢ɻ

ྫ 2.3. ^ྫ2.1^{ͷر๬ϦετͰ͸ɼ}rankh1(d3) = 2,rankh1(d4) = 4^Ͱ͋Δ͔Βɼd3<h1 d4Ͱ

͋Δɻ·ͨɼrankd2(h2) = 1,rankd2(h4) = 3Ͱ͋Δ͔Βɼh2<d2 h4Ͱ͋Δɻ

ఆٛ2.4. H ʹଐ͢Δ1ਓͷஉੑͱDʹଐ͢Δ1ਓͷঁੑͷ૊ΛϖΞͱ͍͍ɼஉੑhi(∈H)ͱ

ঁੑdj(∈D)ͷϖΞΛ(hi, dj)ͱද͢ɻϖΞ͸H×DͷཁૉͰ͋Δɻ

H×D^{ͷ෦෼ू߹Ͱɼ୭΋͕}2ͭҎ্ͷϖΞʹଐ͞ͳ͍΋ͷΛϚονϯάͱ͍͏ɻϚονϯ ά͕n૊ͷϖΞΛؚΉͱ͖ɼͭ·Γ୭΋͕ϖΞʹଐ͍ͯ͠Δͱ͖ɼ͜ͷϚονϯάΛ׬શϚον ϯάͱ͍͏ɻɹ

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

AH ͷ͏ͪɼஉੑh1ͱͷϖΞ(h1, d1),(h1, d2),(h1, d3),(h1, d4)ͷؒͷลʹ͍ͭͯߟ͑

Δɻஉੑh1ͷબ޷ॱং͸d2, d3, d1, d4Ͱ͋Δ͔ΒɼลΛਤࣔ͢Δͱ࣍ͷΑ͏ʹͳΔɻ

h1

d1 d2 d3 d4

͔͠͠ɼh1ͷબ޷ॱং͸࣍ͷล͚ͩͰද͢͜ͱ͕Ͱ͖Δɻ

h1

d1 d2 d3 d4

ͭ·Γɼrankh1(di) = rankh1(dj) + 1ͱͳΔล((h1, di),(h1, dj))͚ͩΛදࣔ͢Ε͹Α

͍ɻଞͷߦͱྻͰ΋ಉ༷Ͱ͋ΔͷͰɼ҆ఆ݁ࠗάϥϑΛඳ͘ࡍɼล͸

((h, d),(h, d^′)) (rankh(d) = rankh(d^′) + 1), ((h, d),(h^′, d)) (rankd(h) = rankd(h^′) + 1)

ͷΈΛඳ͘͜ͱʹ͢Δɻͭ·Γɼ҆ఆ݁ࠗάϥϑΛඳ͘ͱ͖͸બ޷ॱংΛද͢ͷʹඞཁ࠷

௿ݶͷลͷΈΛඳ͘ɻ

ྫ 3.1. H ={h1, h2, h3, h4}^ɼD={d1, d2, d3, d4}^{ͱ͠ɼر๬Ϧετ͸}

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

ͱ͢Δɻ͜ͷͱ͖ͷ҆ఆ݁ࠗάϥϑ͸࣍ͷΑ͏ʹͳΔɻ

3 ^{҆ఆ݁ࠗάϥϑ}

3.1

ر๬ϦετΛ༗޲άϥϑͰදͨ͠΋ͷΛ҆ఆ݁ࠗάϥϑͱݺͿɻ

ఆٛ3.1. ҆ఆ݁ࠗ໰୊ʹ͓͍ͯɼஉੑू߹ΛH,ঁੑू߹ΛDͱ͠ɼV =H×D,A=AH∪AD

ͱ͢Δɻͨͩ͠ɼ

AH={((h, d),(h, d^′))∈V ×V |d^′<hd}, AD={((h, d),(h^′, d))∈V ×V |h^′<dh} Ͱ͋Δɻ͜ͷͱ͖ɼ༗޲άϥϑΓ = (V, A)Λ҆ఆ݁ࠗάϥϑͱ͍͏ɻ

҆ఆ݁ࠗάϥϑͷඳ͖ํ

• ^఺ू߹

உੑू߹H ={h1, h2,· · ·, hn},^ঁੑू߹ D={d1, d2,· · · , dn}ͷ҆ఆ݁ࠗάϥϑͰ͸ɼ n^{2ݸͷ఺ΛԼਤͷΑ͏ʹ}n^ߦnྻʹฒ΂Δɻߦ͸্͔Βॱʹஉੑh1, h2,· · · , hnΛɼྻ

͸ࠨ͔Βॱʹd1, d2,· · ·, dnΛද͠ɼi^ߦj^{ྻͷ௖఺͸}(hi, dj)^{Λද͍ͯ͠Δɻ}

h1

h2

hn

d1 d2 dn

... ... ...

· · ·

· · ·

· · ·

ͳ͓ɼ֤ߦɼ֤ྻʹ͸ରԠ͢ΔஉੑɼঁੑΛϥϕϧͱ͚͓ͯͭͯ͘͠ɻ

• ^ลू߹

உੑू߹H ={h1, h2, h3, h4}^{ɼঁੑू߹} D ={d1, d2, d3, d4}Ͱɼر๬Ϧετ͕࣍ͷ৔

߹Ͱઆ໌͢Δɻ

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

AH ͷ͏ͪɼஉੑh1ͱͷϖΞ(h1, d1),(h1, d2),(h1, d3),(h1, d4)ͷؒͷลʹ͍ͭͯߟ͑

Δɻஉੑh1ͷબ޷ॱং͸d2, d3, d1, d4Ͱ͋Δ͔ΒɼลΛਤࣔ͢Δͱ࣍ͷΑ͏ʹͳΔɻ

h1

d1 d2 d3 d4

͔͠͠ɼh1ͷબ޷ॱং͸࣍ͷล͚ͩͰද͢͜ͱ͕Ͱ͖Δɻ

h1

d1 d2 d3 d4

ͭ·Γɼrankh1(di) = rankh1(dj) + 1ͱͳΔล((h1, di),(h1, dj))͚ͩΛදࣔ͢Ε͹Α

͍ɻଞͷߦͱྻͰ΋ಉ༷Ͱ͋ΔͷͰɼ҆ఆ݁ࠗάϥϑΛඳ͘ࡍɼล͸

((h, d),(h, d^′)) (rankh(d) = rankh(d^′) + 1), ((h, d),(h^′, d)) (rankd(h) = rankd(h^′) + 1)

ͷΈΛඳ͘͜ͱʹ͢Δɻͭ·Γɼ҆ఆ݁ࠗάϥϑΛඳ͘ͱ͖͸બ޷ॱংΛද͢ͷʹඞཁ࠷

௿ݶͷลͷΈΛඳ͘ɻ

ྫ3.1. H ={h1, h2, h3, h4}^ɼD={d1, d2, d3, d4}^{ͱ͠ɼر๬Ϧετ͸}

h1 : d2 d3 d1 d4 d1 : h4 h1 h3 h2

h2 : d4 d1 d2 d3 d2 : h2 h3 h4 h1

h3 : d2 d4 d3 d1 d3 : h3 h2 h4 h1

h4 : d3 d1 d4 d2 d4 : h1 h4 h3 h2

ͱ͢Δɻ͜ͷͱ͖ͷ҆ఆ݁ࠗάϥϑ͸࣍ͷΑ͏ʹͳΔɻ

3 ^{҆ఆ݁ࠗάϥϑ}

3.1

ر๬ϦετΛ༗޲άϥϑͰදͨ͠΋ͷΛ҆ఆ݁ࠗάϥϑͱݺͿɻ

ఆٛ3.1. ҆ఆ݁ࠗ໰୊ʹ͓͍ͯɼஉੑू߹ΛH,ঁੑू߹ΛDͱ͠ɼV =H×D,A=AH∪AD

ͱ͢Δɻͨͩ͠ɼ

AH={((h, d),(h, d^′))∈V ×V |d^′ <hd}, AD={((h, d),(h^′, d))∈V ×V |h^′<dh} Ͱ͋Δɻ͜ͷͱ͖ɼ༗޲άϥϑΓ = (V, A)Λ҆ఆ݁ࠗάϥϑͱ͍͏ɻ

҆ఆ݁ࠗάϥϑͷඳ͖ํ

• ^఺ू߹

உੑू߹H ={h1, h2,· · ·, hn},^ঁੑू߹ D={d1, d2,· · ·, dn}ͷ҆ఆ݁ࠗάϥϑͰ͸ɼ n^{2ݸͷ఺ΛԼਤͷΑ͏ʹ}n^ߦnྻʹฒ΂Δɻߦ͸্͔Βॱʹஉੑh1, h2,· · ·, hnΛɼྻ

͸ࠨ͔Βॱʹd1, d2,· · · , dnΛද͠ɼi^ߦj^{ྻͷ௖఺͸}(hi, dj)^{Λද͍ͯ͠Δɻ}

h1

h2

hn

d1 d2 dn

... ... ...

· · ·

· · ·

· · ·

ͳ͓ɼ֤ߦɼ֤ྻʹ͸ରԠ͢ΔஉੑɼঁੑΛϥϕϧͱ͚͓ͯͭͯ͘͠ɻ

• ^ลू߹

உੑू߹H ={h1, h2, h3, h4}^{ɼঁੑू߹}D ={d1, d2, d3, d4}Ͱɼر๬Ϧετ͕࣍ͷ৔

߹Ͱઆ໌͢Δɻ

ఆٛ 3.3. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}W ^ΛV ^{ͷ෦෼ू߹ͱ͢Δɻ}

͜ͷͱ͖ɼAW ={(s, t)∈A|s, t∈W}^ͱఆΊɼΓ^{ͷ෦෼άϥϑ} ΓW = (W, AW)^ΛW ^ʹ Αͬͯఆ·ΔΓͷ҆ఆ݁ࠗ෦෼άϥϑͱ͍͏ɻ

஫ҙɹW =V ^ͷ࣌͸ΓW = ΓͰ͋ΔͷͰɼ҆ఆ݁ࠗάϥϑ΋҆ఆ݁ࠗ෦෼άϥϑͱ͍͑Δɻ

ྫ 3.3. ྫ2.1ͷ҆ఆ݁ࠗ໰୊ʹ͓͍ͯɼW = (H×D)\ {(h1, d3),(h2, d1),(h3, d2),(h4, d4)} ͱ͢Δͱ͖ɼ҆ఆ݁ࠗ෦෼άϥϑ ΓW ͸࣍ͷΑ͏ʹͳΔɻ

h1

h2

h3

h4

d1 d2 d3 d4

҆ఆ݁ࠗ෦෼άϥϑͷ৔߹΋ɼลʹؔͯ͠͸બ޷ॱংΛද͢ͷʹඞཁ࠷௿ݶͷลͷΈΛඳ͘ɻ

ྫ͑͹ɼh1ͷߦͰ͸͢΂ͯͷลΛඳ͘ͱ

h1

d1 d2 d4

ͱͳΔ͕ɼh1ͷબ޷ॱংΛද͢ʹ͸࣍ͷ2^{ลͷΈͰे෼Ͱ͋Δɻ}

h1

d1 d2 d4

h1

h2

h3

h4

d1 d2 d3 d4

ఆٛ 3.2. ^{҆ఆ݁ࠗάϥϑ}Γ = (V, A)^ͷ఺(h, d)∈V ^{ʹର͠ɼҎԼͷ}4^{ͭͷू߹Λఆٛ͢Δɻ} pre_H(h, d) ={(h, d^′)∈V |d^′ <hd}, sucH(h, d) ={(h, d^′)∈V |d <hd^′}, pre_D(h, d) ={(h^′, d)∈V |h^′<dh}, sucD(h, d) ={(h^′, d)∈V |h <dh^′}.

ྫ 3.2. ^ྫ2.1ͷ҆ఆ݁ࠗάϥϑʹ͓͍ͯɼ఺(h3, d4)^ʹରͯ͠

pre_H(h3, d4) ={(h3, d2)}, sucH(h3, d4) ={(h3, d1),(h3, d3)}, pre_D(h3, d4) ={(h1, d4),(h4, d4)}, sucD(h3, d4) ={(h2, d4)}

ͱͳΔɻ

h1

h2

h3

h4

d1 d2 d3 d4

ఆٛ3.3. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}W^ΛV ^{ͷ෦෼ू߹ͱ͢Δɻ}

͜ͷͱ͖ɼAW ={(s, t)∈A|s, t∈W}^ͱఆΊɼΓ^{ͷ෦෼άϥϑ}ΓW = (W, AW)^ΛW ^ʹ Αͬͯఆ·ΔΓͷ҆ఆ݁ࠗ෦෼άϥϑͱ͍͏ɻ

஫ҙɹW =V ^ͷ࣌͸ΓW = ΓͰ͋ΔͷͰɼ҆ఆ݁ࠗάϥϑ΋҆ఆ݁ࠗ෦෼άϥϑͱ͍͑Δɻ

ྫ3.3. ྫ2.1ͷ҆ఆ݁ࠗ໰୊ʹ͓͍ͯɼW = (H×D)\ {(h1, d3),(h2, d1),(h3, d2),(h4, d4)} ͱ͢Δͱ͖ɼ҆ఆ݁ࠗ෦෼άϥϑΓW ͸࣍ͷΑ͏ʹͳΔɻ

h1

h2

h3

h4

d1 d2 d3 d4

҆ఆ݁ࠗ෦෼άϥϑͷ৔߹΋ɼลʹؔͯ͠͸બ޷ॱংΛද͢ͷʹඞཁ࠷௿ݶͷลͷΈΛඳ͘ɻ

ྫ͑͹ɼh1ͷߦͰ͸͢΂ͯͷลΛඳ͘ͱ

h1

d1 d2 d4

ͱͳΔ͕ɼh1ͷબ޷ॱংΛද͢ʹ͸࣍ͷ2^{ลͷΈͰे෼Ͱ͋Δɻ}

h1

d1 d2 d4

h1

h2

h3

h4

d1 d2 d3 d4

ఆٛ3.2. ^{҆ఆ݁ࠗάϥϑ}Γ = (V, A)^ͷ఺(h, d)∈V ^{ʹର͠ɼҎԼͷ}4^{ͭͷू߹Λఆٛ͢Δɻ} pre_H(h, d) ={(h, d^′)∈V |d^′ <hd}, sucH(h, d) ={(h, d^′)∈V |d <hd^′}, pre_D(h, d) ={(h^′, d)∈V |h^′<dh}, sucD(h, d) ={(h^′, d)∈V |h <dh^′}.

ྫ3.2. ^ྫ2.1ͷ҆ఆ݁ࠗάϥϑʹ͓͍ͯɼ఺(h3, d4)^ʹରͯ͠

pre_H(h3, d4) ={(h3, d2)}, sucH(h3, d4) ={(h3, d1),(h3, d3)}, pre_D(h3, d4) ={(h1, d4),(h4, d4)}, sucD(h3, d4) ={(h2, d4)}

ͱͳΔɻ

h1

h2

h3

h4

d1 d2 d3 d4

ূ໌ ɹ

఺(h, d)^{Λஉੑ࠷ྑ఺}(h^′, d)ʹࢧ഑͞ΕΔ఺Ͱ͋Δͱ͠ɼ(h, d)^{͕҆ఆϚονϯά}M ^ʹؚ·

ΕΔͱ͢ΔͱɼϚονϯάͷఆٛΑΓ(h^′, d)̸∈M ^{Ͱ͋Δɻ͢Δͱɼ}(h^′, d)^{͕உੑ࠷ྑ఺Ͱ͋Δ}

͜ͱΑΓd <h^′ PM(h^′)^ɼ(h, d)^͕(h^′, d)^{ʹࢧ഑͞ΕΔ͜ͱΑΓ}h^′<dh=PM(d)^ͱͳΔͷͰɼ (h^′, d)^͸M ^{ͷෆ҆ఆϖΞͱͳΔɻ}M ͸҆ఆϚονϯάͰ͋ΔͷͰɼ(h, d)^͸M ^ʹؚ·Εͳ͍

͜ͱ͕ݴ͑Δɻ

ಉ༷ʹͯ͠ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ͷ৔߹΋੒Γཱͭ͜ͱ͕ݴ͑Δɻ

͜ͷ໋୊ΑΓɼ҆ఆϚονϯάΛٻΊΔͱ͖͸ɼஉੑ࠷ྑ఺ɾঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͸আ

֎ͯ͠ߟ͑Ε͹Α͍͜ͱ͕Θ͔Δɻ

ఆٛ 3.5. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW = (W, AW)Λͦͷ҆ఆ݁ࠗ෦෼άϥϑͱ͢Δͱ

͖ɼ࣍ͷط໿ԽΞϧΰϦζϜͰಘΒΕΔ҆ఆ݁ࠗ෦෼άϥϑΓ^′ΛΓW ͷط໿҆ఆ݁ࠗ෦෼άϥ ϑͱ͍͏ɻಛʹɼW =V ^ͷͱ͖͸Γ^′_W ^ΛΓ^′ͱද͠ɼΓͷط໿҆ఆ݁ࠗάϥϑͱ͍͏ɻ ط໿ԽΞϧΰϦζϜɹ

0. W0=W, i= 0ͱ͢Δɻ

1. ΓWiʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͔ΒͳΔू߹ΛXi

ͱ͢Δɻ

2. (1) Xi̸=∅^ͳΒ͹Wi+1=Wi\Xiͱ͠ɼi+ 1^ͷ஋Λi^ͱͯ͠1.^ʹ໭Δɻ (2) Xi=∅^ͳΒ͹Γ^′_W = (Wi, AWi)^{ͱ͠ɼऴྃ͢Δɻ}

ྫ 3.5. ^ྫ2.1^{ͷ҆ఆ݁ࠗάϥϑ}Γ = (V, A)ʹରͯ͠ط໿ԽΞϧΰϦζϜΛߦ͏ɻ W0=V, i= 0^ͱ͢Δɻ

ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ఆٛ 3.4. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW = (W, AW)Λͦͷ҆ఆ݁ࠗ෦෼άϥϑͱ͠ɼ (h, d)^ɹ ∈W ^ͱ͢Δɻ

(1) pre_H(h, d)∩W =∅^Ͱ͋Δ఺(h, d)^ΛΓW ʹ͓͚Δஉੑ࠷ྑ఺ɼsucH(h, d)∩W =∅^Ͱ

͋Δ఺(h, d)ΛΓW ʹ͓͚Δஉੑ࠷ѱ఺ͱ͍͏ɻ

(2) pre_D(h, d)∩W =∅^Ͱ͋Δ఺(h, d)ΛΓW ʹ͓͚Δঁੑ࠷ྑ఺ɼsucD(h, d)∩W =∅^Ͱ

͋Δ఺(h, d)ΛΓW ʹ͓͚Δঁੑ࠷ѱ఺ͱ͍͏ɻ

(3) ఺(h, d)͕ΓW ʹ͓͚Δஉੑ࠷ྑ఺ͷͱ͖ɼsucD(h, d)∩W ʹଐ͢Δ఺ΛɼΓW ʹ͓͍

ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ͱ͍͏ɻ

(4) ^఺(h, d)^͕ΓW ʹ͓͚Δঁੑ࠷ྑ఺ͷͱ͖ɼsucH(h, d)∩W ^{ʹଐ͢Δ఺Λɼ}ΓW ʹ͓͍

ͯঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ͱ͍͏ɻ

҆ఆ݁ࠗάϥϑʹ͓͍ͯ͸ɼ࠷ྑ఺ʢ࠷ѱ఺ʣ͸બ޷ॱং͕࠷্Ґʢ࠷ԼҐʣͷҟੑͱͷϖΞ Λද͢఺Ͱ͋Δɻ

҆ఆ݁ࠗ෦෼άϥϑʹ͓͍ͯ͸ɼஉੑ࠷ྑ఺Λ˔Ͱɼঁੑ࠷ྑ఺Λ˕Ͱද͢͜ͱʹ͢Δɻ

ྫ 3.4. ^ྫ2.1ͷ҆ఆ݁ࠗάϥϑͷ৔߹͸ɼ(h1, d2),(h2, d4),(h3, d2),(h4, d3)^{͕உੑ࠷ྑ఺ɼ} (h1, d4),(h2, d2),(h3, d3),(h4, d1)^{͕ঁੑ࠷ྑ఺ͱͳΔɻ}

h1

h2

h3

h4

d1 d2 d3 d4

·ͨɼஉੑ࠷ྑ఺(h4, d3)ʹࢧ഑͞Ε͍ͯΔ఺͸(h1, d3)ɼঁੑ࠷ྑ఺(h3, d3)ʹࢧ഑͞Εͯ

͍Δ఺͸(h3, d1)^Ͱ͋Δɻ

໋୊ 3.1. உੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͸҆ఆϚονϯάʹؚ·Ε ͳ͍ɻ

ূ໌ ɹ

఺(h, d)^{Λஉੑ࠷ྑ఺}(h^′, d)ʹࢧ഑͞ΕΔ఺Ͱ͋Δͱ͠ɼ(h, d)^{͕҆ఆϚονϯά}M ^ʹؚ·

ΕΔͱ͢ΔͱɼϚονϯάͷఆٛΑΓ(h^′, d)̸∈M ^{Ͱ͋Δɻ͢Δͱɼ}(h^′, d)^{͕உੑ࠷ྑ఺Ͱ͋Δ}

͜ͱΑΓd <h^′ PM(h^′)^ɼ(h, d)^͕(h^′, d)^{ʹࢧ഑͞ΕΔ͜ͱΑΓ}h^′ <d h=PM(d)^ͱͳΔͷͰɼ (h^′, d)^͸M ^{ͷෆ҆ఆϖΞͱͳΔɻ}M ͸҆ఆϚονϯάͰ͋ΔͷͰɼ(h, d)^͸M ^ʹؚ·Εͳ͍

͜ͱ͕ݴ͑Δɻ

ಉ༷ʹͯ͠ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ͷ৔߹΋੒Γཱͭ͜ͱ͕ݴ͑Δɻ

͜ͷ໋୊ΑΓɼ҆ఆϚονϯάΛٻΊΔͱ͖͸ɼஉੑ࠷ྑ఺ɾঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͸আ

֎ͯ͠ߟ͑Ε͹Α͍͜ͱ͕Θ͔Δɻ

ఆٛ3.5. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW = (W, AW)Λͦͷ҆ఆ݁ࠗ෦෼άϥϑͱ͢Δͱ

͖ɼ࣍ͷط໿ԽΞϧΰϦζϜͰಘΒΕΔ҆ఆ݁ࠗ෦෼άϥϑΓ^′ΛΓW ͷط໿҆ఆ݁ࠗ෦෼άϥ ϑͱ͍͏ɻಛʹɼW =V ^ͷͱ͖͸Γ^′_W ^ΛΓ^′ͱද͠ɼΓͷط໿҆ఆ݁ࠗάϥϑͱ͍͏ɻ ط໿ԽΞϧΰϦζϜɹ

0. W0=W, i= 0ͱ͢Δɻ

1. ΓWiʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͔ΒͳΔू߹ΛXi

ͱ͢Δɻ

2. (1) Xi̸=∅^ͳΒ͹ Wi+1=Wi\Xiͱ͠ɼi+ 1^ͷ஋Λi^ͱͯ͠1.^ʹ໭Δɻ (2) Xi=∅^ͳΒ͹ Γ^′_W = (Wi, AWi)^{ͱ͠ɼऴྃ͢Δɻ}

ྫ3.5. ^ྫ2.1^{ͷ҆ఆ݁ࠗάϥϑ}Γ = (V, A)ʹରͯ͠ط໿ԽΞϧΰϦζϜΛߦ͏ɻ W0=V, i= 0^ͱ͢Δɻ

ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ఆٛ 3.4. Γ = (V, A)^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW = (W, AW)Λͦͷ҆ఆ݁ࠗ෦෼άϥϑͱ͠ɼ (h, d)^ɹ ∈W ^ͱ͢Δɻ

(1) pre_H(h, d)∩W =∅^Ͱ͋Δ఺(h, d)^ΛΓW ʹ͓͚Δஉੑ࠷ྑ఺ɼsucH(h, d)∩W =∅^Ͱ

͋Δ఺(h, d)ΛΓW ʹ͓͚Δஉੑ࠷ѱ఺ͱ͍͏ɻ

(2) pre_D(h, d)∩W =∅^Ͱ͋Δ఺(h, d)ΛΓW ʹ͓͚Δঁੑ࠷ྑ఺ɼsucD(h, d)∩W =∅^Ͱ

͋Δ఺(h, d)ΛΓW ʹ͓͚Δঁੑ࠷ѱ఺ͱ͍͏ɻ

(3) ఺(h, d)͕ΓW ʹ͓͚Δஉੑ࠷ྑ఺ͷͱ͖ɼsucD(h, d)∩W ʹଐ͢Δ఺ΛɼΓW ʹ͓͍

ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ͱ͍͏ɻ

(4) ^఺(h, d)^͕ΓW ʹ͓͚Δঁੑ࠷ྑ఺ͷͱ͖ɼsucH(h, d)∩W ^{ʹଐ͢Δ఺Λɼ}ΓW ʹ͓͍

ͯঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ͱ͍͏ɻ

҆ఆ݁ࠗάϥϑʹ͓͍ͯ͸ɼ࠷ྑ఺ʢ࠷ѱ఺ʣ͸બ޷ॱং͕࠷্Ґʢ࠷ԼҐʣͷҟੑͱͷϖΞ Λද͢఺Ͱ͋Δɻ

҆ఆ݁ࠗ෦෼άϥϑʹ͓͍ͯ͸ɼஉੑ࠷ྑ఺Λ˔Ͱɼঁੑ࠷ྑ఺Λ˕Ͱද͢͜ͱʹ͢Δɻ

ྫ 3.4. ^ྫ2.1ͷ҆ఆ݁ࠗάϥϑͷ৔߹͸ɼ(h1, d2),(h2, d4),(h3, d2),(h4, d3)^{͕உੑ࠷ྑ఺ɼ} (h1, d4),(h2, d2),(h3, d3),(h4, d1)^{͕ঁੑ࠷ྑ఺ͱͳΔɻ}

h1

h2

h3

h4

d1 d2 d3 d4

·ͨɼஉੑ࠷ྑ఺(h4, d3)ʹࢧ഑͞Ε͍ͯΔ఺͸(h1, d3)ɼঁੑ࠷ྑ఺(h3, d3)ʹࢧ഑͞Εͯ

͍Δ఺͸(h3, d1)^Ͱ͋Δɻ

໋୊ 3.1. உੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞ΕΔ఺͸҆ఆϚονϯάʹؚ·Ε ͳ͍ɻ

ΓW2 ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸ଘࡏ͠ͳ͍

ͷͰX2=∅^Ͱ͋ΓɼΓ^′= ΓW2 ͕Γͷط໿҆ఆ݁ࠗάϥϑͱͳΔɻ

ఆٛ 3.6. ^{҆ఆ݁ࠗ෦෼άϥϑ}ΓW ʹ͓͚Δ͢΂ͯͷ҆ఆϚονϯάͷू߹ΛM(ΓW)^ͱද͢ɻ

ఆཧ 3.1. ([3]) Γ^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW Λ҆ఆ݁ࠗ෦෼άϥϑͱ͢Δͱ͖ɼ

M(Γ) =M(Γ^′), M(ΓW) =M(Γ^′_W)

͕੒ཱ͢Δɻ

4 ҆ఆϚονϯάͷ࠷େ਺ʹ͍ͭͯ

4.1

͜͜Ͱ͸ɼ҆ఆ݁ࠗ໰୊ʹ͓͚Δ҆ఆϚονϯάͷ࠷େ਺ʹ͍ͭͯௐ΂Δɻ

ఆٛ 4.1. ^αΠζnͷ҆ఆ݁ࠗ໰୊ʹ͓͚Δ҆ఆϚονϯάͷ࠷େ਺Λf(n)^ͱද͢ɻ உঁnਓͣͭͷϚονϯάͷ਺͸࠷େͰ΋n!^ݸͳͷͰɼf(n)≤n!^Ͱ͋Δɻ

ྫ 4.1. f(n)≤n!^ΑΓɼf(1) = 1, f(2)≤2Ͱ͋Δɻ͜͜Ͱ࣍ͷر๬ϦετΛ࣋ͭαΠζ2^ͷ

҆ఆ݁ࠗ໰୊Λߟ͑Δɻ

h1 : d1 d2 d1 : h2 h1

h2 : d2 d1 d2 : h1 h2

2^{ͭͷ҆ఆϚονϯά}M1 ={(h1, d1),(h2, d2)}, M2={(h1, d2),(h2, d1)}^{͕ଘࡏ͢ΔͷͰɼ} f(2) = 2^Ͱ͋Δɻ

ఆٛ 4.2. H={h1, h2,· · ·, hn}^{Λஉੑू߹ɼ}D={d1, d2,· · · , dn}Λঁੑू߹ͱ͢ΔαΠζn ͷ҆ఆ݁ࠗ໰୊ΛIͱ͢Δɻ͜ͷͱ͖ɼ1≤i, j≤nʹରͯ͠

M^i,j={M ∈ M(I)|(hi, dj)∈M}

ͱఆΊΔɻ·ͨɼஉੑू߹Hi =H\ {hi}^{ɼঁੑू߹}Dj =D\ {dj}^{ͷ҆ఆ݁ࠗ໰୊Λ}Ii,jͱ

͓͖ɼͦͷ҆ఆ݁ࠗάϥϑΛΓi,jͱ͓͘ɻͨͩ͠ɼIi,jͷر๬Ϧετʹ͍ͭͯ͸ɼI^ͷر๬Ϧε τ͔ΒhiͱdjΛ࡟আ͢Δ͚ͩͰॱংͷೖΕସ͑͸͠ͳ͍ɻ

ΓW0ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸(h1, d2),(h1, d3),(h4, d2)^{ɼঁੑ࠷ྑ఺ʹࢧ഑}

͞Ε͍ͯΔ఺͸(h2, d3),(h3, d1),(h4, d2),(h4, d4)^Ͱ͋Δ͔Βɼ

X0={(h1, d2),(h1, d3),(h2, d3),(h3, d1),(h4, d2),(h4, d4)} ͱͳΔɻ

X0̸=∅^Ͱ͋Δ͔ΒɼW1=W0\X0(=V \X0)ͱ͠ɼΓW1 Λߟ͑Δɻ ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ɹΓW1ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸(h2, d1)ɼঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸ଘ ࡏ͠ͳ͍ͷͰɼX1={(h2, d1)}^ͱͳΔɻ

X1̸=∅^Ͱ͋Δ͔ΒɼW2=W1\X1(=V \(X0∪X1))ͱ͠ɼΓW2Λߟ͑Δɻ ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ΓW2 ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺ɼঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸ଘࡏ͠ͳ͍

ͷͰX2=∅^Ͱ͋ΓɼΓ^′= ΓW2͕Γͷط໿҆ఆ݁ࠗάϥϑͱͳΔɻ

ఆٛ3.6. ^{҆ఆ݁ࠗ෦෼άϥϑ}ΓW ʹ͓͚Δ͢΂ͯͷ҆ఆϚονϯάͷू߹ΛM(ΓW)^ͱද͢ɻ

ఆཧ3.1. ([3]) Γ^{Λ҆ఆ݁ࠗάϥϑɼ}ΓW Λ҆ఆ݁ࠗ෦෼άϥϑͱ͢Δͱ͖ɼ

M(Γ) =M(Γ^′), M(ΓW) =M(Γ^′_W)

͕੒ཱ͢Δɻ

4 ҆ఆϚονϯάͷ࠷େ਺ʹ͍ͭͯ

4.1

͜͜Ͱ͸ɼ҆ఆ݁ࠗ໰୊ʹ͓͚Δ҆ఆϚονϯάͷ࠷େ਺ʹ͍ͭͯௐ΂Δɻ

ఆٛ4.1. ^αΠζnͷ҆ఆ݁ࠗ໰୊ʹ͓͚Δ҆ఆϚονϯάͷ࠷େ਺Λf(n)^ͱද͢ɻ உঁnਓͣͭͷϚονϯάͷ਺͸࠷େͰ΋n!^ݸͳͷͰɼf(n)≤n!^Ͱ͋Δɻ

ྫ4.1. f(n)≤n!^ΑΓɼf(1) = 1, f(2)≤2Ͱ͋Δɻ͜͜Ͱ࣍ͷر๬ϦετΛ࣋ͭαΠζ2^ͷ

҆ఆ݁ࠗ໰୊Λߟ͑Δɻ

h1 : d1 d2 d1 : h2 h1

h2 : d2 d1 d2 : h1 h2

2^{ͭͷ҆ఆϚονϯά}M1={(h1, d1),(h2, d2)}, M2 ={(h1, d2),(h2, d1)}^{͕ଘࡏ͢ΔͷͰɼ} f(2) = 2^Ͱ͋Δɻ

ఆٛ4.2. H ={h1, h2,· · ·, hn}^{Λஉੑू߹ɼ}D={d1, d2,· · · , dn}Λঁੑू߹ͱ͢ΔαΠζn ͷ҆ఆ݁ࠗ໰୊ΛIͱ͢Δɻ͜ͷͱ͖ɼ1≤i, j≤nʹରͯ͠

M^i,j={M ∈ M(I)|(hi, dj)∈M}

ͱఆΊΔɻ·ͨɼஉੑू߹Hi =H\ {hi}^{ɼঁੑू߹}Dj =D\ {dj}^{ͷ҆ఆ݁ࠗ໰୊Λ}Ii,jͱ

͓͖ɼͦͷ҆ఆ݁ࠗάϥϑΛΓi,jͱ͓͘ɻͨͩ͠ɼIi,jͷر๬Ϧετʹ͍ͭͯ͸ɼI^ͷر๬Ϧε τ͔ΒhiͱdjΛ࡟আ͢Δ͚ͩͰॱংͷೖΕସ͑͸͠ͳ͍ɻ

ΓW0ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸(h1, d2),(h1, d3),(h4, d2)^{ɼঁੑ࠷ྑ఺ʹࢧ഑}

͞Ε͍ͯΔ఺͸(h2, d3),(h3, d1),(h4, d2),(h4, d4)^Ͱ͋Δ͔Βɼ

X0={(h1, d2),(h1, d3),(h2, d3),(h3, d1),(h4, d2),(h4, d4)} ͱͳΔɻ

X0̸=∅^Ͱ͋Δ͔ΒɼW1=W0\X0(=V \X0)ͱ͠ɼΓW1Λߟ͑Δɻ ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ɹΓW1 ʹ͓͍ͯஉੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸(h2, d1)ɼঁੑ࠷ྑ఺ʹࢧ഑͞Ε͍ͯΔ఺͸ଘ ࡏ͠ͳ͍ͷͰɼX1={(h2, d1)}^ͱͳΔɻ

X1̸=∅^Ͱ͋Δ͔ΒɼW2=W1\X1(=V \(X0∪X1))ͱ͠ɼΓW2Λߟ͑Δɻ ɹ

h1

h2

h3

h4

d1 d2 d3 d4

ྫ 4.3. ^ྫ2.1^{ͷ҆ఆ݁ࠗ໰୊Λ}I^ͱ͠ɼM(I3,2)^ΛٻΊΔɻI3,2ͷر๬Ϧετ͸

h1 : d3 d1 d4 d1 : h4 h1 h2

h2 : d4 d1 d3 d3 : h2 h4 h1

h4 : d3 d1 d4 d4 : h1 h4 h2

Ͱ͋Γɼط໿҆ఆ݁ࠗάϥϑ͸࣍ͷΑ͏ʹͳΔɻ

h1

h2

h4

d1 d3 d4

I3,2͸҆ఆϚονϯάMa={(h1, d1),(h2, d4),(h4, d3)}, Mb={(h1, d4),(h2, d3),(h4, d1)}^Λ

࣋ͪɼM(I3,2) ={Ma, Mb}^{Ͱ͋ΔɻΑͬͯɼ}|M(I3,2)|= 2^ͱͳΓɼྫ4.2^ΑΓ|M^3,2|= 1^Ͱ

͋Δ͔Βɼ|M^3,2| ≤ |M(I3,2)|^{͕੒ཱ͢Δɻ}

͜ͷྫͰ΋෼͔ΔΑ͏ʹɼ|M^i,j|=|M(Ii,j)|͕੒Γཱͭͱ͸ݶΒͳ͍ɻ

໋୊ 4.3. f(n)≤nf(n−1)

ূ໌ ɹ

I^Λf(n)ݸͷ҆ఆϚονϯάΛ࣋ͭαΠζnͷ҆ఆ݁ࠗ໰୊ͱ͢Δɻ

͜ͷͱ͖ɼIi,j͸αΠζn−1ͷ҆ఆ݁ࠗ໰୊ͱͳΓɼ

|M^i,j| ≤ |M(Ii,j)| ≤f(n−1).

ैͬͯ

f(n) =|M(I)|=

∑n

j=1

|M^i,j| ≤

∑n

j=1

f(n−1) =nf(n−1)

ͱͳΔɻ

ྫ 4.2. ^ྫ2.1^{ͷ҆ఆ݁ࠗ໰୊}I^{ʹରͯ͠͸ɼҎԼͷ}3ͭͷ҆ఆϚονϯά͕ଘࡏ͢Δɻ M1={(h1, d1),(h2, d4),(h3, d2),(h4, d3)},

M2={(h1, d1),(h2, d2),(h3, d4),(h4, d3)}, M3={(h1, d4),(h2, d2),(h3, d3),(h4, d1)}.

ैͬͯɼM^1,1={M1, M2},M^3,2={M1}^{Ͱ͋Δɻ·ͨɼ}I3,2ͷر๬Ϧετ͸࣍ͷΑ͏ʹͳΔɻ h1 : d3 d1 d4 d1 : h4 h1 h2

h2 : d4 d1 d3 d3 : h2 h4 h1

h4 : d3 d1 d4 d4 : h1 h4 h2

ϚονϯάͷఆٛΑΓɼ͕࣍੒Γཱͭɻ

໋୊ 4.1. ^ɹ

(1) M^i,j∩ M^i,k =M^j,i∩ M^k,i =∅ (j̸=k) (2) M(I) =

∪n

j=1

M^i,j=

∪n

j=1

M^j,i (3) |M(I)|=

∑n

j=1

|M^i,j|=

∑n

j=1

|M^j,i|

໋୊4.1(3)ΑΓɼ҆ఆ݁ࠗ໰୊Iʹ͓͚ΔϚονϯάͷ਺͸ɼM^i,jͷཁૉͷݸ਺͔ΒٻΊΔ

͜ͱ͕Ͱ͖Δɻ

|M^i,j|ʹ͍ͭͯ͸͕࣍੒Γཱͭɻ

໋୊ 4.2. ^ɹ

(1) M ∈ M^i,jʹରͯ͠M^′=M \ {(hi, dj)}^ͱ͓͘ͱ͖ɼM^′∈ M(Ii,j)^Ͱ͋Δɻ (2) |M^i,j| ≤ |M(Ii,j)|

ূ໌ ɹ

(1) M ͸ϚονϯάͰ͋Δ͔ΒɼM^′΋ϚονϯάͰ͋Δɻ·ͨɼM^′͕ෆ҆ఆϖΞ(h, d)Λ

࣋ͭͱ͢Δͱɼ(h, d)͸M ʹ͓͍ͯ΋ෆ҆ఆϖΞͱͳΔɻ͜Ε͸M͕҆ఆϚονϯάͰ

͋Δ͜ͱʹໃ६͢Δ͔ΒɼM^′΋҆ఆϚονϯάͰ͋ΓɼM^′∈ M(Ii,j)͕੒Γཱͭɻ (2) (1)ΑΓ{M^′ | M ∈ M^i,j} ⊂ M(Ii,j)Ͱ͋ΓɼM1, M2 ∈ M^i,j, M1 ̸=M2ͱ͢Δͱ

M₁^′ ̸=M₂^{′ Ͱ͋Δ͔Βɼ}|M^i,j| ≤ |M(Ii,j)|^{͕੒Γཱͭɻ}