組合せ最適化 第1,2章 M2  酒井 隆行.

Slides:



Advertisements
Similar presentations
ゲームプログラミング講習 第2章 関数の使い方
Advertisements

サービス管理責任者等研修テキスト 分野別講義    「アセスメントと        支援提供の基本姿勢」 <児童発達支援管理責任者> 平成27年10月1日.
ヒトの思考プロセスの解明を目的とするワーキングメモリの研究
第27講 オームの法則 電気抵抗の役割について知る オームの法則を使えるようにする 抵抗の温度変化を理解する 教科書P.223~226
コラッツ予想の変形について 東邦大学 理学部 情報科 白柳研究室 山中 陽子.
コンパイラ 第3回 字句解析 ― 決定性有限オートマトンの導出 ―
第5章 家計に関する統計 ー 経済統計 ー.
公共財 公共経済論 II no.3 麻生良文.
VTX alignment D2 浅野秀光 2011年12月15日  放射線研ミーティング.
冷却フランシウム原子を用いた 電子の永久電気双極子能率探索のための ルビジウム磁力計の研究
生命情報学 (8) スケールフリーネットワーク
前半戦 「史上最強」風 札上げクイズ.

認知症を理解し 環境の重要性について考える
フッ化ナトリウムによる洗口 2010・9・13 宮崎市郡東諸県郡薬剤師会 学校薬剤師  日高 華代子.
食品の安全性に関わる社会システム:総括 健康弱者 ハイリスク集団 HACCP (食肉処理場・食品工場) 農場でのQAP 一般的衛生管理
規制改革とは? ○規制改革の目的は、経済の活性化と雇用の創出によって、   活力ある経済社会の実現を図ることにあります。
地域保健対策検討会 に関する私見(保健所のあり方)
公共政策大学院 鈴木一人 第8回 専門化する政治 公共政策大学院 鈴木一人
医薬品ネット販売規制について 2012年5月31日 ケンコーコム株式会社.
平成26年8月27日(水) 大阪府 健康医療部 薬務課 医療機器グループ
平成26年度 呼吸器学会からの提案結果 (オレンジ色の部分が承認された提案) 新規提案 既収載の変更 免疫組織化学染色、免疫細胞化学染色
エナジードリンクの危険性 2015年6月23日 経営学部市場戦略学科MR3195稲沢珠依.
自動吸引は 在宅を変えるか 大分協和病院 院長         山本 真.
毎月レポート ビジネスの情報 (2016年7月号).
医療の歴史と将来 医療と医薬品産業 個人的経験 3. 「これからの医療を考える」 (1)医薬品の研究開発 -タクロリムスの歴史-
社会福祉調査論 第4講 2.社会調査の概要 11月2日.
2015年12月28日-2016年3月28日 掲載分.
2010度 民事訴訟法講義 補論 関西大学法学部教授 栗田 隆.
腫瘍学概論 埼玉医科大学国際医療センター 包括的がんセンター 緩和医療科/緩和ケアチーム 奈良林 至
“企業リスクへの考え方に変化を求められています。 トータルなリスクマネジメント・サービスをプロデュースします。“
情報漏えい 経済情報学科 E  西村 諭 E  釣 洋平.
金融班(ミクロ).
第11回 2009年12月16日 今日の資料=A4・4枚+解答用紙 期末試験:2月3日(水)N2教室
【ABL用語集】(あいうえお順) No 用語 解説 12 公正市場価格 13 債権 14 指名債権 15 事業収益資産 16 集合動産 17
基礎理論(3) 情報の非対称性と逆選択 公共政策論II No.3 麻生良文.
浜中 健児 昭和42年3月27日生まれ 東京都在住 株式会社ピー・アール・エフ 代表取締役 (学歴) 高 校:千葉県立東葛飾高校 卒業
COPYRIGHT(C) 2011 KYUSHU UNIVERSITY. ALL RIGHTS RESERVED
Blosxom による CMS 構築と SEO テクニック
記入例 JAWS DAYS 2015 – JOB BOARD 会社名 採用職種 営業職/技術職/その他( ) 仕事内容 待遇 募集数
ネットビジネスの 企業と特性 MR1127 まさ.
Future Technology活用による業務改革
ネットビジネス論(杉浦) 第8回 ネットビジネスと情報技術.
g741001 長谷川 嵩 g740796 迫村 光秋 g741000 西田 健太郎 g741147 小井出 真聡
自然独占 公共経済論 II no.5 麻生良文.
Autonomic Resource Provisioning for Cloud-Based Software
Webショップにおける webデザイン 12/6 08A1022 甲斐 広大.
物理的な位置情報を活用した仮想クラウドの構築
ハイブリッドクラウドを実現させるポイントと SCSKのOSSへの取組み
寺尾 敦 青山学院大学社会情報学部 第12回 情報デザイン(4) 情報の構造化と表現 寺尾 敦 青山学院大学社会情報学部
【1−1.開発計画 – 設計・開発計画】 システム開発計画にはシステム開発を効率的、効果的に実行する根拠(人員と経験、開発手順、開発・導入するシステム・アプリケーション・サービス等)を記述すること。 システム開発の開始から終了までの全体スケジュールを記載すること。 アプリケーション機能配置、ソフトウェア、インフラ構成、ネットワーク構成について概要を示すこと。
6 日本のコーポレート・ガバナンス 2008年度「企業論」 川端 望.
急成長する中国ソフトウェア産業 中国ソフトウェアと情報サービス産業の規模 総売上高は5年間で約5.3倍の成長
米国ユタ州LDS病院胸部心臓外科フェローの経験
公益社団法人日本青年会議所 関東地区埼玉ブロック協議会 JCの情熱(おもい)育成委員会 2011年度第1回全体委員会
次世代大学教育研究会のこれまでの活動 2005年度次世代大学教育研究大会 明治大学駿河台校舎リバティタワー9階1096教室
子どもの本の情報 大阪府内の協力書店の情報 こちらをクリック 大阪府内の公立図書館・図書室の情報
第2回産業調査 小島浩道.
〈起点〉を示す格助詞「を」と「から」の選択について
広東省民弁本科高校日語専業骨幹教師研修会 ①日本語の格助詞の使い分け ②動詞の自他受身の選択について   -日本語教育と中日カルチャーショックの観点から- 名古屋大学 杉村 泰.
■5Ahバッテリー使用報告 事例紹介/東【その1】 ■iphon4S(晴れの昼間/AM8-PM3) ◆約1時間で68%⇒100%
『ワタシが!!』『地域の仲間で!!』 市民が始める自然エネルギー!!
ポイントカードの未来形を形にした「MUJI Passport」
SAP NetWeaver を支える Microsoft テクノロジーの全貌 (Appendix)
ガイダンス(内業) 測量学実習 第1回.
Python超入門 久保 幹雄 東京海洋大学.
熱力学の基礎 丸山 茂夫 東京大学大学院 工学系研究科 機械工学専攻
京都民医連中央病院 CHDF学習推進委員会
資料2-④ ④下水道.
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Presentation transcript:

組合せ最適化 第1,2章 M2  酒井 隆行

第1章 はじめに 様々な実際的な問題 抽象的な最適化問題

第1章 はじめに 様々な実際的な問題 抽象的な最適化問題 例えば…

なるべく早く、ドリルで板の複数個の位置に穴をあけたい 第1章 はじめに 最適化問題の例1 なるべく早く、ドリルで板の複数個の位置に穴をあけたい (移動は等速) 問題1.1 ドリル穴あけ問題(Drilling Problem) インスタンス: 平面上のn個の点  𝑝 1 ,…, 𝑝 𝑛 ∈ 𝑅 𝑛 タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛

第1章 はじめに 最適化問題の例1 各従業員にジョブを割り振る 担当可能なジョブは従業員ごとに異なる 処理能力の差はない 第1章 はじめに 最適化問題の例1 各従業員にジョブを割り振る 担当可能なジョブは従業員ごとに異なる 処理能力の差はない 同一のジョブに対して、同時に複数の従業員が担当可 従業員は複数のジョブを担当可(同時には不可) 早く終わらせたい 問題1.2 ジョブ割当問題(Job Assignment Probrem) インスタンス:  n個の非負実数 𝑡 1 ,…, 𝑡 𝑛 ∈ 𝑅 + (ジョブの処理時間)     m人の従業員と各ジョブ𝑖∈ 1,…,𝑛 に対する担当可な従業員 の部分集合 𝑆 𝑖 ∈ 1,…,𝑚 タスク:  各𝑖=1,…,𝑛で 𝑗∈ 𝑆 𝑖 𝑥 𝑖,𝑗 = 𝑡 𝑖 を満たす 𝑥 𝑖𝑗 ∈ 𝑅 + 𝑖=1,…,𝑛, 𝑗∈ 𝑆 𝑖 の うちで、 max 𝑗∈ 1,…,𝑚 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 が最小となるような 𝑥 𝑖𝑗 ∈ 𝑅 + を求める

1.1 列挙 問題1.1 ドリル穴あけ問題(Drilling Problem) タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛 最適解を計算するアルゴリズムは…? 順列を全列挙すると最適解は見つかる

1.1 列挙 アルゴリズム1.1 パス列挙アルゴリズム (Path Enumeration Algorithm) 出力:  パスの長さ 𝑐𝑜𝑠𝑡 𝜋 ∗ ≔ 𝑖=1 𝑛−1 𝑑 𝑝 𝜋 ∗ 𝑖 , 𝑝 𝜋 ∗ 𝑖+1 が最小とな る順列 𝜋 ∗ : 1,…,𝑛 → 1,…,𝑛 (疑似コード略) 順列を、辞書式順に小さいものから順に調べて、 costの最も小さいものを保存 O 𝑛 2 𝑛! (解析は甘い)   もっと高速なアルゴリズムは…?

1.2 アルゴリズムの計算時間 アルゴリズムの入力 = 数のリスト 数がすべて整数ならば、2進数表現でコード化可能 有理数は分母と分子を別々にコード化 有理数データからなるインスタンスxに対して、 入力サイズ𝑠𝑖𝑧𝑒 𝑥 = すべての数の2進数表現に必要なビット数

1.2 アルゴリズムの計算時間 定義1.3 A: 集合Xの要素を入力として受け取るアルゴリズム 𝑓: 𝑁→ 𝑅 + 𝑓: 𝑁→ 𝑅 + ある定数𝛼>0が存在して、任意の入力𝑥∈𝑋に対して Aがその計算を高々𝛼𝑓 𝑠𝑖𝑧𝑒 𝑥 回の初等的操作で終了するならば Aは𝑶 𝒇 時間で走る or Aの計算時間は𝑶 𝒇 である という

1.2 アルゴリズムの計算時間 定義1.4 有理数入力に対するアルゴリズム ある整数kが存在して、入力サイズnのどの入力に対しても、𝑂 𝑛 𝑘 時間で走り、計算の途中で生じる数もすべて𝑂 𝑛 𝑘 ビットで記憶で きるとき、多項式時間で走るという 任意の入力に対するアルゴリズム ある整数kが存在して、n個の数のどの入力に対しても𝑂 𝑛 𝑘 時間 で走り、有理数入力に対しても多項式時間で走るとき、強多項式 時間で走るという k=1のときは線形時間アルゴリズムという

1.3 線形の最適化問題 問題1.2 ジョブ割当問題(Job Assignment Probrem) 1.3 線形の最適化問題 問題1.2 ジョブ割当問題(Job Assignment Probrem) インスタンス:  n個の非負実数 𝑡 1 ,…, 𝑡 𝑛 ∈ 𝑅 + (ジョブの処理時間)     m人の従業員と各ジョブ𝑖∈ 1,…,𝑛 に対する担当可な従業員 の部分集合 𝑆 𝑖 ∈ 1,…,𝑚 タスク:  各𝑖=1,…,𝑛で 𝑗∈ 𝑆 𝑖 𝑥 𝑖,𝑗 = 𝑡 𝑖 を満たす 𝑥 𝑖𝑗 ∈ 𝑅 + 𝑖=1,…,𝑛, 𝑗∈ 𝑆 𝑖 の うちで、 max 𝑗∈ 1,…,𝑚 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 が最小となるような 𝑥 𝑖𝑗 ∈ 𝑅 + を求める ジョブが完了する時刻Tを用いて、線形計画問題として定式化可能 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 ) 𝑥 𝑖𝑗 ≥0 (𝑖∈ 1,…,𝑛 ,𝑗∈ 𝑆 𝑖 ) 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤𝑇 (𝑖∈ 1,…,𝑛 )

1.3 線形の最適化問題 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 ) 1.3 線形の最適化問題 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 ) 𝑥 𝑖𝑗 ≥0 (𝑖∈ 1,…,𝑛 ,𝑗∈ 𝑆 𝑖 ) 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤𝑇 (𝑖∈ 1,…,𝑛 ) すべての実行可能解の集合は多面体と呼ばれ、凸であることがわかる。 最適解が存在するならば、必ず多面体の頂点のいずれかが最適解となる 列挙よりもいい方法がある(後の章で) 集合 𝑆 𝑖 をグラフでモデル化すると… 各ジョブiと各従業員jに対して頂点を考える ジョブと、そのジョブを担当できる従業員を結ぶ 多くの組合せ最適化問題はグラフ理論を用いて定式化される

1.3 線形の最適化問題 便宜上、 どのジョブも処理時間は1時間 1時間でジョブを全部完了できるか という問題を考えると… 1.3 線形の最適化問題 便宜上、 どのジョブも処理時間は1時間 1時間でジョブを全部完了できるか という問題を考えると… すべてのiとjに対して 0≤ 𝑥 𝑖𝑗 ≤1 各𝑖=1,…,𝑛に対して  𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =1 各j=1,…,𝑚 に対して  𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤1 となるような 𝑥 𝑖𝑗 を求める問題になる 解が存在するならば整数解も存在 (すべてのiとjに対して𝑥 𝑖𝑗 =0 𝑜𝑟 1) よって 各ジョブを1人の従業員に割り当て、かつどの従業員も2個以上ジョブが割り当てられないように割り当てることと等価 グラフ的には、すべてのジョブをカバーするマッチングを求めればよい ジョブ 従業員

1.4 ソーティング 問題1.1 ドリル穴あけ問題(Drilling Problem) 1.4 ソーティング 問題1.1 ドリル穴あけ問題(Drilling Problem) インスタンス: 平面上のn個の点  𝑝 1 ,…, 𝑝 𝑛 ∈ 𝑅 𝑛 タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛 もし、直線上にn個の点があったら…   端から順に穴をあければよい つまり… 与えられたn個の点を座標順に並び替えればよい

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 8,2,1,5 6,4,3,7 分割 8,2 1,5 6,4 3,7 8 2 1 5 6 4 3 7

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 6,4,3,7 2,8 1,5 4,6 3,7 統治 8 2 1 5 6 4 3 7

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1 6,4,3,7 2,8 5 4,6 3,7 統治 8 2 1 5 6 4 3 7

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2 6,4,3,7 8 5 4,6 3,7 統治 8 2 1 5 6 4 3 7

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2,5 6,4,3,7 8 4,6 3,7 統治 8 2 1 5 6 4 3 7

1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm) 入力:   n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力:   すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2,5,8 6,4,3,7 計算時間は𝑂 𝑛𝑙𝑜𝑔𝑛 4,6 3,7 統治 8 2 1 5 6 4 3 7

第2章 グラフ 2.1 基礎的な定義 2.2 木、閉路、カット 2.3 連結性 2.4 オイラーグラフと2部グラフ 2.5 平面性 2.6 平面的双対性

2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 Vの要素: 頂点 Eの要素: 辺

2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 Ψ 𝑒 = Ψ 𝑒′ となる2つの辺は並列である 並列辺をもたないグラフは単純である

2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 単純グラフについては𝐺= 𝑉 𝐺 ,𝐸 𝐺

2.1 基礎的な定義 有向グラフGに対する無向基礎グラフG’ 辺の向きをなくす G G’

2.1 基礎的な定義 𝐺= 𝑉 𝐺 ,𝐸 𝐺 に対する部分グラフ𝐻= 𝑉 𝐻 ,𝐸 𝐻 𝑉 𝐻 ⊆𝑉 𝐺 かつ𝐸 𝐻 ⊆𝐸 𝐺 𝐺= 𝑉 𝐺 ,𝐸 𝐺 に対する部分グラフ𝐻= 𝑉 𝐻 ,𝐸 𝐻 𝑉 𝐻 ⊆𝑉 𝐺 かつ𝐸 𝐻 ⊆𝐸 𝐺 𝐸 𝐻 = 𝑥,𝑦 ∈𝐸 𝐺 :𝑥,𝑦∈𝑉 𝐻 を満たすときHはGの誘導部分グラフ(𝐻=𝐺 𝑉 𝐻 と書くこともある) 上のHは誘導部分グラフではない 1 1 2 2 4 4 3 G H

2.1 基礎的な定義 𝑉 𝐻 =𝑉 𝐺 のとき、Hは全点であるという 𝑣∈𝑉 𝐺 のとき、 𝑉 𝐺 ∖ 𝑣 で誘導されるGの部分グラフを 𝐺 −𝑣 と表記する 𝑒∈𝐸 𝐺 のとき、 𝐺 −𝑒 を 𝐺 −𝑒 ≔ 𝑉 𝐺 ,𝐸 𝐺 ∖ 𝑒 と表記する 1 1 2 2 4 4 3 3 G H

2.1 基礎的な定義 2つのグラフG,Hに対して、G+Hは = + 𝑉 𝐺+𝐻 =𝑉 𝐺 ∪𝑉 𝐻 𝐸 𝐺+𝐻 は𝐸 𝐺 と𝐸 𝐻 の直和 4 4 5 3 5 3

2.1 基礎的な定義 2つの無向グラフGとHに対して、(有向も同様) 全単射 Φ 𝑉 :𝑉 𝐺 →𝑉 𝐻 と Φ 𝐸 :𝐸 𝐺 →𝐸 𝐻 が 2.1 基礎的な定義 2つの無向グラフGとHに対して、(有向も同様) 全単射 Φ 𝑉 :𝑉 𝐺 →𝑉 𝐻 と Φ 𝐸 :𝐸 𝐺 →𝐸 𝐻 が  存在して、すべての 𝑣,𝑤 ∈𝐸 𝐺 で Φ 𝐸 𝑣,𝑤 = Φ 𝑉 𝑣,𝑤 , Φ 𝑉 𝑣,𝑤  となるとき、GとHは同形であるという 1 2 a b 1→a 2→b 3→f 4→d 5→e 6→c 6 3 f c e d 5 4

2.1 基礎的な定義 無向グラフGと𝑋⊆𝑉 𝐺 に対して、Xを縮約するとは… Xのすべての点とG[X]のすべての辺を削除 新しい点xを追加 2.1 基礎的な定義 無向グラフGと𝑋⊆𝑉 𝐺 に対して、Xを縮約するとは… Xのすべての点とG[X]のすべての辺を削除 新しい点xを追加 𝑣∈𝑋,𝑤∉𝑋となる各辺 𝑣,𝑤 を辺 𝑥,𝑤 で置き換え 1 x 2 2 4 3 3 G/Xと書くことも X={1,4}

2.1 基礎的な定義 グラフGと𝑋,𝑌⊆𝑉 𝐺 に対して、 2.1 基礎的な定義 グラフGと𝑋,𝑌⊆𝑉 𝐺 に対して、 無向グラフ𝐸 𝑋,𝑌 ≔ 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 有向グラフ 𝐸 + 𝑋,𝑌 ≔ 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 1 2 Y X 4 3 𝐸 𝑋,𝑌 = 1,2

2.1 基礎的な定義 X 無向グラフGと𝑋⊆𝑉 𝐺 に対して、 𝛿 𝑋 ≔𝐸 𝑋,𝑉 𝐺 ∖𝑋 として、 Γ 𝑋 ≔ 𝑣∈𝑉 𝐺 ∖𝑋:𝐸 𝑋, 𝑣 ≠𝜙 をXの隣接頂点集合という

2.1 基礎的な定義 有向グラフGと𝑋⊆𝑉 𝐺 に対して、 𝛿 + 𝑋 ≔ 𝐸 + 𝑋,𝑉 𝐺 ∖𝑋 𝛿 − 𝑋 ≔ 𝛿 + 𝑉 𝐺 ∖𝑋 𝛿 𝑋 ≔ 𝛿 + 𝑋 ⋃ 𝛿 − 𝑋 と定義する 𝛿 + 𝑣 : 出次数 𝛿 − 𝑣 : 入次数

2.1 基礎的な定義 k-正則グラフ すべての点の次数がkであるグラフ

2.1 基礎的な定義 グラフの次数に関する性質 すべての点の次数の和は枝の数の倍 奇数次数の頂点の数は偶数 入次数の和=出次数の和

2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) (b) 2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 (b)   𝛿 − 𝑋 + 𝛿 − 𝑌 = 𝛿 − 𝑋⋂𝑌 + 𝛿 − 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 証明 対称性より片方だけ証明すればよい。(a)を証明する

2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 証明 2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 証明 𝑍=𝑉 𝐺 ∖ 𝑋⋃𝑌 とする 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝐸 + 𝑋∪𝑌,𝑍 + 𝐸 + 𝑋∩𝑌,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝛿 + 𝑋∪𝑌 + 𝛿 + 𝑋∩𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋

= 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌 証明 𝑍=𝑉 𝐺 ∖ 𝑋⋃𝑌 とする 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝐸 + 𝑋∪𝑌,𝑍 + 𝐸 + 𝑋∩𝑌,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝛿 + 𝑋∪𝑌 + 𝛿 + 𝑋∩𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 X Y

2.1 基礎的な定義 補題2.1(2) 無向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(c),(d)が成立 (c) (d) 2.1 基礎的な定義 補題2.1(2) 無向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(c),(d)が成立 (c) 𝛿 𝑋 + 𝛿 𝑌 = 𝛿 𝑋⋂𝑌 + 𝛿 𝑋⋃𝑌 +2 𝐸 𝑋,𝑌 (d) Γ 𝑋 + Γ 𝑌 ≥ Γ 𝑋⋂𝑌 + Γ 𝑋⋃𝑌 証明 Γ 𝑋 + Γ 𝑌 = Γ 𝑋∪𝑌 + Γ 𝑋 ∩Γ 𝑌 + Γ 𝑋 ∩𝑌 + 𝑋∩Γ 𝑌 Γ 𝑋∩𝑌 ⊆Γ 𝑋 ∩Γ 𝑌 を用いると(d)は得られる

2.1 基礎的な定義 関数𝑓: 2 𝑈 →𝑅(U:有限集合、 2 𝑈 :Uのべき集合)は 2.1 基礎的な定義 関数𝑓: 2 𝑈 →𝑅(U:有限集合、  2 𝑈 :Uのべき集合)は すべての𝑋,𝑌⊆𝑈で𝑓 𝑋∩𝑌 +𝑓 𝑋∪𝑌 ≤𝑓 𝑋 +𝑓 𝑌 ならば劣モジュラー 𝛿 + , 𝛿 − , 𝛿 , Γ が劣モジュラーである(補題2.1より)ことは 後で用いられる

2.1 基礎的な定義 完全グラフ: 任意の頂点間に枝が存在 Gの補グラフH: 無向グラフGに対してG+Hが完全グラフとなるようなH 2.1 基礎的な定義 完全グラフ: 任意の頂点間に枝が存在 Gの補グラフH: 無向グラフGに対してG+Hが完全グラフとなるようなH Gのマッチング: 無向グラフGの頂点を共有しない辺の集合 Gの点カバーS: 点集合𝑆⊆𝑉 𝐺 に対して、Gのどの辺も少なくともSの1点と隣接 Gの安定集合S: Sのどの2点もGで隣接していない GのクリークS: Sのどの2点もGで隣接 Gの辺カバーF: 辺集合𝐹⊆𝐸 𝐺 に対して、Gのどの点も少なくともFの1辺と接続

2.1 基礎的な定義 命題2.2 グラフGと𝑋⊆𝑉 𝐺 に対して、以下の命題(a)-(c)は互いに等価である (a) XはGの点カバーである 2.1 基礎的な定義 命題2.2 グラフGと𝑋⊆𝑉 𝐺 に対して、以下の命題(a)-(c)は互いに等価である (a) XはGの点カバーである (b) 𝑉 𝐺 ∖𝑋はGの安定集合である (c) 𝑉 𝐺 ∖𝑋はGの補グラフのクリークである

2.1 基礎的な定義 線グラフ 点集合𝐸 𝐺 辺集合𝐹= 𝑒 1 , 𝑒 2 : 𝑒 1 , 𝑒 2 ∈𝐸 𝐺 , 𝑒 1 ∩ 𝑒 2 =1 辺集合𝐹= 𝑒 1 , 𝑒 2 : 𝑒 1 , 𝑒 2 ∈𝐸 𝐺 , 𝑒 1 ∩ 𝑒 2 =1 a a b b c c

2.1 基礎的な定義 辺の重複を許すウォーク 3 c 2 d b 4 1 e f a 5 g 7 6 同じ辺通らないものをウォーク 2.1 基礎的な定義 辺の重複を許すウォーク 3 c 2 d b 4 1 e f a 5 g 7 6 同じ辺通らないものをウォーク 始点と終点が同じものを閉ウォーク

2.1 基礎的な定義 パス 3 c 2 d b 4 1 e f a 5 g 7 6 同じ頂点をとおらないものをパス 全点パスをハミルトンパス

2.1 基礎的な定義 閉路 3 c 2 d b 4 1 e f a 5 g 7 6 閉ウォークで同じ頂点をとおらないものを閉路 2.1 基礎的な定義 閉路 3 c 2 d b 4 1 e f a 5 g 7 6 閉ウォークで同じ頂点をとおらないものを閉路 全点閉路をハミルトン閉路

2.2 木、閉路、カット G: 無向グラフ 連結: Gに存在する任意の頂点間にパスが存在 する(そうでないとき非連結) 2.2 木、閉路、カット G: 無向グラフ 連結: Gに存在する任意の頂点間にパスが存在 する(そうでないとき非連結) Gの極大な連結部分グラフをGの連結成分 点集合Xで誘導される部分グラフが連結であるとき、Xは連結であるという

2.2 木、閉路、カット 関節点v: 𝐺 −𝑣 の連結成分がGより多くなるよう な点v 連結成分 連結成分 関節点

2.2 木、閉路、カット 橋e: 𝐺 −𝑒 の連結成分がGより多くなるよう な辺e 連結成分 連結成分 橋

2.2 木、閉路、カット 森: 閉路をもたない無向グラフ 木: 連結な森 葉: 木で次数1の点 スターグラフ: 葉でない点が高々1点である木

2.2 木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である (b)Gを有向グラフとし、𝑟∈𝑉 𝐺 とする。 すべての点𝑣∈𝑉 𝐺 に対してr-v-パスが存在するとき、 そしてそのときのみ、 𝑟∈𝑋となるすべての𝑋⊂𝑉 𝐺 に 対して 𝛿 + 𝑋 ≠𝜙である。 (a)だけ証明

2.2 木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である If exist X s.t.𝛿 𝑋 =𝜙… v r r-v-パスは存在しない。 よって非連結

2.2 木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である もし非連結ならば…あるr,vに対して、r-v-パスが存在しない  rから到達可能な点をRとすると、𝑟∈𝑅,𝑣∉𝑅かつ𝛿 𝑅 =𝜙が得られる

定理2.4の証明 a⇒g 端点のパスが一意でなければ閉路が存在 よって Gが木ならば任意の2点間に唯一のパスが存在

定理2.4の証明 g⇒e⇒dは命題2.3から得られる d⇒fは自明である f⇒b⇒c n点m辺p個の連結成分からなる森 n=m+p が成り立つことから得られる

定理2.4の証明 c⇒a Gからk本取り除いても連結性を保てたとする。 得られたグラフG’はm=n-1-k本の辺をもつ n=m+p=n-1-k+1より k=0 a⇒g⇒e⇒d⇒f⇒b⇒c⇒aが言えた

有向木 有向グラフが連結=無向基礎グラフが連結 根 有向木 有向木ではない

定理2.5の証明 (a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ (b)⇒(c) 根以外の点の入次数は1より、任意のvに対してr-v-パスが得られる(vからrまでの唯一のパスをたどれる) (d)⇒(e) 命題2.3から成立

定理2.5の証明 (a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ (b)⇒(c) 根以外の点の入次数は1より、任意のvに対してr-v-パスが得られる(vからrまでの唯一のパスをたどれる) (d)⇒(e) 命題2.3から成立

定理2.5の証明 (f)⇒(g)⇒(a) 自明 (e)⇒(f) (e)の極小性からrの入次数は0 命題2.3よりすべてのvに対してr-v-パスが存在 あるvに対して2つのr-v-パスがあったとすると eをとってもどの点もrから到達可能。矛盾 (f)⇒(g)⇒(a) 自明 e

カット 𝜙≠𝑋⊂𝑉 𝐺 を用いて𝛿 𝑋 と書ける辺集合 有向の場合は 𝛿 + 𝑋 t s 頂点sとtを分離するカットをs-t-カット

無向パス 無向閉路 無向カット それぞれ、無向基礎グラフにおけるパス、閉路、カット

補題2.6 Gを有向グラフとし、𝑒∈𝐸 𝐺 とする。eは黒で彩色され、残りの各辺は赤、黒あるいは緑のいずれかで彩色されているとする。このとき、以下の(a)あるいは(b)のいずれかが成立し、両方同時に成立することはない。 (a) eを含み、赤と黒の辺だけからなる無向閉路で、黒い辺はすべて同一の向きをもつようなものが存在する。 (b) eを含み、緑と黒の辺からなる無向カットで、黒い辺はすべて同一の向きを持つようなものが存在する。

下のグラフは(a)を満たし、(b)を満たさない (a) eを含み、赤と黒の辺だけからなる無向閉路で、黒い辺はすべて同一の向きをもつようなものが存在する。 (b) eを含み、緑と黒の辺からなる無向カットで、黒い辺はすべて同一の向きを持つようなものが存在する。 下のグラフは(a)を満たし、(b)を満たさない e

yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達できる点にラベル付け xがラベル付けされたら(a)を満たす無向閉路を持つ y x e

yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達できる点にラベル付け xがラベル付けされなければラベル付けされた頂点集合が(b)を満たす無向カットを構成する y x e

(a)を満たす無向閉路と(b)を満たす無向カットに共通する辺は黒 y x e

有向グラフの強連結 有向グラフGは、すべての𝑠,𝑡∈𝑉 𝐺 に対してsからtのパスとtからsのパスがあるとき、強連結であるという。 有向グラフの極大な強連結部分グラフを強連結成分という。

系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる

系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる 命題2.3 (b)Gを有向グラフとし、𝑟∈𝑉 𝐺 とする。すべての点𝑣∈𝑉 𝐺 に対してr-v-パスが存在するとき、そしてそのときのみ、 𝑟∈𝑋となるすべて𝑋⊂𝑉 𝐺 に対して 𝛿 + 𝑋 ≠𝜙である。

系2.7(補題2.6の適用) 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる

系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる X 𝑟∈𝑉 𝐺 :任意の点 目標:各𝑣∈𝑉 𝐺 に対してr-v-パスが存在 正しくないと仮定 r

定義2.8 トポロジカル順序 Gを有向グラフとする。任意の辺 𝑣 𝑖 , 𝑣 𝑗 ∈𝐸 𝐺 に対して、i<jが成立するような点集合𝑉 𝐺 = 𝑣 1 ,…, 𝑣 𝑛 の順序をGのトポロジカル順序という。 1 3 2 5 6 4

命題2.9 有向グラフがトポロジカル順序を持つ ⇔ 無閉路(有向閉路を持たない)である 証明(⇒) 対偶は自明 (⇐)辺数に関する帰納法

辺𝑒∈𝐸 𝐺 を持つものとする。eはある有向カットに属する 帰納法の仮定から、それぞれの頂点集合から誘導されるグラフにはトポロジカル順序が存在

サイクル空間とコサイクル空間 有向グラフGの各無向閉路にベクトルを対応させる 無向閉路を形成する辺に1 or -1(符号は向きに対応) それ以外の辺に0 𝐶 1 1 2 𝜁 𝐶 1 = 1 −1 1 0 0 0 0 0 3 4 6 5 7 8

サイクル空間とコサイクル空間 有向グラフGの各無向閉路にベクトルを対応させる 無向閉路を形成する辺に1 or -1(符号は向きに対応) それ以外の辺に0 無向閉路に対応するベクトルの集合で生成されるベクトル空間の部分空間をサイクル空間という

サイクル空間とコサイクル空間 有向グラフGの各無向カットにベクトルを対応させる 無向カットを形成する辺に1 or -1(符号は向きに対応) それ以外の辺に0 𝐷 1 1 2 𝜁 𝐷 1 = 0 0 0 1 1 −1 1 0 3 4 6 5 7 8

サイクル空間とコサイクル空間 有向グラフGの各無向カットにベクトルを対応させる 無向カットを形成する辺に1 or -1(符号は向きに対応) それ以外の辺に0 無向カットに対応するベクトルの集合で生成されるベクトル空間の部分空間をコサイクル空間という

命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 任意の閉路Cと任意の無向カットDに対して、𝜁 𝐶 と𝜁 𝐷 のスカラー積が0になることを示す

命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 考慮するべき辺は共通する辺のみ (他の辺に対応するベクトルの成分はC,Dのどちらかにおいて0となる)

命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 無向カットを有向カットとしてもスカラー積の値に影響を与えない (有向カットの非零成分の符号はすべて一致すると考えても一般性を失わない)

命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 閉路を考えると、 Dに入る辺の数=Dから出る辺の数 つまり、ベクトルにおいて、 1となる成分の数=0となる成分の数

サイクル基底 コサイクル基底 無向閉路の集合は、対応するベクトルの集合がサイクル空間の基底となるとき、サイクル基底と呼ばれる 無向カットの集合は、対応するベクトルの集合がコサイクル空間の基底となるとき、コサイクル基底と呼ばれる。

基本閉路と基本カット Gをグラフ、Tを無向閉路を含まないGの極大な部分グラフとする 各𝑒∈𝐸 𝐺 ∖𝐸 𝑇 に対して、T+eに含まれる唯一の無向閉路をTに関するeの基本閉路という e

基本閉路と基本カット Gをグラフ、Tを無向閉路を含まないGの極大な部分グラフとする 各𝑒∈𝐸 𝑇 に対して、 𝛿 𝐺 𝑋 ∩𝐸 𝑇 = 𝑒 となる集合𝑋⊆𝑉 𝐺 が存在する。 𝛿 𝐺 𝑋 をTに関するeの基本カットという X e

定理2.11 Gを有向グラフ、Tを無向閉路を持たないGの極大な部分グラフとする。 Tに関する 𝐸 𝐺 ∖𝐸 𝑇 個の𝐸 𝐺 ∖𝐸 𝑇 の辺の基本閉路の集合はGのサイクル基底となる。 Tに関する 𝐸 𝑇 個の𝐸 𝑇 の辺の基本カットの集合はコサイクル基底となる。 各基本閉路は他の基本閉路に含まれない辺eを含むので、基本閉路に対応する 𝐸 𝐺 ∖𝐸 𝑇 個のベクトルは線形独立 基本カットに対応する 𝐸 𝑇 個のベクトルに対しても同様 2つのベクトル空間は互いに直交するので、次元の和は 𝐸 𝐺

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える 1 2 3

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える 1 2 3 𝐶 1

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える 𝐶 2 1 2 3 𝐶 1

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える 𝐶 2 1 2 3 𝐶 3 𝐶 1

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える もしTが有向木ならばFの任意の2要素は共通部分を持たないか、あるいは一方が他方に含まれるかである 1 2 3 𝐶 3 𝐶 2 𝐶 1

定義2.12 集合システム 空でない有限集合UとUの部分集合の族Fの対(U,F)は集合システムと呼ばれる。 任意の2つの集合X,Yに対して 𝑋∖𝑌,𝑌∖𝑋,𝑋⋂𝑌,𝑈∖ 𝑋⋃𝑌 のいずれかが空⇒クロスフリー (どのX,Yを見ても、一方が他方を含んでいる、共通する要素がない、すべての要素をカバーする、のいずれかを満たす) 𝑋∖𝑌,𝑌∖𝑋,𝑋⋂𝑌のいずれかが空⇒ラミナー (どのX,Yを見ても、一方が他方を含んでいる、共通する要素がない、のいずれかを満たす)

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える 𝐶 2 1 クロスフリー族 2 3 𝐶 3 𝐶 1

T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える もしTが有向木ならばFの任意の2要素は共通部分を持たないか、あるいは一方が他方に含まれるかである 1 ラミナー族 2 3 𝐶 3 𝐶 2 𝐶 1

定義から、 集合システム 𝑈,𝐹 がクロスフリーであることと、任意の𝑟∈𝑋に対して、 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 がラミナー族であることは等価であることが得られる

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 r 𝐶 2 1 クロスフリー族 2 3 𝐶 3 𝐶 1

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 r 𝐶 2 1 2 3 𝐶 3 𝐶 1

定義2.13 Tを無向基礎グラフが木となる有向グラフとする。 Uを有限集合とし、𝜑:𝑈→𝑉 𝑇 とする。 𝑒= 𝑥,𝑦 に対して、 𝑆 𝑒 ≔ 𝑠∈𝑈: 𝜑 𝑠 と𝑦は𝑇−𝑒の同じ連結成分に属する と定義して、 𝐹≔ 𝑆 𝑒 :𝑒∈𝐸 𝑇 とする。このとき、 𝑇,𝜑 を 𝑈,𝐹 の木表現という。

クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現 d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現 d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現 d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 の4通りが考えられる

𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 w v x y 𝑆 𝑒 ∩ 𝑆 𝑓 =∅ e f 𝑆 𝑒 𝑆 𝑓

𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 w v y x 𝑆 𝑒 ⊆ 𝑆 𝑓 (c)の場合は 𝑆 𝑓 ⊆ 𝑆 𝑒 e f 𝑆 𝑒 𝑆 𝑓

𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 v w y x 𝑆 𝑒 ∪ 𝑆 𝑓 =𝑈 Tが有向木ならばこのパターンは起こりえない。 その場合はラミナー族 e f 𝑆 𝑓 𝑆 𝑒

命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

F: ラミナー族 𝑉 𝑇 ≔𝐹∪ 𝑟 𝐸 ′ ≔ 𝑋,𝑌 ∈𝐹×𝐹:𝑋⊃𝑌≠∅かつ𝑋⊃𝑍⊃𝑌となる𝑍が存在しない 𝐸 ′ ≔ 𝑋,𝑌 ∈𝐹×𝐹:𝑋⊃𝑌≠∅かつ𝑋⊃𝑍⊃𝑌となる𝑍が存在しない 𝐸 𝑇 ≔𝐸′∪ 𝑟,𝑋 :𝑋は𝐹の極大要素 Fが空集合を含むならば、任意の極小集合Xに(X,Φ)を追加 各x∈𝑈に対して、xを含む極小集合Xを用いて 𝜑 𝑥 =𝑋 xを含む集合がないときは 𝜑 𝑥 =𝑟 として𝜑を定義 Tはrを根とする有向木 r X Y

F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 z

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

系2.15 Uの異なる部分集合の… ラミナー族は高々2|U|個の要素しか含まない クロスフリー族は高々4|U|-2個の要素しか含まない 非空真部分集合のラミナー族F 命題2.14における構成法では… 異なる部分集合の数=枝の数=頂点数-1 各頂点に対して 出次数が2以上である or ラベル付けされる ラベル付けされる頂点の数は高々|U|個 出次数が2以上となるのは高々 𝐸 𝑇 2 𝐸 𝑇 +1= 𝑉 𝑇 ≤ 𝑈 + 𝐸 𝑇 2 𝐹 = 𝐸 𝑇 ≤2 𝑈 −2 空集合とUを合わせると…

系2.15 Uの異なる部分集合の… ラミナー族は高々2|U|個の要素しか含まない クロスフリー族は高々4|U|-2個の要素しか含まない 非空真部分集合のクロスフリー族F Fの変換により得られるラミナー族F’ 𝐹 ≤2 𝐹 ′ ≤4 𝑈 −4 空集合とUを合わせると…