Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    File 1714029217 66059 Graph

    Uploaded by

    tarunsocsa

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    File 1714029217 66059 Graph

    Uploaded by

    tarunsocsa
    1 views15 pages

    Original Title

    file_1714029217_66059_Graph (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    1 views15 pages

    File 1714029217 66059 Graph

    Uploaded by

    tarunsocsa

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Graph

    Dr. Preeti Mittal


    IIMTU
    Graph
    ● A non linear data structure.
    ● comprising nodes (or vertices) connected by edges.
    ● Vertices, also known as nodes, represent distinct entities
    ● Edges are the lines or arcs that establish connections between any two
    nodes
    ● G=(E, V), where E is the set of edges and V is the set of vertices

    V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.


    This is a graph with 5 vertices and 6 edges.
    Examples:

    ● A map serves as a familiar illustration of a graph. Within a map, diverse


    connections exist between cities, typically facilitated by roads, railway
    lines, and aerial networks.
    ● Transportation Network
    ● Social Network
    ● Telephone Network
    ● Circuit Network
    Exercise:
    ● Ten people are seated around a circular table. Each person shakes hands with everyone at
    the table except the person sitting directly across the table. Draw a graph that models this
    situation.
    ● Six fraternity brothers (Adam, Bert, Chuck, Doug, Ernie, and Filthy Frank) need to pair
    off as roommates for the upcoming school year. Each person has compiled a list of the
    people with whom he would be willing to share a room.

    Adam’s list: Doug


    Bert’s list: Adam,
    Ernie Chuck’s list: Doug, Ernie
    Doug’s list: Chuck
    Ernie’s list: Ernie
    Frank’s list: Adam, Bert
    Draw a digraph that models this situation.
    Types of Edges

    Undirected Edge: An undirected edge is bidirectional, meaning that if there is


    an undirected edge between vertices A and B, then the edge (A, B) is
    equivalent to the edge (B, A).

    Directed Edge: A directed edge is unidirectional. If there is a directed edge


    from vertex A to vertex B, then the edge (A, B) is not equal to the edge (B, A).

    Weighted Edge: A weighted edge is an edge that carries a cost or weight


    associated with it.
    Types of Graph

    Undirected Graph Directed Graph

    Graph exclusively composed of A graph consisting solely of directed


    undirected edges edges
    Types of Graph Complete Graph

    Every node is adjacent to all other


    Weighted Graph nodes in the graph

    A graph is considered weighted In an undirected graph, the number


    when non-negative values are of edges is equal to n(n−1)/2, where
    assigned to each edge, representing n is the number of vertices.
    the length or cost between two
    vertices.
    Types of Graph
    Regular Graph

    A regular graph is characterized by nodes


    being adjacent to each other, ensuring Cycle Graph:
    accessibility from any node to any other
    A graph containing a cycle is called a
    node.
    cycle graph, where the first and last
    All vertices of graph G are of equal nodes in the cycle are the same. A
    degree. closed simple path defines a cycle.
    Types of Graph

    Acyclic Graph: Simple Graph:

    A graph lacking any cycles is A graph is identified as simple when


    referred to as an acyclic graph. it lacks parallel and self-loop edges.
    Properties:
    ● Degree of a Vertex: The total number of edges connected to a vertex is known as the
    degree of that vertex.
    ● Indegree of a Vertex: The total number of incoming edges connected to a vertex is
    denoted as the indegree of that vertex.
    ● Outdegree of a Vertex: The total number of outgoing edges connected to a vertex is
    designated as the outdegree of that vertex.
    ● Outgoing Edge: A directed edge is termed as an outgoing edge concerning its origin
    vertex.
    ● Incoming Edge: A directed edge is referred to as an incoming edge concerning its
    destination vertex.
    ● Parallel Edges or Multiple Edges: When two undirected edges share the same end
    vertices, or two directed edges have identical origins and destinations, such edges are
    termed parallel edges or multiple edges.
    ● Self-loop: An edge, whether undirected or directed, is considered a self-loop if its two
    endpoints coincide.
    General Terms:
    ● Adjacent Nodes: Nodes are deemed adjacent when there exists an edge connecting one node to
    another.
    ● Incidence: In an undirected graph, the edge between v1 and v2 is incident on nodes v1 and v2.
    ● Walk: A walk is defined as a finite alternating sequence of vertices and edges, commencing and
    concluding with vertices, such that each edge is incident with the vertices preceding and
    following it.
    ● Closed Walk: A walk that begins and ends at the same vertex is termed a closed walk; otherwise,
    it is an open walk.

    If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively


    ,then v1 e1 v2 e2 v4 e3 v3 e4 v1 be its closed walk or circuit.
    ●
    General Terms:
    ● Path: An open walk in which no vertex is repeated is termed a path. If e_1 and e_2
    represent the edges between the vertex pairs (v_1, v_3) and (v_1, v_2) respectively, then
    the sequence v_3, e_1, v_1, e_2, v_2 forms a path.
    ● Length of a Path: The count of edges in a path is referred to as the length of that path. In
    the given example, the path length is 3.
    ● Circuit: A closed walk in which no vertex, except the initial and final vertex, is repeated is
    known as a circuit. Illustrated is a circuit with three vertices and three edges.
    ● Subgraph: A graph S is considered a subgraph of another graph G if all the vertices and
    edges of S are in G , and each edge of S shares the same end vertices in both S and G .
    ● Connected Graph: A graph G is labeled as connected if there exists at least one path
    between every pair of vertices in G ; otherwise, G is termed disconnected.
    Graph Representation:

    Adjacency Matrix:
    ● a 2D array is used to store information about the edges between
    vertices.
    ● The entry at position (i, j) in the matrix indicates whether there is an edge
    between vertex i and vertex j.
    ● For an undirected graph, the matrix is symmetric, and for a weighted
    graph, the matrix may contain weights.
    Graph Representation:

    Adjacency List:
    ● Each vertex maintains a list of its adjacent vertices.
    ● This representation is suitable for sparse graphs where the number of
    edges is much less than the maximum possible edges.
    ● It saves space by only storing information about existing edges.

    You might also like