|
所属組織 |
大学院環境情報研究院 社会環境と情報部門 |
|
職名 |
准教授 |
|
研究キーワード |
グラフ理論、離散数学 |
|
ホームページ |
|
|
関連SDGs |
|
小関 健太 (オゼキ ケンタ)
OZEKI Kenta
|
|
ORCID
学内所属歴 【 表示 ／ 非表示 】
-
2019年4月-現在
専任 横浜国立大学 大学院環境情報研究院 社会環境と情報部門 准教授
-
2017年2月-2019年3月
専任 横浜国立大学 大学院環境情報研究院 社会環境と情報部門 特任教員（准教授）
-
2021年4月-現在
併任 横浜国立大学 大学院先進実践学環 准教授
-
2019年4月-現在
併任 横浜国立大学 大学院環境情報学府 情報メディア環境学専攻 准教授
-
2019年4月-現在
併任 横浜国立大学 大学院環境情報学府 情報環境専攻 准教授
著書 【 表示 ／ 非表示 】
-
IT Text 離散数学
松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男（ 担当： 共著 , 範囲: 4章 グラフと木）
オーム社 2010年10月
記述言語：日本語 著書種別：教科書・概説・概論
情報系を学ぶ学生にとっての基礎数学として、わかりやすい言葉と高校までに学んだ範囲で離散数学を基礎からていねいに解説した教科書。システム開発者や他分野の方にも基礎概念の整理に役立つ一冊。
論文 【 表示 ／ 非表示 】
-
A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs
MATSUI Yasuko, OZEKI Kenta
IEICE Transactions on Information and Systems 104 ( 3 ) 389 - 391 2021年
記述言語：英語 掲載種別：研究論文（学術雑誌） 出版者・発行元：一般社団法人 電子情報通信学会 共著
<p>This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with <i>n</i> vertices in O(<i>n</i>) time, and another one generates each <i>k</i>-edge-connected spanning subgraph of a general graph with <i>m</i> edges in O(<i>mT</i>) time, where <i>T</i> is the running time to check the <i>k</i>-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in <i>O</i>(<i>n</i><sup>2</sup>) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.</p>
-
Thomassen's conjecture for line graphs of 3-hypergraphs
Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr
DISCRETE MATHEMATICS 343 ( 6 ) 2020年6月 [査読有り]
記述言語：英語 掲載種別：研究論文（学術雑誌） 共著
-
Long Paths in Bipartite Graphs and Path-Bistar Bipartite Ramsey Numbers
Furuya Michitaka, Maezawa Shun-ichi, Ozeki Kenta
GRAPHS AND COMBINATORICS 36 ( 1 ) 167 - 176 2020年1月 [査読有り]
記述言語：英語 掲載種別：研究論文（学術雑誌） 共著
-
A degree sum condition on the order, the connectivity and the independence number for hamiltonicity
Chiba Shuya, Furuya Michitaka, Ozeki Kenta, Tsugaki Masao, Yamashita Tomoki
ELECTRONIC JOURNAL OF COMBINATORICS 26 ( 4 ) 2019年12月 [査読有り]
記述言語：英語 掲載種別：研究論文（学術雑誌） 共著
-
On the minimum leaf number of cubic graphs
Goedgebeur Jan, Ozeki Kenta, Van Cleemput Nico, Wiener Gabor
DISCRETE MATHEMATICS 342 ( 11 ) 3000 - 3005 2019年11月 [査読有り]
記述言語：英語 掲載種別：研究論文（学術雑誌） 共著
総説・解説記事等 【 表示 ／ 非表示 】
-
エレガントな解答を求む 2021年4月号出題 2
小関 健太
数学セミナー 2021年4月 [依頼有り]
記述言語：日本語 掲載種別：記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） 出版者・発行元：日本評論社 単著
図1 はあるホテルの見取り図で，斜線部が部屋で白
い部分が廊下を表している．すべての廊下には電灯が
ついており，丸数字が表すスイッチにより隣接する廊
下の電灯のon–off を切り替えられる．ただし1 つの
スイッチは連動しており，例えば1 のスイッチを押す
と，図2 のように，1 と2 の間の廊下，1 と3 の間の
廊下，1 と4 の間の廊下の3 つの電灯のon–off が同時
に変わってしまう．(他の廊下の電灯のon–off は変わ
らない)
(1) 以下のどの状況のときに全部の廊下の電灯をoff に
できるでしょうか？
(A) 全部の電灯がon．
(B) 1 と2 の間の廊下と5 と6 の間の廊下だけ
電灯がoff，他はon，
(C) 1 と2 の間の廊下と4 と5 の間の廊下だけ
電灯がoff，他はon，
(2) 他の状態からはじめたときや別のホテルでも考え
てみてください．すべてをoff にできるための必
要十分条件を，すっきりした形で言えないでしょ
うか？
(1) のみの解答でも構いませんので，ぜひ考えてみて
ください． -
エレガントな解答を求む 2020年4月号出題 2
小関 健太,阿部 敏生
数学セミナー 2020年4月 [依頼有り]
記述言語：日本語 掲載種別：記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） 出版者・発行元：日本評論社 共著
平面上にある点の集合 S に対し，次の 3 つのルールで何本かの線を引くことを考える．
各線は S のある点からスタートし，S の点をちょうど 1 つ通過し S の点で終わる．
線同士は S の点以外で交差しない（各線は自分自身とも S の点以外では交差できない）．
S の各点で線の出入りは合計 3 回まで可能である．
例えば図 1 のように進行すると，3 本の線を引いた時点ですべての点で線の出入りがちょうど 3 回行われ，これ以上線が引けなくなる．特に，各線はスタートの点を通過したり，S の同じ点に戻ってきたりしてもよいことに注意されたい．一方で図 2 のように進行すると，線を 2 本引いた時点で線が引けなくなってしまう．
(1) S が 6 点のとき，最大で何本の線が引けるか ?
(2) S が 6 点のとき，それ以上線が引けなくなるまでに少なくとも何本の線を引く必要があるか ?
余裕のある方は，S が n 点のときも考えてみてください． -
ネットワークとグラフ理論
小関 健太
数理科学 2020年2月 [依頼有り]
記述言語：日本語 掲載種別：記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） 出版者・発行元：株式会社サイエンス社 単著
-
すごい反例 組合せ論・グラフ理論
小関 健太
日本評論社 2019年11月 [依頼有り]
記述言語：日本語 掲載種別：記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） 単著
-
エレガントな解答を求む 2019年4月号出題 1
小関 健太
数学セミナー 2019年4月
記述言語：日本語 掲載種別：記事・総説・解説・論説等（大学・研究所紀要） 出版者・発行元：日本評論社 単著
正三角形が並んでいる図形をn段の三角格子とよぶ．ただし，nは外側の各辺に並んでいる正三角形の数である．
三角格子の頂点を何色かで塗り，3 頂点がすべて同じ色の正三角形(単色三角形とよぶ) を見つけたい．ただし，ここでいう単色三角形はいくつかの小三角形を組合わせたもののみであり，向きは上向きでも下向きでも構わないとする．
(1) 4段の三角格子は，頂点をどのように2色で塗っても単色三角形を持つことを示せ．
(2) 5段の三角格子の3色での頂点の塗り方で，単色三角形を持たないものを一つ示せ．
(3) 10; 000段の三角格子は頂点をどのように3色で塗っても単色三角形を持つことを示せ．
科研費（文科省・学振）獲得実績 【 表示 ／ 非表示 】
-
トポロジー的な性質を持つハミルトン閉路を利用した， 閉曲面上のグラフの頂点彩色 研究課題
2018年4月 - 2021年3月
科学研究費補助金 基盤研究(C)
代表者：小関 健太
資金種別：競争的資金
本研究の目的は，閉曲面上のグラフについて，ハミルトン閉路を利用した新しい彩色の手法を提案することである
その他競争的資金獲得・外部資金受入状況 【 表示 ／ 非表示 】
-
グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決
2014年11月 - 2015年11月
公益財団法人 住 友 財 団 住友財団 基礎科学研究助成
代表者：小関 健太
グラフとは，頂点集合と辺集合（頂点集合の二元部分集合族）からなる構造として定義される．グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び，ちょうど一度ずつ通る道をハミルトン道と呼ぶ．「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は，組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため，グラフ理論の中でも非常に多くの研究がなされている．
ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると，この問題は四色定理とも関わりを持つこともあり，多くの研究が行われている．本研究もこの流れに沿うものである．閉曲面上のグラフのハミルトン性については，表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた．例えば，1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している．なお，グラフが，``任意の 2頂点に対し，それらを結ぶハミルトン道が存在する'' という性質を満たすとき，ハミルトン連結であるという．
このように，この分野についていくつかの結果が示されているが，未解決な部分も存在する．特に，次の命題は，40年以上未解決であり，グラフ理論全体の中でも重要なものとなっている．この予想の完全解決が研究の目的である．
予想 (Grunbaum `70, Nash-Williams `73)
トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ．
研究発表 【 表示 ／ 非表示 】
-
グラフの出次数制約のある向き付け
小関健太
第31回 位相幾何学的グラフ理論研究集会
開催年月日： 2019年11月
記述言語：英語 会議種別：口頭発表（一般）
-
An orientation of graphs with out-degree constraint
Kenta Ozeki [招待有り]
The 2nd East Asia Workshop on Extremal and Structural Graph Theory
開催年月日： 2019年11月
記述言語：英語 会議種別：口頭発表（招待・特別）
-
Spanning trees with few leaves in graphs on surfaces
Kenta Ozeki [招待有り]
International Conference on Graph Theory, Combinatorics and Applications
開催年月日： 2019年6月
記述言語：英語 会議種別：口頭発表（一般）
-
Spanning trees with few number of leaves in 4-connected graphs on higher genus surface
Kenta Ozeki
Structural Graph Theory and Graph Colorings
開催年月日： 2019年4月
記述言語：英語 会議種別：口頭発表（一般）
-
Spanning trees with few leaves in graphs on surfaces
Kenta Ozeki
Joint Mathematics Meetings (Baltimore) American Mathematical Society, Mathematical Association of America
開催年月日： 2019年1月
記述言語：英語 会議種別：口頭発表（一般）
開催地：Baltimore
学会誌・論文誌編集等 【 表示 ／ 非表示 】
-
Journal of Algebra Combinatorics Discrete Structures and Applications
Editorial Board
2014年5月-現在 -
Theory and Applications of Graphs
Editorial Board
2014年1月-現在 -
Graphs and Combinatorics
Managing Editor
1985年1月-現在
担当授業科目（学内） 【 表示 ／ 非表示 】
-
2021年度 数理情報特論Ⅱ
大学院先進実践学環
-
2021年度 数理情報特論Ⅰ
大学院先進実践学環
-
2021年度 情報数学特論Ⅰ
大学院先進実践学環
-
2021年度 IT技法通論Ⅱ
大学院先進実践学環
-
2021年度 グラフアルゴリズム論演習
大学院環境情報学府