完全グラフ

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

yokobuttonの不定期で競技プログラミングをするブログ•4年前

完全グラフと全彩色予想④

４，全彩色グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという。グラフGがk-全彩色可能であるようなkの最小値をGの全染色数といい、χ2(G)で表す。グラフGの頂点彩色について、k-頂点彩色可能であるようなkの最小値をGの頂点染色数といい、χ(G)で表す。定理４・１ χ2(Kp)=p(pが奇数のとき)、p+1(pが偶数のとき) (証明) 完全グラフKp+1の線グラフをL(Kp+1)で表す。このとき、…

#グラフ理論#完全グラフ#全彩色予想

関連ブログ

yokobuttonの不定期で競技プログラミングをするブログ•4年前

完全グラフと全彩色予想③

３，辺彩色グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能であるが(k-1)-辺彩色可能でないとき、kをGの辺染色数といいχ1(G)で表す。定理３・１完全グラフKpに対して、 χ1(Kp)=p(pが奇数)、p-1(pが偶数) である。 (証明) (1)pが偶数の場合、Kpは定理１・１より、p-1個の1-因子Fi(i=1、2、・・・、p-1)に分解できる。各因子Fiに色iを付ければ、Kpのp-1色によ…

#グラフ理論#完全グラフ#全彩色予想

yokobuttonの不定期で競技プログラミングをするブログ•4年前

完全グラフと全彩色予想②

２、線グラフと全グラフグラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合を持ち、T(G)の2頂点が隣接するのは対応するGの2つの要素(頂点と辺)が隣接しているか、接続しているとき、かつそのときに限るグラフのことである。命題２・１ T(Kp)=L(Kp+1) (証明) 完全グラフKpの性質より、L(Kp)もT(Kp)も正則グラフになる。r-正則グラフのサイズは握手補題より、rp/2になる。完全グラ…

#グラフ理論#完全グラフ#全彩色予想

yokobuttonの不定期で競技プログラミングをするブログ•4年前

完全グラフと全彩色予想①

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。１，因子分解グラフHがグラフGの部分グラフであるとは、Hが V(H)がV(G)の部分集合かつ E(H)がE(G)の部分集合を満たすグラフのことである。特に、V(H)=V(G)のとき、HをGの全域部分グラフという。グラフGの全域部分グラフのうち、木であるものを全域木という。各頂点の次数(頂点に接続する辺の数)がすべて等しいグラフを正則グラフといい、各頂点の次数がkの正則グラフをk-正則グラフという。グラフGの空でない全域部分グラフを因子といい、Gのr-正則な因子をr-因子という。グ…

#グラフ理論#完全グラフ#全彩色予想