| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-01-18 12:45 グラフの決定セットの判定法に関する検証 ○田中香貴・後藤隆文・中田 充（山口大）・Chiranut Sa-ngiamsak（Khon Kaen Univ.）・葛 崎偉（山口大）  MSS2017-51 SS2017-38 |
|
| 抄録 | （和） | グラフ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 / / | |
| 文献情報 | 信学技報, vol. 117, no. 380, MSS2017-51, pp. 25-30, 2018年1月. | |
| 資料番号 | MSS2017-51 | |
| 発行日 | 2018-01-11 (MSS, SS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | MSS2017-51 SS2017-38 |
|
| 研究会情報 | |
| 研究会 | SS MSS |
| 開催期間 | 2018-01-18 - 2018-01-19 |
| 開催地（和） | 広島市立大学サテライトキャンパス |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2018-01-SS-MSS |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフの決定セットの判定法に関する検証 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-01-18 12:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | MSS2017-51, SS2017-38 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.380(MSS), no.381(SS) |
| ページ範囲 | pp.25-30 |
| ページ数 | 6 |
| 発行日 | 2018-01-11 (MSS, SS) |
[研究会発表申込システムのトップページに戻る]