Graph Theory Introduction PDF

# Outline 1. History of Graph Theory 2. Basic Concepts of Graph Theory 3. Graph Representations 4. Graph Terminologies 5. Different Type of Graphs # Why Graph Theory? - Graphs used to model pairwise relations between objects. - Generally a network can be represented by a graph. - Many practical p...

# Outline 1. History of Graph Theory 2. Basic Concepts of Graph Theory 3. Graph Representations 4. Graph Terminologies 5. Different Type of Graphs # Why Graph Theory? - Graphs used to model pairwise relations between objects. - Generally a network can be represented by a graph. - Many practical problems can be easily represented in terms of graph theory. # Definition: Graph - A graph is a collection of nodes and edges. - Denoted by G = (V, E). - V = nodes (vertices, points). - E = edges (links, arcs) between pairs of nodes. - Graph size parameters: n = |V|, m = |E|. # Vertex & Edge - **Vertex / Node** - Basic Element - Drawn as a node or a dot. - Vertex set of G is usually denoted by V(G), or V or VG - **Edge /Arcs** - A set of two elements - Drawn as a line connecting two vertices, called end vertices, or endpoints. - The edge set of G is usually denoted by E(G), or E or EG - **Neighborhood** - For any node v, the set of nodes it is connected to via an edge is called its neighborhood and is represented as N(v). # Graph: Example The image shows a graph with 6 vertices, 7 edges. - n = 6, m = 7 - Vertices (V) :={1,2,3,4,5,6} - Edge (E) := {1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}} - N(4) := Neighborhood (4) ={6,5,3} # Edge Types: - **Undirected**: E.g., distance between two cities, friendships. - **Directed**: ordered pairs of nodes. E.g. Directed edges have a source (head, origin) and target (tail, destination) vertices. - **Weighted**: usually weight is associated. # Empty Graph / Edgeless Graph - No edge - **Null graph**: No nodes. Obviously no edge. The image shows an empty graph with six vertices, 1, 2, 3, 4, 5, and 6. # Directed Graph (Digraph) - Edges have directions - A != AT The image shows a directed graph with 5 vertices, 1, 2, 3, 4, and 5. Edges have arrows showing direction. There are two directed edges between vertex 1 and vertex 2, representing a "multiple arc" (one edge is going from vertex 1 to vertex 2, and the other is going from vertex 2 to vertex 1). There is a directed edge from vertex 3 to vertex 1, representing a "loop" (going from a vertex back to itself). The image also shows an "arc" between vertex 1 and vertex 2, an edge that is not a loop. # Weighted Graph - is a graph for which each edge has an associated weight. The image shows a weighted graph with two different examples. The first example is a directed graph with six vertices, numbered 1, 2, 3, 4, 5, and 6. The second example is an undirected graph, where the number of edges is shown on each edge. # Trees - An undirected graph is a tree if it is connected and does not contain a cycle (Connected Acyclic Graph). - Two nodes have exactly one path between them. The image shows two examples of trees. The first tree has 5 vertices numbered 1, 2, 3, 4, and 5. The second tree has 9 vertices numbered 1, 2, 3, 4, 5, 6, 7, 8, and 9. # Classification of Graph Terms - **Global terms** refer to a whole graph. - **Local terms** refer to a single node in a graph. # Connected and Isolated Vertex - Two vertices are connected if there is a path between them. - Isolated vertex - not connected. The image shows a graph with six vertices labeled 1, 2, 3, 4, 5, and 6, with vertex 4 being an isolated vertex. # Adjacent Nodes - **Adjacent nodes**: Two nodes are adjacent if they are connected via an edge. - If edge e={u,v} ∈ E(G), we say that u and v are adjacent or neighbors. - An edge where the two end vertices are the same is called a loop, or a self-loop. # Degree (Un Directed Graphs) - Number of edges incident on a node The image shows an undirected graph with 6 vertices labeled 1, 2, 3, 4, 5, and 6. Vertex 5 has a degree of 3 because it has 3 edges incident on it. # Degree (Directed Graphs) - In-degree: Number of edges entering - Out-degree: Number of edges leaving - Degree = indeg + outdeg The image shows a directed graph with five vertices labeled 1, 2, 3, 4, and 5. Vertex 1 has an out-degree of 2 and an in-degree of 0 because it has 2 edges leaving it and 0 edges entering it. Vertex 2 has an out-degree of 2 and an in-degree of 2 because it has 2 edges leaving it and 2 edges entering it. Vertex 3 has an out-degree of 1 and an in-degree of 4 because it has 1 edge leaving it and 4 edges entering it. # Walk - **trail**: No edge can be repeated (a-b-c-d-e-b-d). - **walk**: A path in which edges/nodes can be repeated (a-b-d-a-b-c) - A walk is closed is a=c. The image shows a graph labeled with letters a, b, c, d, e, and f. The image shows a trail a-b-c-d-e-b-d, where the edge (b,d) is repeated. It also shows a walk a-b-d-a-b-c, where the vertex b and the edge a-b are repeated. # Paths - **Path**: Is a sequence P of nodes V1, V2, ..., Vk-1, Vk. - No vertex can be repeated. - A closed path is called a cycle. - The length of a path or cycle is the number of edges visited in the path or cycle The image shows an undirected graph with 6 vertices labeled 1, 2, 3, 4, 5, and 6. It also shows different walks and paths in the graph. - 1,2,5,2,3,4 is a walk of length 5 because the edge (2,5) is repeated. - 1,2,5,2,3,2,1 is a walk of length 6 because the edge (2,5) and (2,3) are repeated. - 1,2,3,4,6 is a path of length 4 because all the edges are visited only once. # Cycle - Cycle - closed path: cycle (a-b-c-d-a), closed if x=y. - Cycles denoted by Ck, where k is the number of nodes in the cycle. The image shows three different cycles: - A cycle C3 with 3 vertices. - A cycle C4 with 4 vertices. - A cycle C5 with 5 vertices. # Shortest Path - **Shortest Path**: Is the path between two nodes that has the shortest length. - **Length**: Number of edges. - **Distance**: Between u and v is the length of a shortest path between them. - The **diameter** of a graph is the length of the longest shortest path between any pairs of nodes in the graph.