Discrete Structures20815 marksMinimum Spanning Trees
Define chromatic number. How does Kruskal's algorithm find Minimum Spanning Tree?
Define chromatic number. How does Kruskal's algorithm find Minimum Spanning Tree? [5]
--- The chromatic number of a graph G is the minimum number of colors required to color the vertices of G such that no two adjacent vertices (vertices connected by an edge) share the same color. It is denoted by χ(G) (chi of G). Examples: - A complete graph Kn has chromatic number χ(Kn) = n - A c...