Given an undirected graph G G G G , the problem is to determine whether or not
Question:
Given an undirected graph G, the problem is to determine whether or not G is connected. Use an adversary argument to prove that it is necessary to look at all (n2−n)/2 potential edges in the worst case.
Graph G:
A graph consists of a set of vertices and a set of edges , such that each edge in is a connection between a pair of vertices in The number of vertices is written , and the number of edges is written can range from zero to a maximum of . A graph with relatively few edges is called sparse, while a graph with many edges is called dense. A graph containing all possible edges is said to be complete.
A graph whose edges are not directed is called an undirected graph (as illustrated by Figure 11.1(a)).
Figure 11.1 (a):
Step by Step Answer:
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer