グラフの向き付けとは，無向グラフの各辺に向きを付けて有向グラフを得ることをいい，組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである．本講演では，連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく，「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する．我々の主結果は，「2k辺連結無向グラフの任意の向き付けに対して，うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ，最終的にk辺連結向き付けを得ることができる」というものである．これは，古典的な Nash-Williams の定理を強めた結果であり，k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である．

なお，この成果は本プロジェクトメンバーとの共同研究に基づくものであり，SODA2022で発表予定である．