[Term] Graph Theory

• Graph theory is a branch of discrete mathematics that study the relationship between objects. These objects are called vertices or node that are joined by edges or link/arc.
• A graph G = {V , E } consists of V , a non-empty set of vertices (or nodes), and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints.
• Vertex (Node): A fundamental unit of a graph.
• Edge (Link/Arc): A connection between two vertices.
• Undirected Graph: Edges have no direction.
• Directed Graph (Digraph): Edges have a direction.
• Weighted Graph: Edges have a numerical value (weight/cost) associated with them.
• Unweighted Graph: Edges have no associated value.
• Loop: An edge that connects a vertex to itself.
• Parallel Edges (Multiple Edges): More than one edge connecting the same pair of vertices.
• Simple Graph: A graph with no loops and no parallel edges.
• The dots are called vertices or nodes. V = set of vertices = {1, 2, 3, 4, 5}
• The connection between vertices or nodes are called the edges or link/arc. It is also called as adjacent.
• E = {{1,2}, {2,3}, {2,5}, {3,4}, {3,5}, {4,5}} //edge sets
• Graph is a collection of vertices and edges.
• The neighborhood of a v vertex is the set of all vertices adjacent to v. NG(2) = {1, 3, 5}
• The degree of a vertex is the number of edges on it. d(1) = 1; d(2) = 3; d(3) = 3; d(4) = 2; d(5) = 3 Sum = 1 + 3 + 3 + 2 + 3 = 12
• Adjacency Matrix represents a graph in a table form, containing a row and column for each vertex.
• Adjacency List represents the collection of unordered lists where each list corresponds to a vertex.
• What is in the picture?

  A) Directed Graph

  B) Directed Graph

  
• What is in the picture?

  A) Weighted Undirected Graph

  B) Weighted Undirected Graph

  C) neighbor vertex, weight

  
• What is in the picture?

  A) Weighted Directed Graph

  B) Weighted Directed Graph

  C) destination vertex, weight