1. Discrete Mathematics

Hello everyone, welcome to this lecture. The plan for this lecture is as follows. In this lecture, we will discuss various operations that we can perform on graphs. We will see various mechanisms of representing graphs. We will discuss the graph isomorphism problem and we will define the connectivity in a graph.

This section introduces the topic of graph operations. Graphs are mathematical structures used to model pairwise relationships between objects. Operations on graphs allow us to manipulate and analyze these structures in various ways. During the lecture, different mechanisms for representing graphs will be covered, such as adjacency matrices and adjacency lists. Additionally, concepts related to graph isomorphism, which is about determining when two graphs are structurally identical, and graph connectivity, which relates to the paths within a graph, will be discussed.

Think of a graph as a social network where each person is a node, and each friendship is an edge. The operations we discuss will help us understand how friendships can form, change, or how we can analyze the structure of the social network.

We will first define what we call as the subgraph of a graph, if you are given a graph G = (V, E) with the vertex set being V and edge set being E. Then, a graph H = (W, F) with vertex set W and edge set F will be called a subgraph of G, if the vertex set W of H is a subset of the vertex set V of G and the edge set F of H is a subset of the edge set E of G.

A subgraph is a smaller graph formed from a larger graph by selecting some of its vertices and edges. For H to be a subgraph of G, every vertex in H must also be a vertex in G, and every edge in H must connect vertices that are found within the vertex set of G. This is important in various applications where we want to analyze smaller components of a larger network.

Imagine a large city map (the graph G), and you decide to focus only on a specific neighborhood (the subgraph H) which contains some streets (edges) and intersections (vertices) from the city map. This neighborhood can be analyzed independently, much like examining a subgraph within a larger network.

Now let us define what we call a proper subgraph of a graph. A graph H will be called as a proper subgraph of G if either the vertex set of H is a proper subset of the vertex set of G and the edge set of H is a proper subset of the edge set of G.

A proper subgraph is a type of subgraph that must contain fewer vertices and edges than the original graph. This means that neither the vertex set nor the edge set of H can be identical to those of G. Hence, a proper subgraph 'H' cannot represent the entire structure of 'G' but instead consists of a part of it.

Returning to our city analogy, if the entire city (G) can be viewed as a graph, then a proper subgraph might be just one specific district within it. It would not include every street and intersection but only those specific to that district.

Next, we will define what we call an induced subgraph. If you are given a graph G = (V, E) with vertex set V and edge set E and if I take a subset of vertices W, then G’ is called the induced subgraph or the induced by the vertex set W such that the vertex set of G’ is W and the edge set E’ of G’ consists of only those edges whose both endpoints are within the subset W.

An induced subgraph is created from a graph by selecting a subset of its vertices and then including all edges that connect pairs of vertices in this subset. This offers a focused view of the relationships among the selected vertices compared to the entire graph, providing insights into specific components or relationships.

Consider again the city analogy, where if you decide to study just the high-school students in a neighborhood (W), the induced subgraph would include all friendships (edges) between these students while ignoring relationships outside this group. This helps in understanding dynamics in that specific segment.

Now let us see some set theoretic operations that we can perform on an existing graph to get new graphs, so imagine you are given a graph then the deletion of an edge is denoted by this operation. If I delete an edge then the vertex set does not get disturbed, it remains the same, it is only the edge set which gets affected.

This chunk outlines how operations such as the deletion of edges and vertices can change a graph while affecting its structure. Removing edges affects connections between vertices but not the vertices themselves, whereas removing vertices impacts both the vertex set and associated edges. Understanding these operations is crucial in applications where network reliability or connectivity might be challenged, for example, in telecommunications or transport networks.

If we think of the graph as a network of roads connecting various towns, then removing a road (edge) doesn’t eliminate the towns (vertices); it just changes how people can travel between them. Conversely, if one of the towns itself is removed, all roads leading to and from that town also disappear, effectively altering the entire structure of the travel network.

Now let us discuss the various data structures that we can use to represent graphs. We have what we call as the adjacency matrix representation. This is a boolean matrix.

Graphs can be represented using various data structures, where adjacency matrices and adjacency lists are popular. An adjacency matrix encodes which vertices are connected by edges in a two-dimensional grid format, suitable for dense graphs. In contrast, an adjacency list represents each vertex alongside a list of adjacent vertices, which is more space-efficient for sparse graphs.

Continuing with the road network analogy, think of the adjacency matrix as a large table that lists all the towns (vertices) and indicates which ones are directly connected by roads (edges). On the other hand, an adjacency list would list each town and show just the names of the towns directly reachable from it, making it easier to see connections without requiring an overwhelming amount of space.

Let us define a graph isomorphism. If you see these two graphs, pictorially they are drawn in a different way. However, structurally, they are similar graphs with the same number of vertices and edges.

Graph isomorphism checks if two graphs are fundamentally the same despite differences in their visual representations or vertex labels. This involves finding a one-to-one correspondence between the vertices of the graphs that preserves connections or edges. Understanding isomorphism is critical in many fields like chemistry and network analysis, where different representations convey the same underlying structure.

Think of graph isomorphism as two different maps of the same city. One map might show a park and the other might not, but the underlying streets and connections are the same. As long as you can find a way to match roads from one map to the other without changing connectivity, the maps are isomorphic.

Let us next define connectivity in a graph. A path of length 'n' between nodes 'u' and 'v' is defined as a sequence of edges connecting these nodes. An undirected graph is called connected if there exists a path between every pair of distinct vertices.

Connectivity describes how well a graph is connected: a connected graph means every vertex can be reached from any other vertex via paths. A path connects two nodes through a series of edges. Understanding connectivity is important in networking, logistics, and social graphs, as it reflects the network's reliability and accessibility.

Picture a public transportation system. If every station can be reached from every other station through existing routes, the system is 'connected.' But if some stations can’t be reached without transferring to another mode of travel or are isolated, that’s akin to having disconnected vertices in a graph.

Let us next define cut vertex and cut edge. Cut vertices are critical since if deleting the vertex will disconnect the graph, it is defined as a cut vertex.

Cut vertices and cut edges represent crucial components in a connected graph. A cut vertex, or articulation point, is one whose removal increases the number of connected components, meaning it disconnects parts of the graph. Similarly, a cut edge (or bridge) is an edge whose removal has the same effect. Understanding these points is vital in analyses related to network robustness and vulnerability.

Imagine a power grid as a graph where cities represent vertices and power lines are edges. If a power line (cut edge) is severed, entire sections of the city may lose power. A cut vertex might represent a central power station; if it goes offline, multiple neighborhoods will lose their energy supply, highlighting points of failure within the network.

--