| 講演名 | 2004-06-25 関数に基づく集合分割とラインダイグラフ 河合 博之, 柴田 幸夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | fとgを集合Eから集合Fの間の二つの写像とし,すべてのEの要素xに対してf(x)≠g(x)を満足するものとする.Sahili[7]は集合Fの任意の要素zに対して,f^<-1>(z)が高々n個の要素を持つならば集合Eはf(E_i)∩g(E_i)=0,1≦i≦2n+1となるような部分集合への分割E_1,E_2,...,E_<2n+1>が可能であることを示した.この結果は二つの集合と二つ関数との関係をダイグラフとラインダイグラフとの関係に置換えることにより証明された.Sahili[7]はまた次の問題も提起している:分割数2n+1は最適な界であるだろうか?本報告では,ラインダイグラフの彩色数の結果を利用しこの上界2n+1をmin[numerical formula]へと改善する.また,2階ラインダイグラフの観点から二つの関数を三つの関数へ拡張することを試みる. |
| 抄録(英) | Let f and g be two maps from a set E into a set F such that f(x)≠g(x) for all x in E. Sahili[7] has shown that the relationship obtained from the maps and the sets is represented by a digraph and its line digraph. It was shown that for any element z∈F_1, if either f^<-1>(z) or g^<-1>(z) has at most n elements, then E can be partitioned into subsets E_1,E_2,...,E_<2n+1> such that f(E_i)∩g(E_i)=0, 1≦i≦2n+1 Sahili[7] also posed a question: Is 2n+1 the best possible bound?In this report, we answer this problem, that is, we improve 2n+1 to min[numerical formula] using the result of an arc-coloring of digraphs. We also investigate extended version to three maps. |
| キーワード(和) | 集合分割 / グラフ辺彩色 / ラインダイグラフ |
| キーワード(英) | partition / arc-coloring / line digraph |
| 資料番号 | COMP2004-18 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 関数に基づく集合分割とラインダイグラフ |
| サブタイトル（和） | |
| タイトル（英） | Partitions, Functions and Line digraphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 集合分割 / partition |
| キーワード(2)（和/英） | グラフ辺彩色 / arc-coloring |
| キーワード(3)（和/英） | ラインダイグラフ / line digraph |
| 第 1 著者 氏名（和/英） | 河合 博之 / Hiroyuki KAWAI |
| 第 1 著者 所属（和/英） | 群馬大学サテライトベンチャービジネスラボラトリー Satellite Venture Business Laboratory, Gunma University |
| 第 2 著者 氏名（和/英） | 柴田 幸夫 / Yukio SHIBATA |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 発表年月日 | 2004-06-25 |
| 資料番号 | COMP2004-18 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 147 |
| ページ範囲 | pp.- |
| ページ数 | 3 |
| 発行日 | |