graph unit 3

Graphs Introduction

• Graphs are non-linear data structures that model relationships between entities, with less restriction compared to tree structures.
• Tree structures have a strict hierarchical relationship (one parent, many children), while graphs allow more flexible relationships (many parents, many children).
• Examples of graph applications in the real world include airline routes, source-destination networks for commodities, and representing geographical connections such as bridges.

Graph Terminologies

• A graph G consists of two sets—vertices (nodes) denoted by V, and edges (arcs) denoted by E.
• E contains pairs of elements from V, which represent connections between the vertices.
• A digraph, or directed graph, is a graph where the edges are ordered pairs, meaning the direction of the connection matters.
• In an undirected graph, edges are unordered, so (vi, vj) and (vj, vi) represent the same edge whereas in a digraph they are distinct.
• A weighted graph is one where the edges have associated weights or labels

Types of Vertices and Graphs

• Adjacent vertices are vertices connected by an edge. For an edge from v; to vj, v; is adjacent to vj.
• A self-loop is an edge where the starting and ending vertices are the same (such as (v₁, v₁)).
• Parallel edges occur when there is more than one edge between the same pair of vertices.
• A multigraph is a graph that contains either self-loops, or parallel edges, or potentially both.
• A simple graph lacks in self-loops nor parallel edges.
• A complete graph is where every vertex is adjacent to every other vertex in the graph.

Connectivity and Cycles

• A cycle exists when a path starts from a vertex and returns to the same vertex.
• An acyclic graph is a graph without any cycles.
• An isolated vertex has no edges connecting it to other vertices in the graph.
• The degree of a vertex is defined as the number of edges connected to it.
• In a digraph there are two types of degrees—indegree (number of edges incident into the vertex), and outdegree (number of edges emanating from the vertex).
• A pendant vertex is has indegree of 1 and outdegree of 0.
• Two vertices are said to be connected if there is a path between them. A graph is connected if there is a path between every pair of distinct vertices.
• A digraph is strongly connected if for every pair of vertices, there is a directed path from v; to vj and from vj to vi.
• In a digraph, if undirected the underlying graph is connected, then the digraph is weakly connected.

Limited Graph Varieties

• Main varieties of graphs are—directed, undirected, weighted and non-weighted graphs.

Graph Representation

• Graph representation methods include - set, linked, and sequential (matrix) representations.
• Set representation involves maintaining two sets – V (vertices) and E (edges). For a weighted graph, E is a set of three tuples (W, V, V), where W is the set of weights.
• In linked representation, there are two node structures: one for non-weighted, and one for weighted graphs
• Matrix representation uses of a square matrix to represent the graph.
• Matrix entries can be 1 or 0 to indicate connection; its useful for multigraph, and can be used for weighted graphs

Matrix Representation Details

• An adjacency matrix is a matrix representation of the graph where the value of aij = 1 if there is an edge from v; to vj, and 0 otherwise.
• An adjacency matrix is also referred to as bit matrix, or Boolean matrix.
• In a multigraph representation, the matrix entry indicates the number of edges between two vertices
• In a weighted graph, the entries are the weights of the edges.
• One of the disadvantages of using an adjacency matrix representation is that it still requires a n x n regardless, even with graphs with sparse connections

Graph Lemmas

• If A is the adjacency matrix of graph G, and A = AT (AT is the transpose of A), graph G is a simple undirected graph.
• If a graph is simple, all diagonal entries in its adjacency matrix are 0.
• The diagonal entries of A x AT from digraph G's adjacency matrix gives degrees, while AT x A gives indegrees of all vertices in G.
• AL that given the number of paths of length L from vi to vj, where AL is the Lth power matrix of A.
• In a simple digraph, length of any elementary path is less than or equal to n - 1 vertices.

Path Matrix Summary

• A path matrix (or reachability matrix) P indicates the existence of a path from vi to vj.
• In a path matrix, if there is a path = 1 to vj and 0 otherwise.
• For obtaining a path matrix, from its adjacency matrix determine if there is an from vi which there is immediate connection and edge.

Path Matrix Details

• Element in ith row and jth column of Bn are # of paths of length n with edges between v; to v; in the graph
• In path matrix [P], pij = 1 if there's non-zero event and one or more one path between a pair of points (and cycle at that same point)
• A vertex contains a cycle if the i, i entry in the path matrix P = 1.
• A graph is strongly connected if with V; and V; element in graph G; i,j entry and j,i entry in path matrix P are 1
• ith column of matrix [PT] give and show strong component + element

Graph Operations

• Possible operations on graph G are:

1. Insertion of vertex + connectivity w/ other vertices - can be integrated within current existing graph.
2. Insertion of edge between two vertices into current existing graph
3. Deletion of the vertex from the graph
4. Deletion of edge from within the graph
5. Merging the two graphs from each other on the individual graphs G1 and G2 + into one single graph only.
6. Traversal on a graph means visiting all of the vertices that is within the graph

Insertion of Vertex and Linked Structure

• Insertion of a vertex into a linked-structure graph involves adding a new vertex and establishing its connections.
• The procedure differs between directed (digraph) and undirected graphs.
• In an undirected graph, adding a vertex requires adding it to the adjacency lists of its neighbors and vice versa.
• In a digraph, the process depends on creating a path (adds a list), and vertex.

Matrix Representation of Graph Insertion

• To insert a vertex using matrix involves = adding a row / column - it must be a transpose + is a new matrix row and new column/ for all entries, is O or 1s if it is not direct.
• InsertEdge_AM_UG algorithm is where if it is used to represent adjacency, the two entries will be "ls".
• "DeleteVertex_AM", algorithm: Is a process involved with vertex to be a vertex to be removed.

Graph Traversals

• Graph traversal methods include breadth-first search (BFS) and depth-first search (DFS)-they both visit each node
• BFS is like a a "tree order" with which is from level to level
• DFS is similar to binary tree which in order goes w/ tree but in a way that nodes are deeper before level

Graph Algorithms (DFS & BFS) Summary:

• The DFS and BFS algorithm process has:
• Vertices added to stack (DFS)
• While the vertices in stack isnt fully opened they
• Pushes to adjacent vertices into array or visit array
• Once vertices have passed they will enter the visited status

A BDD Graph

• One way for a graph model is via a BDD graph (or more correctly decision, but graph wise graph)
• Before understanding let us go the notation system that BDD graph has

1. The "var (v)": Each Terminal vertex or "v" (vertices is listed by the variable, var)
2. The "Low (v)" For "V" ( vertices the edge which corresponds will always arc the labelled O
3. "High (v): which contains "V or vertices that indicated with which direction "arch labelled" 1 is
   • There are 3 ways in converting method 1: To remove terminals that duplicate others 2: Removing none terminals that duplicate others 3: Removing edges that redundant others.