- 4 A Suppose That The Greedy Algorithm Uses K Colors On A Graph G Prove That G Must Have At Least 1 2 K 1 1 (14.35 KiB) Viewed 27 times
4. (a) Suppose that the greedy algorithm uses k colors on a graph G. Prove that G must have at least 1+ 2+ ... + (k-1) =
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
4. (a) Suppose that the greedy algorithm uses k colors on a graph G. Prove that G must have at least 1+ 2+ ... + (k-1) =
4. (a) Suppose that the greedy algorithm uses k colors on a graph G. Prove that G must have at least 1+ 2+ ... + (k-1) = (2) edges. (Hint: whenever a color other than color 1 is used, there are some edges that have to exist to cause this.) (b) Prove that if G has m edges, then (G) <1+ 2m.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!