| 講演名 | 2018-01-18 グラフの決定セットの判定法に関する検証 田中 香貴(山口大), 後藤 隆文(山口大), 中田 充(山口大), Chiranut Sa-ngiamsak(Khon Kaen Univ.), 葛 崎偉(山口大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフG=(V,E)の自己同型写像とは，隣接関係を保つ節点集合V自身への一対一対応である．Gの自己同型写像の全集合Aut(G)におけるS⊆Vの対応づけを決めた時，Aut(G)においてT⊆V-Sの対応づけが決まるならば，TはSにより決定されるという．T=V-SのときSをGの決定セットという．また，決定セットのいかなる真部分集合も決定セットとならないとき，その決定セットを極小決定セットと呼ぶ．さらに，要素数が最小の決定セットをカーネルセットと呼ぶ．本論文では，現在提案されている与えられた節点集合が決定セットであるか判定するアルゴリズムの厳密さの検証を行う．まずは，決定セットに関わる定義を示す．次に，決定セットに関わる性質および判定方法を示し，その判定方法に対する実験の結果を示す．最後に，対称節点集合に関する定義を議論する． |
| 抄録(英) | An automorphism of graph G=(V,E) is such a one-to-one correspondence from the vertex set V to itself that adjacency of the vertices are maintained. In general, there are multiple automorphisms for a graph. When a one-to-one correspondence of a subset S of V is decided and meanwhile the adjacency relationship of S is maintained, S is called determiner set of G if the correspondence of all the vertices in V-S is uniquely determined.Also, if no any proper subset of a determiner set S is a determiner set, S is called minimum determiner set. Furthermore, a determiner set S with the smallest number of elements is called a kernel set. In this paper, we verify the restriction of the algorithm to determine whether a given node set is a determiner set. First, definitions and properties related to determiner sets are given. Then our method of judging determiner sets as well as its experimental results are explained. Finally, the discussion is done for the definitions related to symmetric nodes. |
| キーワード(和) | グラフ / 自己同型写像 / 決定セット / 極小決定セット / カーネルセット / 対称節点 |
| キーワード(英) | graph / automorphism / determiner set / minimum determiner set / kernel set / symmetric node |
| 資料番号 | MSS2017-51,SS2017-38 |
| 発行日 | 2018-01-11 (MSS, SS) |
| 研究会情報 | |
| 研究会 | SS / MSS |
|---|---|
| 開催期間 | 2018/1/18(から2日開催) |
| 開催地（和） | 広島市立大学サテライトキャンパス |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 緒方 和博(北陸先端大) / 名嘉村 盛和(琉球大) |
| 委員長氏名（英） | Kazuhiro Ogata(JAIST) / Morikazu Nakamura(Univ. of Ryukyus) |
| 副委員長氏名（和） | 中田 明夫(広島市大) / 髙井 重昌(阪大) |
| 副委員長氏名（英） | Akio Nakata(Hiroshima City Univ.) / Shigemasa Takai(Osaka Univ.) |
| 幹事氏名（和） | 小林 隆志(東工大) / 肥後 芳樹(阪大) / 豊嶋 伊知郎(東芝エネルギーシステムズ) / 金澤 尚史(阪大) |
| 幹事氏名（英） | Takashi Kobayashi(Tokyo Inst. of Tech.) / Yoshiki Higo(Osaka Univ.) / Ichiro Toyoshima(Toshiba) / Takahumi Kanazawa(Osaka Univ.) |
| 幹事補佐氏名（和） | 島 和之(広島市大) / 金城 秀樹(沖縄大) |
| 幹事補佐氏名（英） | Kazuyuki Shima(Hiroshima City Univ.) / Hideki Kinjo(Okinawa Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Software Science / Technical Committee on Mathematical Systems Science and its applications |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフの決定セットの判定法に関する検証 |
| サブタイトル（和） | |
| タイトル（英） | Verification of an Approach to Find Determiner Set of Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 自己同型写像 / automorphism |
| キーワード(3)（和/英） | 決定セット / determiner set |
| キーワード(4)（和/英） | 極小決定セット / minimum determiner set |
| キーワード(5)（和/英） | カーネルセット / kernel set |
| キーワード(6)（和/英） | 対称節点 / symmetric node |
| 第 1 著者 氏名（和/英） | 田中 香貴 / Koki Tanaka |
| 第 1 著者 所属（和/英） | 山口大学(略称：山口大) Yamaguchi University(略称：Yamaguchi Univ.) |
| 第 2 著者 氏名（和/英） | 後藤 隆文 / Takafumi Goto |
| 第 2 著者 所属（和/英） | 山口大学(略称：山口大) Yamaguchi University(略称：Yamaguchi Univ.) |
| 第 3 著者 氏名（和/英） | 中田 充 / Mituru Nakata |
| 第 3 著者 所属（和/英） | 山口大学(略称：山口大) Yamaguchi University(略称：Yamaguchi Univ.) |
| 第 4 著者 氏名（和/英） | Chiranut Sa-ngiamsak / Chiranut Sa-ngiamsak |
| 第 4 著者 所属（和/英） | Khon Kaen University(略称：Khon Kaen Univ.) Khon Kaen University(略称：Khon Kaen Univ.) |
| 第 5 著者 氏名（和/英） | 葛 崎偉 / Qi-Wei Ge |
| 第 5 著者 所属（和/英） | 山口大学(略称：山口大) Yamaguchi University(略称：Yamaguchi Univ.) |
| 発表年月日 | 2018-01-18 |
| 資料番号 | MSS2017-51,SS2017-38 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | MSS-380,SS-381 |
| ページ範囲 | pp.25-30(MSS), pp.25-30(SS), |
| ページ数 | 6 |
| 発行日 | 2018-01-11 (MSS, SS) |