定式化
グラフ彩色問題は，以下のように定義される問題である．
点数 $n$ の無向グラフ $G=(V,E)$ の $K$分割（$K$ partition）とは，点集合 $V$ の $K$ 個の部分集合への分割 $\Upsilon= \{V_1, V_2, \ldots, V_K\}$ で， $V_i \cap V_j =\emptyset, \forall i \neq j$（共通部分がない），$\bigcup_{j=1}^K V_j =V$（合わせると点集合全体になる） を満たすものを指す．各 $V_i (i=1,2,\ldots,K)$ を色クラス(color class)と呼ぶ．
$K$分割は，すべての色クラス $V_i$ が安定集合（点の間に枝がない）のとき $K$彩色($K$ coloring)と呼ばれる． 与えられた無向グラフ $G=(V,E)$ に対して， 最小の $K$ （これを彩色数と呼ぶ) を導く $K$ 彩色 $\Upsilon=\{ V_1, V_2, \ldots, V_K \}$ を求めよ.
グラフ彩色問題の定式化を行うために，彩色可能な色数の上界 $K_{\max}$ が分かっているものと仮定する． すなわち，最適な $K$彩色は，$1 \leq K \leq K_{\max}$ の整数から選択される．
標準定式化
点 $i$ に塗られた色が $k$ のとき $1$，それ以外のとき $0$ の $0$-$1$ 変数 $x_{ik}$ と， 色クラス $V_{k}$ に含まれる点が $1$つでも あるときに $1$，それ以外の（色クラスが空の）とき $0$ の $0$-$1$ 変数 $y_{k}$ を用いると， グラフ彩色問題は，以下のように定式化できる．
$$ \begin{array}{l l l} minimize & \sum_{k=1}^{K_{\max}} y_{k} & \\ s.t. & \sum_{k=1}^{K_{\max}} x_{ik} = 1 & \forall i \in V \\ & x_{ik} + x_{jk} \leq y_{k} & \forall (i,j) \in E, k=1,2,\ldots,K_{\max} \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & y_{k} \in \{0,1\} & \forall k =1,2,\ldots,K_{\max} \end{array} $$Gurobiをはじめとする多くの数理最適化ソルバーは，分枝限定法を利用して求解している． 分枝限定法においては， 上のグラフ彩色問題の定式化における色クラスはすべて無記名で扱われるため，解は対称性をもつ． たとえば，解 $V_1=\{1,2,3\}, V_2=\{4,5\}$ と解 $V_1=\{4,5\}, V_2=\{1,2,3\}$ はまったく同じものであるが， 上の定式化では異なるベクトル $x,y$ で表される．この場合，変数 $x,y$ をもとに分枝しても下界が改良されない現象が発生する． グラフ彩色問題を市販の数理最適化ソルバーで求解する際には，解の対称性を避けるために，添え字の小さい色クラスを優先して用いることを表す，以下の制約を付加することが推奨される．
$$ y_{k} \leq \sum_{i \in V} x_{ik} \ \ \ \forall k=1,2,\ldots,K_{\max} $$$$ y_{k} \geq y_{k+1} \ \ \ \forall k=1,2,\ldots,K_{\max}-1 $$random.seed(123)
n = 10
K = n
pos = {i: (random.random(), random.random()) for i in range(n)}
G = nx.random_geometric_graph(n, 0.5, pos=pos)
V = G.nodes()
E = G.edges()
model = Model("gcp - standard")
x, y = {}, {}
for i in V:
for k in range(K):
x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
for k in range(K):
y[k] = model.addVar(vtype="B", name=f"y({k})")
model.update()
for i in V:
model.addConstr(quicksum(x[i, k] for k in range(K)) == 1, f"AssignColor({i})")
for (i, j) in E:
for k in range(K):
model.addConstr(x[i, k] + x[j, k] <= y[k], f"BadEdge({i},{j},{k})")
for k in range(K):
model.addConstr(y[k] <= quicksum(x[i, k] for i in V), f"SymmetryBreak1({k})")
for k in range(K - 1):
model.addConstr(y[k] >= y[k + 1], f"SymmetryBreak2({k})")
model.setObjective(quicksum(y[k] for k in range(K)), GRB.MINIMIZE)
model.optimize()
color = {}
if model.status == GRB.Status.OPTIMAL:
for i in V:
for k in range(K):
if x[i, k].X > 0.5:
color[i] = k
break
print("solution:", color)
nx.draw(
G,
pos=pos,
with_labels=False,
node_color=[color[i] for i in V],
node_size=100,
cmap=plt.cm.Paired,
edge_color="black",
width=0.5,
)
彩色数固定定式化
上で示したアプローチでは，彩色数 $K$ を最小化することを目的としていた． 以下では，彩色数 $K$ を固定した定式化を用いることによって，より大規模な問題を求解することを考えよう．
枝の両端点が同じ色で彩色されているとき $1$，それ以外のとき $0$ を表す 新しい変数 $z_{ij}$ を導入する．そのような「悪い」枝の数を最小化し， 最適値が $0$ になれば，彩色可能であると判断される．彩色数 $K$ を変えながら， この最適化問題を解くことによって，最小の彩色数を求めることができる．
$$ \begin{array}{l l l} minimize & \sum_{(i,j) \in E} z_{ij} & \\ s.t. & \sum_{k=1}^{K} x_{ik} = 1 & \forall i \in V \\ & x_{ik} + x_{jk} \leq 1+z_{ij} & \forall (i,j) \in E, k=1,2,\ldots,K \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K \\ & z_{ij} \in \{0,1\} & \forall (i,j) \in E \end{array} $$ここで目的関数は，悪い枝の数の最小化である． 最初の制約は，各点 $i$ に必ず1つの色が塗られることを表す． 2番目の制約は，枝$(i,j)$ の両端点の点$i$ と点$j$ が，同じ色クラスに割り当てられている場合には， 枝$(i,j)$ が悪い枝と判定されることを表す．
彩色数 $K$ を固定した定式化は，以下のようになる．
def gcp_fixed_k(V, E, K):
"""gcp_fixed_k -- model for minimizing number
of bad edges in coloring a graph
Parameters:
- V: set/list of nodes in the graph
- E: set/list of edges in the graph
- K: number of colors to be used
Returns a model, ready to be solved.
"""
model = Model("gcp - fixed k")
x, z = {}, {}
for i in V:
for k in range(K):
x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
for (i, j) in E:
z[i, j] = model.addVar(vtype="B", name=f"z({i},{j})")
model.update()
for i in V:
model.addConstr(quicksum(x[i, k] for k in range(K)) == 1, f"AssignColor({i})")
for (i, j) in E:
for k in range(K):
model.addConstr(x[i, k] + x[j, k] <= 1 + z[i, j], f"BadEdge({i},{j},{k})")
model.setObjective(quicksum(z[i, j] for (i, j) in E), GRB.MINIMIZE)
model.update()
model.__data = x, z
return model
上のモデル（彩色数固定定式化）を用いて最適な（色数最小の）グラフ彩色を得るには，2分探索をすればよい． 以下のそのためのコードを示す．
def solve_gcp(V, E):
"""solve_gcp -- solve the graph coloring problem
with bisection and fixed-k model
Parameters:
- V: set/list of nodes in the graph
- E: set/list of edges in the graph
Returns tuple with number of colors used,
and dictionary mapping colors to vertices
"""
LB = 0
UB = len(V)
color = {}
while UB - LB > 1:
K = (UB + LB) // 2
print("trying fixed K=", K)
gcp = gcp_fixed_k(V, E, K)
gcp.Params.OutputFlag = 0 # silent mode
gcp.Params.Cutoff = 0.1
gcp.optimize()
if gcp.status == GRB.Status.OPTIMAL:
x, z = gcp.__data
for i in V:
for k in range(K):
if x[i, k].X > 0.5:
color[i] = k
break
# else:
# raise "undefined color for", i
UB = K
else:
LB = K
return UB, color
K, color = solve_gcp(V, E)
print("minimum number of colors:", K)
print("solution:", color)
ampl = AMPL(Environment(AMPL_PATH))
ampl.option['solver'] = 'highs'
ampl.read("../ampl/gcp_fixed_k.mod")
ampl.set['V'] = list(V)
ampl.set['E'] = list(E)
LB = 0
UB = len(V)
while UB - LB > 1:
K = (UB + LB) // 2
print("current K:{}\t[LB:{},UB:{}]".format(K,LB,UB))
ampl.param['K'] = K
ampl.solve()
Z = ampl.obj['Z']
#print("Bad edges:", Z.value())
if Z.value() > .5:
LB = K
z = ampl.var['z']
# for (i, j) in E:
# if z[i, j].value() > .5:
# print("Bad edge:", (i, j))
else:
UB = K
x = ampl.var['x']
for k in range(1, K + 1):
vk = [i for i in V if x[i, k].value() > .5]
#print("color {} used in {}".format(k, vk))
print()
print("Chromatic number:", UB)
print("color {} used in {}".format(k, vk))
半順序定式化
解の対称性を除去するために，同じ色に塗られた点の部分集合に対する半順序を用いた定式化を示す．
点 $i$ に塗られた色が $k$ のとき $1$，それ以外のとき $0$ の $0$-$1$ 変数 $x_{ik}$ の他に， 各点 $i$ に対して色 $k$ に先行する（$i \prec k$）か後続する（$k \prec i$）かを表す以下の変数を導入する．
$y_{ki}$: 点 $i$ が色$k$に後続する（$k \prec i$）とき $1$，それ以外のとき $0$ の $0$-$1$ 変数
$z_{ik}$: 点 $i$ が色$k$に先行する（$i \prec k$）とき $1$，それ以外のとき $0$ の$0$-$1$ 変数
グラフ彩色問題は，以下のように定式化できる．
$$ \begin{array}{l l l} minimize & 1+\sum_{k=1}^{K_{\max}} y_{k0} & \\ s.t. & x_{ik} = 1-(y_{ki}+z_{ik}) & \forall i \in V; k =1,2,\ldots,K_{\max} \\ & z_{i1} = 0 & \forall i \in V \\ & y_{K_{\max},i} = 0 & \forall i \in V \\ & y_{ki} \geq y_{k+1,i} & \forall i \in V, k =1,2,\ldots,K_{\max}-1 \\ & y_{ki} + z_{i,k+1} =1 & \forall i \in V, k =1,2,\ldots,K_{\max}-1 \\ & y_{k0} \geq y_{ki} & \forall i \in V \setminus \{0\}, k =1,2,\ldots,K_{\max} \\ & x_{ik} + x_{jk} \leq 1 & \forall (i,j) \in E \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & y_{ki} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & z_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \end{array} $$目的関数は，最初の点 $0$ に先行する色数の最小化であり，点 $0$ が塗られた色クラス $1$ を加えたものが最小の彩色数になる．
最初の制約は，点 $i$ が色 $k$ に後続も先行もされないときは，色 $k$ に塗られていることを表す． 2番目の制約は，色 $1$ に先行する点がないこと，3番目の制約は，最後の色に後続する点がないことを表す． 4番目の制約は，点が色$k+1$に後続するなら色$k$にも後続することを表す． 5番目の制約は，点 $i$ が何れかの色に塗られることを規定する． 6番目の制約は，他の点が色 $k$ に塗られたら，点 $0$ には $k$以上の色で塗ることを表す． 最後の制約は，枝の両端点が異なる色で塗られることを表す．
半順序を用いた定式化は，以下のようになる．
K = n
model = Model("gcp - partial order")
x, y, z = {}, {}, {}
for i in V:
for k in range(K):
x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
y[k, i] = model.addVar(vtype="B", name=f"y({k},{i})")
z[i, k] = model.addVar(vtype="B", name=f"z({i},{k})")
model.update()
for i in V:
model.addConstr(z[i, 0] == 0, f"FixZ({i})")
model.addConstr(y[K - 1, i] == 0, f"FixY({i})")
for i in V:
for k in range(K - 1):
model.addConstr(y[k, i] >= y[k + 1, i], f"Ordering({i},{k})")
model.addConstr(y[k, i] + z[i, k + 1] == 1, f"AssignColor({i},{k})")
model.addConstr(y[k, 0] >= y[k, i], f"FirstNode({i},{k})")
# for i in V:
# model.addConstr(quicksum(x[i,k] for k in range(K)) == 1,
# f"AssignColor({i})")
for i in V:
for k in range(K):
model.addConstr(x[i, k] == 1 - (y[k, i] + z[i, k]), f"Connection({i},{k})")
for (i, j) in E:
for k in range(K):
model.addConstr(x[i, k] + x[j, k] <= 1, f"BadEdge({i},{j},{k})")
model.setObjective(1 + quicksum(y[k, 0] for k in range(K)), GRB.MINIMIZE)
model.optimize()
for i in V:
for k in range(K):
if x[i, k].X > 0.5:
color[i] = k
break
print("solution:", color)
代表点定式化
隣接していない2つの点 $i,j$ に対して， 点 $j$ の色を点 $i$ と同じ色にするとき $1$，それ以外のとき $0$ になる $0$-$1$ 変数 $x_{ij}$ を導入する． 変数 $x_{ij}$ が $1$ のとき， 点 $j$ は点 $i$ に割り当てられ，点 $i$ が点 $j$ の代表点になっている また， $0$-$1$ 変数 $x_{ii}$ は，点 $i$ を色 $i$ で彩色するとき$1$，それ以外のとき $0$ になるものとする．
$N_i (A_i)$ を点 $i$ に隣接していない点からなるグラフの点（枝）集合とする．
これらの記号を用いると，グラフ彩色問題は，以下のように定式化できる．
$$ \begin{array}{l l l} minimize & \sum_{i \in V} x_{ii} & \\ s.t. & \sum_{i \in N_j} x_{ij} + x_{jj} \geq 1 & \forall j \in V \\ & x_{ij} + x_{ik} \leq x_{ii} & \forall i \in V, (j,k) \in A_i \\ & x_{ij} \leq x_{ii} & \forall i \in V, j \in N_i \\ & x_{ij} \in \{0,1\} & \forall i \in V, j \in V \end{array} $$目的関数は色の代表点として選ばれた点数の最小化である．
最初の制約は，点 $j$ は代表点になるか，他の隣接していない点に割り振られるかのいずれかであることを表す． 2番目の制約は，点 $i$ に隣接していないグラフ内の枝 $(j,k)$ の両端点に，点 $i$ に塗られている色を同時に割り振らないことを表す． 3番目の制約は，他の点から割り振られた点は必ず代表点であることを表す．
最後の2本の制約は，点 $i$ に隣接していないグラフ内の極大クリーク（完全部分グラフ）を用いることによって強化できる．
Gbar = nx.complement(G)
model = Model("gcp - representative")
x = {}
for i in V:
for j in V:
x[i, j] = model.addVar(vtype="B", name=f"x({i},{j})")
model.update()
for j in V:
model.addConstr(
quicksum(x[i, j] for i in Gbar.neighbors(j)) + x[j, j] >= 1, f"Assign({j})"
)
for i in V:
for (j, k) in G.subgraph(Gbar.neighbors(i)).edges():
model.addConstr(x[i, j] + x[i, k] <= x[i, i], f"BadEdge({i},{j},{k})")
for j in Gbar.neighbors(i):
model.addConstr(x[i, j] <= x[i, i], f"Connection({i},{j})")
model.setObjective(quicksum(x[i, i] for i in V), GRB.MINIMIZE)
model.optimize()
color = {}
k = 0
for i in V:
if x[i, i].X > 0.5:
color[i] = k
k += 1
for (i, j) in x:
if i != j and x[i, j].X > 0.5:
color[j] = color[i]
print("solution:", color)
from scop import *
m = Model()
K = 20
nodes = [f"node_{i}" for i in V]
varlist = m.addVariables(nodes, range(K))
for (i, j) in E:
con1 = Alldiff(f"alldiff_{i}_{j}", [varlist[i], varlist[j]], "inf")
m.addConstraint(con1)
m.Params.TimeLimit = 10
sol, violated = m.optimize()
if m.Status == 0:
print("solution")
for x in sol:
print(x, sol[x])
print("violated constraint(s)")
for v in violated:
print(v, violated[v])
構築法
グラフ彩色問題に対しては，以下の構築法が代表的である．
- seq_assignment: 与えられた点の番号の順に，彩色可能な最小の番号の色で塗っていく．
- largest_first: 点の次数（隣接する点の数）が大きいものから順に彩色する．
- dsatur: 構築法の途中で得た動的な情報をもとに，次に彩色する点を選択する．具体的には，次に彩色する点を， 隣接する点ですでに使われた色数が最大のもの（同点の場合には，彩色されていない隣接点の数が最大のもの）とする．
- recursive_largest_fit: 同じ色を塗ることができる点の集合（色クラス）は，互いに隣接していてはいけない． これは，安定集合に他ならない． 新しい色で彩色するための安定集合を順次求めることによって解を構築する．
print("*** graph coloring problem ***")
print()
print("instance randomly created")
nodes, adj = gts.rnd_adj_fast(100, 0.5)
print("sequential assignment")
color, K = seq_assignment(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("largest fit")
color, K = largest_first(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("dsatur")
color, K = dsatur(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("recursive largest fit")
color, K = recursive_largest_fit(nodes, adj)
print("solution: z =", K)
print(color)
print()
タブーサーチ
彩色数 $K$ を固定した問題を考える．枝の両端点が同色で塗られた枝を「悪い枝」とよぶことにする． 点 $i$ に接続する悪い枝の数 $B(i)$ とすると， この問題における目的関数は以下のように定義される．
$$ \sum_{i=1}^{n} B(i)/2 $$彩色数 $K$ は固定されているので，もし目的関数が $0$ となる解が得られたときは，$K$ 彩色が得られたことになる． 彩色数の上限は点 の数 $n$ であるので，$2$ 分探索法を用いれば 最悪でも $\lceil \log_2 n \rceil$ 回だけ彩色数 $K$ を固定した問題を解けば原問題の最適解が得られる． ちなみに，$\lceil \cdot \rceil$ は天井関数（ceiling function）であり， $\cdot$ 以上の最小の整数を表す．
この問題の目的関数値を減らすためには，接続する悪い枝の数 $B(i)$ が正の値をもつ点の色を変える必要がある． したがって，$B(i)>0$ である点に限定して色を変更する操作を行う方が良いと考えられる． このような近傍の制限は，近傍が広い（近傍に含まれる解の数が多い）ときに有効である．
以下に，彩色数 $K$ を固定した場合に対する制限付きmove近傍を用いたタブーサーチを示す． 禁断リスト $tabu$ には，点と色のペアを保管する．
nodes, adj = gts.rnd_adj_fast(100, 0.5)
K = 15 # tentative number of colors
print("tabu search, trying coloring with", K, "colors")
color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()
print("starting tabu search")
tabulen = K
max_iter = 1000
color, sum_bad_degree = tabu_search(nodes, adj, K, color, tabulen, max_iter)
print("final solution: z =", sum_bad_degree)
print("color:", color)
遺伝的アルゴリズムとタブーサーチの融合法
タブーサーチは，広い範囲の問題例に対して，比較的短時間で良好な近似解を算出するので推奨されるが， より長い時間を要してさらに良い解を探索したい場合には，複数の解を保持して， その集団を改良していく方法を用いることができる．ここでは簡単な遺伝的アルゴリズムとの融合を用いる． この融合法は，改善法を遺伝的アルゴリズムに組み込んだ方法（遺伝的近傍探索法）と考えられる．
まず，集団から親を選択する方法について述べる． 集団 $P$ 内に保持された解を目的関数値（この場合には悪い枝の数）の小さい順に $0,1,\cdots,|P|-1$ と並べておく． この順位をランクとよぶ．ランクの小さな解を優先し，かつランダムに親を選択することを考える． $i$ 番目のランクをもつ解が親として選択される確率を $|P|-i$ に比例させるものとする． $m=|P| (|P| +1)/2$ としたとき，選択確率は $$ \frac{|P|-i}{m} $$ となる．
この確率でランダムに選択された相異なる2 つの解（親）に対応する $K$ 分割を， $\Upsilon^1=\{ V_1^1,\ldots,V_K^1 \}$，$\Upsilon^2=\{ V_1^1,\ldots,V_K^2 \}$ とする． 2 つの親の形質をなるべく均等に取り入れ，かつ各色クラスの位数（含まれる点の個数）が大きくなるようにしたいので， 各親から交互になるべく位数の大きな色クラスを選択することにする． これを擬似コードとして記述すると以下のようになる．
$\Upsilon^1=\{ V_1^1,\ldots,V_K^1 \}$，$\Upsilon^2=\{ V_1^1,\ldots,V_K^2 \}$ に対する交叉
- 生成する子 $\Upsilon :=\emptyset$
- for all $i = 1, \ldots, K$ do
- $i$ が奇数のときは親番号 $p=1$，偶数のときは親番号 $p=2$
- $k^* := argmax_{k} \{ |V_k^p| \}$
- 色クラス $V_{k^*}^p$ を子 $\Upsilon$ に追加
- 色クラス $V_{k^*}^p$ 内の点を $\Upsilon^1, \Upsilon^2$ から削除
- まだ色が塗られていない点に対してランダムに $1,\ldots,K$ を彩色
- return $\Upsilon$
上の交叉を用いることによって，遺伝的アルゴリズムとタブーサーチの融合法が構築できる．
nodes, adj = gts.rnd_adj_fast(100, 0.5)
K = 15 # tentative number of colors
print(
"genetic algorithm (intensification with tabu search), trying coloring with",
K,
"colors",
)
color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()
print("starting evolution with genetic algorithm")
nelem = 10
ngen = 100
TABULEN = K
TABUITER = 100
color, sum_bad_degree = gcp_ga(nodes, adj, K, ngen, nelem, TABULEN, TABUITER)
print("final solution: z =", sum_bad_degree)
print("color:", color)
G = gts.to_nx_graph(nodes, adj)
# print(G.edges())
pos = nx.layout.spring_layout(G)
node_color = [color[i] for i in G.nodes()]
nx.draw(
G,
pos=pos,
with_labels=False,
node_color=node_color,
node_size=50,
width=0.1,
cmap=plt.cm.cool,
edge_color="black",
)
枝彩色問題
グラフ彩色問題が点に色を塗るのに対して，枝彩色問題(edge coloring problem)では，枝に色を塗る． グラフ理論では，2つの問題は区別して研究されているが，最適化の観点では（簡単に帰着できるという意味で）ほぼ同値な問題である．
無向グラフ $G=(V,E)$ に対する枝彩色問題は， 枝（点の対）上に点を配置し，端点を共有する枝に対応する点の間に枝をはったグラフ（線グラフ） $L$ に対する（点）彩色に帰着される．
例として完全グラフに対する枝彩色を行う． $8$ 点の完全グラフに対する枝彩色は $7$ になることが知られており，これは $8$ チームの総当りのトーナメントが $7$ 日で完了することを表している．
G = nx.complete_graph(8)
L = nx.line_graph(G)
nx.draw(G)
点彩色問題に変換したグラフ（線グラフ）を描く．
nx.draw(L)
点彩色問題をメタヒューリスティクスで解く．
K = 7
mapping = dict(zip(L.nodes(), list(range(len(L)))))
G2 = nx.relabel_nodes(L, mapping)
nodes = G2.nodes()
adj = [set([]) for i in nodes]
for (i, j) in G2.edges():
adj[i].add(j)
adj[j].add(i)
color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()
print("starting evolution with genetic algorithm")
nelem = 10
ngen = 100
TABULEN = K
TABUITER = 100
color, sum_bad_degree = gcp_ga(nodes, adj, K, ngen, nelem, TABULEN, TABUITER)
print("final solution: z =", sum_bad_degree)
print("color:", color)
以下のような7色の点彩色が得られる．
nx.draw(
L,
with_labels=False,
node_color=color,
node_size=100,
cmap=plt.cm.cool,
edge_color="black",
width=1,
)
枝彩色に戻して描画する． 色はトーナメントの日を表し，7日でトーナメントが終了することが分かる．
col = {}
for i, (u, v) in enumerate(L.nodes()):
col[u, v] = color[i]
edge_color = []
for (u, v) in G.edges():
edge_color.append(col[u, v])
nx.draw(
G,
with_labels=False,
node_color="b",
node_size=100,
cmap=plt.cm.afmhot,
edge_color=edge_color,
width=5,
)