Problem 1 - Applied Discrete Structures

Question

Estimate the number of vertices and edges in each of the following graphs. Would the graph be considered sparse, so that an adjacency matrix would be inefficient? (a) Vertices: Cities of the world that are served by at least one airline. Edges: Pairs of cities that are connected by a regular direct flight. (b) Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits. (c) Vertices: All English words. Edges: An edge connects word \(x\) to word \(y\) if \(x\) is a prefix of \(y\).

Step-by-Step Solution

Answer

Graph (a) is sparse with cities and flights. Graph (b) has moderate sparsity with ASCII characters. Graph (c) is sparse with English word prefixes.

Step 1: Estimating Vertices and Edges for Graph (a)

Graph (a) represents cities of the world connected by direct flights. There are approximately 10,000 cities worldwide that airports serve, which means we can assume around 10,000 vertices. Each airline may serve multiple routes, resulting in thousands of potential edges. Realistically, not every pair of cities is directly connected, estimating far fewer than 50,000 edges, remaining a sparse graph. With millions of potential connections possible but only thousands present, the adjacency matrix would indeed be inefficient due to its sparseness.

Step 2: Determining Sparsity for Graph (a)

With approximately 10,000 vertices and potentially far less than 50,000 edges, the graph is very sparse. Using an adjacency matrix, which has a possible connection for every pair of two vertices, would require an excessive amount of storage (10,000 x 10,000 matrix), rendering it inefficient.

Step 3: Estimating Vertices and Edges for Graph (b)

Graph (b) uses ASCII characters which have 128 different characters, leading to 128 vertices. Considering edges, an edge exists if two characters differ by exactly two bits. Calculating for 128 characters, the graph becomes a form of a hypercube making it moderately sparse due to combinations of differing only in two bit positions out of at least 7 bits.

Step 4: Determining Sparsity for Graph (b)

With 128 vertices and several combinations for edges based on two-bit differences, it’s more populated compared to fully connected graphs with the same number of vertices; however, it is not sparse enough for an adjacency matrix to be inefficient since it won't be as large as in Graph (a). Thus, it's somewhat dense but manageable.

Step 5: Estimating Vertices and Edges for Graph (c)

Graph (c) covers all English words, estimated as more than 1 million vertices (considering derivatives and plural forms). Each word can be a prefix to many others, resulting in potentially more than a million edges where each word is linked to multiple longer words starting with it. Yet, not all potential pairs have edges as they depend on the dictionary structure: the result is still sparse because many words are not prefixes.

Step 6: Determining Sparsity for Graph (c)

Such a graph with thousands of words as vertices but only connected via prefixation results in very sparse relational structure compared to millions of word combinations possible. The use of adjacency matrix is also inefficient due to memory and computational inefficiency, resulting in extreme sparseness.

Key Concepts

Sparse Graphs

In graph theory, a sparse graph is one where the number of edges is significantly less than the maximum possible number of edges. For example, Graph (a), which represents cities connected by direct flights, is sparse. While there could be millions of connections, only a few thousand actual flights exist. Graph (c), made of English words where each word has edges to longer words it prefixes, is also sparse since not every word connects to others.

• Real-world scenarios like Graphs (a) and (c) often exhibit sparsity, meaning a vast majority of potential edges aren't present.
• In sparse graphs, processes like searching can be faster as there are fewer connections to traverse.

Efficient data structures like adjacency lists are preferred over matrices in sparse graph scenarios because they save both time and space.

Adjacency Matrix

An adjacency matrix is a square grid used to represent a finite graph, with rows and columns labeled by graph vertices. Each position signifies the presence (or absence) of an edge between two vertices.

• In highly connected or dense graphs, this structure can be efficient because every potential edge can be tracked effectively.
• Conversely, in sparse graphs, it can waste significant space since most positions in the matrix would be zero.

Take Graph (a), with 10,000 vertices, which would demand a matrix of 100 million entries, most of which would be zeros due to flight sparsity. Therefore, in sparse scenarios, algebraic representations become inefficient, and alternative representations like adjacency lists or edge lists are more suitable.

Vertices and Edges

In the context of graph theory, vertices (or nodes) are the fundamental units that may or may not be connected to others by pathways called edges.

• Graph (a) has 'cities' as vertices and 'direct flights' as edges.
• Graph (b) consists of 'ASCII characters' and 'two-bit difference' connections as edges.

Estimating vertices and edges provides insights into the graph's structure. For example, minimal edges suggest a sparse graph, while vertices offer a count of elements involved. This relationship helps decide the optimal data structures for storage and operation on graphs.

Combinatorics

Combinatorics is the field of mathematics concerning the counting, arrangement, and combination of objects. In graph theory, it plays a crucial role in predicting the number of possible connections (or edges) in a graph.

• It helps in understanding variations like two-bit differences in Graph (b), which involves combinatorial calculations to find how many characters can differ in this specific way from others.
• In Graph (c), combinations define how prefixes lead one word to another, estimating potential connections as each word could potentially be a prefix to a host of others.

Combinatorics assists in determining sparsity by calculating feasible versus actual edges, supporting the choice of data structures used in representing and analyzing graphs.