O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 27

Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem

Our first example deals with graph theory and uses the result of Example 26.6. As we progress, we shall learn how the three topics for this chapter are related.

Example 27.1: If G = (V, E) is an undirected graph with vertex set V and edge set E, we say that the nonempty subset W of V induces a clique in G, if for all vertices a, b img W, the edge ab(= ba) img E. Hence the subgraph of G made up of the vertices in W together with all the possible edges determined by the vertices from W is a complete graph.

In Fig. 27.1 (a) we have an undirected graph G = (V, E), with img and E = {vw, vy, vz, wx, wy, wz, xy, yz}. The undirected graph in part (b) of the figure is a clique for the undirected graph G. This is the clique induced by the vertex set img. In Fig. 27.1 (c) we find another clique from G—this one induced by the vertex set img. Note that Fig. 27.1 (d) provides the clique induced by . This clique is a subgraph (actually, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required