边的染色 ■边数为m的图的边色数的上界是多少？下界是多少？ ■完全图Kn的边色数是多少？ ■树的边色数是多少？ v5 V2 V4 v3 2023/5/15 16
n 边数为m的图的边色数的上界是多少？下界是多少？ n 完全图Kn的边色数是多少？ n 树的边色数是多少？ 2023/5/15 16 边的染色 v1 v2 v3 v4 v5
边的染色 ■对于任意一个二分图G:X(G⑦=△(G) 2023/5/15 17
n 对于任意一个二分图G：χ’(G) = ∆(G) 2023/5/15 17 边的染色
边的染色 ■对于任意一个二分图G:X(G)=△(G) ●只需证明以(G)≤△(G) ●采用数学归纳法，对(G归纳 2023/5/15 18
n 对于任意一个二分图G：χ’(G) = ∆(G) l 只需证明χ’(G) ≤ ∆(G) l 采用数学归纳法，对ε(G)归纳 2023/5/15 18 边的染色
边的染色 ■对于任意一个二分图G:X(G⑦=△(G) ●只需证明x(G)≤△(G) ●采用数学归纳法，对ε(G归纳 ●当(G①=0时，X(G⑦=？，△(G⑦=？ 2023/5/15 19
n 对于任意一个二分图G：χ’(G) = ∆(G) l 只需证明χ’(G) ≤ ∆(G) l 采用数学归纳法，对ε(G)归纳 l 当ε(G) = 0时，χ’(G) = ?，∆(G) = ? 2023/5/15 19 边的染色
边的染色 ■对于任意一个二分图G:X(G)=△(G) ●假设(G=k时成立 则(G)=k+1时，构造G的正常k边染色且k≤△(G) 2023/5/15 20
n 对于任意一个二分图G：χ’(G) = ∆(G) l 假设ε(G) = k时成立 则ε(G) = k + 1时，构造G的正常k’边染色且k’ ≤ ∆(G) 2023/5/15 20 边的染色