グラフの3彩色について (6ﾚｽ)
上下前次1-新
1: １３２人目の素数さん [] 2025/02/27(木) 11:16:52.50 ID:EOenYDRm(1) AAS
頂点n個の完全グラフを3彩色可のグラフにするため辺をk本切断する操作を考える。
この時kの最小値をnで表せないかな？
対角線だけ残したグラフと周だけ残したグラフの二つは自明だけど…
2: １３２人目の素数さん [] 2025/02/28(金) 09:12:37.30 ID:EHAzzIyG(1) AAS
なんか知らんが頑張れ
3: １３２人目の素数さん [] 2025/03/01(土) 10:42:16.92 ID:fb64tq5C(1/2) AAS
やるかー
時間かかるけどプログラムで計算して表に著して観てみるか
頂点4の時は1本切ればいいけどそれ以降が不透明なんよな
式にできれば帰納法で証明できるだろうからとりあえずそこまで頑張ってみるぜ
4: １３２人目の素数さん [] 2025/03/01(土) 11:02:29.53 ID:fb64tq5C(2/2) AAS
ちなみにchatGPT先生曰くk≒n^2/3らしい。
近似になるのがなんでなのかは分からん。
nk平面における分布をまとめるとそれらしくなるのかもしれないけど。
公式が欲しい。
5: １３２人目の素数さん [] 2025/03/01(土) 22:11:01.33 ID:UQYv3ub4(1) AAS
4^2/3は1に全然近くないが
6: １３２人目の素数さん [] 2025/03/03(月) 21:19:29.35 ID:4GEovj34(1) AAS
nが3の倍数のときn(n-3)/6
それ以外のとき(n-1)(n-2)/6
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.187s*