Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    GT Unit 1 and 2

    Uploaded by

    iamsorryabhu0406
    The document discusses graphs and graph theory concepts like isomorphism, connected and disconnected graphs, walks, paths, circuits, trees, spanning trees, minimum spanning trees, and algorithms for finding minimum spanning trees like Kruskal's algorithm and Prim's algorithm.

    Copyright:

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

    GT Unit 1 and 2

    Uploaded by

    iamsorryabhu0406
    11 views47 pages
    The document discusses graphs and graph theory concepts like isomorphism, connected and disconnected graphs, walks, paths, circuits, trees, spanning trees, minimum spanning trees, and algorithms for finding minimum spanning trees like Kruskal's algorithm and Prim's algorithm.

    Original Title

    GT unit 1 and 2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses graphs and graph theory concepts like isomorphism, connected and disconnected graphs, walks, paths, circuits, trees, spanning trees, minimum spanning trees, and algorithms for finding minimum spanning trees like Kruskal's algorithm and Prim's algorithm.

    Copyright:

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

    GT Unit 1 and 2

    Uploaded by

    iamsorryabhu0406
    The document discusses graphs and graph theory concepts like isomorphism, connected and disconnected graphs, walks, paths, circuits, trees, spanning trees, minimum spanning trees, and algorithms for finding minimum spanning trees like Kruskal's algorithm and Prim's algorithm.

    Copyright:

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

    Unit 1

    Isomorphism

    Fig.(i), (ii) (iii) Isomorphic pair of graphs


    CONNECTED AND DISCONNECTED GRAPHS

    Fig. 30.
    subgraph
    Euler Graph - A connected graph G is called an Euler graph, if there is a closed
    trail which includes every edge of the graph G.
    Walk
    Path : If no vertex of the x-y walk occurs more than once, then the walk is called a x-y path.
    Path

    circuit
    Travelling Salesman Problem (TSP) : Given a set of cities and distances
    between every pair of cities, the problem is to find the shortest possible route
    that visits every city exactly once and returns to the starting point.
    For example, consider the graph shown in the figure
    . A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15
    which is 80.
    Unit 2
    Trees, Circuits and Cut-sets
    ROOTED TREE

    Fig. A rooted tree.

    Co tree
    The cotree T* of a spanning tree T in a connected graph G is the spanning subgraph of G
    containing.exactly those edges of G which are not in T. The edges of G which are not in T* are
    called its twigs.

    BINARY TREES
    Fig. 13-vertices, 4-level binary tree.
    Spanning Trees In A Weighted Graph,
    Algorithm For Shortest Spanning Tree

    There are two Algorithm to find Minimum Spanning Tree

    1. Kruskal's Algorithm
    2. Prim's Algorithm

    Prim’s Algorithm for Minimum Spanning Tree


    (MST)

    Prim’s algorithm is also a Greedy algorithm.


    This algorithm always starts with a single node and moves through several
    adjacent nodes, in order to explore all of the connected edges along the way.
    The algorithm starts with an empty spanning tree.
    The idea is to maintain two sets of vertices. The first set contains the vertices
    already included in the MST, and the other set contains the vertices not yet
    included. At every step, it considers all the edges that connect the two sets
    and picks the minimum weight edge from these edges. After picking the edge,
    it moves the other endpoint of the edge to the set containing MST.
    A group of edges that connects two sets of vertices in a graph is called cut in
    graph theory. So, at every step of Prim’s algorithm, find a cut, pick the
    minimum weight edge from the cut, and include this vertex in MST Set (the set
    that contains already included vertices).
    working of Prim’s algorithm can be described by using the following steps:
    Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
    Step 2: Follow steps 3 to 5 till there are vertices that are not included in the
    MST (known as fringe vertex).
    Step 3: Find edges connecting any tree vertex with the fringe vertices.
    Step 4: Find the minimum among these edges.
    Step 5: Add the chosen edge to the MST if it does not form any cycle.
    Step 6: Return the MST and exit
    0 is selected as starting vertex

    1 is added to the MST


    In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then
    it keeps on adding new edges and nodes in the MST if the newly added edge
    does not form a cycle. It picks the minimum weighted edge at first and the
    maximum weighted edge at last. Thus we can say that it makes a locally optimal
    choice in each step in order to find the optimal solution. Hence this is a Greedy
    Algorithm.

    steps for finding MST using Kruskal’s algorithm:

    1. Sort all the edges in non-decreasing order of their weight.


    2. Pick the smallest edge. Check if it forms a cycle with the spanning
    tree formed so far. If the cycle is not formed, include this edge. Else,
    discard it.
    3. Repeat step#2 until there are (V-1) edges in the spanning tree.
    Without 'g', there is no path between vertex 'c' and vertex 'h' and many other.
    Hence it is a disconnected graph with cut vertex as 'e'. Similarly, 'c' is also a cut
    vertex for the above graph.

    You might also like