小関 健太 (オゼキ ケンタ)

OZEKI Kenta

所属組織

大学院環境情報研究院 社会環境と情報部門

職名

准教授

研究キーワード

グラフ理論、離散数学

ホームページ

http://tgt.ynu.ac.jp/ozeki/

関連SDGs




ORCID  https://orcid.org/0000-0003-3118-0086

学歴 【 表示 / 非表示

  •  
    -
    2009年3月

    慶應義塾大学   理工学研究科   基礎理工学専攻   博士課程   修了

学位 【 表示 / 非表示

  • 博士(理学) - 慶應義塾大学

  • 修士(理学) - 慶應義塾大学

学内所属歴 【 表示 / 非表示

  • 2019年4月
    -
    現在

    専任   横浜国立大学   大学院環境情報研究院   社会環境と情報部門   准教授  

  • 2017年2月
    -
    2019年3月

    専任   横浜国立大学   大学院環境情報研究院   社会環境と情報部門   特任教員(准教授)  

  • 2021年4月
    -
    現在

    併任   横浜国立大学   大学院先進実践学環   准教授  

  • 2019年4月
    -
    現在

    併任   横浜国立大学   大学院環境情報学府   情報メディア環境学専攻   准教授  

  • 2019年4月
    -
    現在

    併任   横浜国立大学   大学院環境情報学府   情報環境専攻   准教授  

全件表示 >>

学外略歴 【 表示 / 非表示

  • 2012年11月
    -
    2017年1月

      国立情報学研究所   特任助教

所属学協会 【 表示 / 非表示

  • 2008年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年

    DOI CiNii

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会   共著  

    <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>

    その他リンク: https://ci.nii.ac.jp/naid/130007993194

  • Thomassen's conjecture for line graphs of 3-hypergraphs

    Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr

    DISCRETE MATHEMATICS   343 ( 6 )   2020年6月  [査読有り]

    DOI Web of Science

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

  • 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月  [査読有り]

    DOI Web of Science

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

  • 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月  [査読有り]

    Web of Science

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

  • 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月  [査読有り]

    DOI Web of Science

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

全件表示 >>

総説・解説記事等 【 表示 / 非表示

  • エレガントな解答を求む 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年度   グラフアルゴリズム論演習

    大学院環境情報学府

全件表示 >>

担当経験のある授業科目(学外) 【 表示 / 非表示

  • 有限数学 第2

    機関名:慶應義塾大学理工学部