Scribd Logo
Upload

Welcome to Scribd!

  • 50 views

    Assignment 4 (Aradhy Ranade)

    Uploaded by

    Aradhy
    The document discusses different types of graphs and graph algorithms. It defines directed and undirected graphs, connected and unconnected graphs, and adjacent and incident vertices. It also provides examples of an adjacency matrix and adjacency list representation of a graph and explains Prim's and Kruskal's minimum spanning tree algorithms in steps.

    Copyright:

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

    Assignment 4 (Aradhy Ranade)

    Uploaded by

    Aradhy
    50 views4 pages
    The document discusses different types of graphs and graph algorithms. It defines directed and undirected graphs, connected and unconnected graphs, and adjacent and incident vertices. It also provides examples of an adjacency matrix and adjacency list representation of a graph and explains Prim's and Kruskal's minimum spanning tree algorithms in steps.

    Original Description:

    G

    Original Title

    Assignment 4 ( Aradhy ranade)

    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 different types of graphs and graph algorithms. It defines directed and undirected graphs, connected and unconnected graphs, and adjacent and incident vertices. It also provides examples of an adjacency matrix and adjacency list representation of a graph and explains Prim's and Kruskal's minimum spanning tree algorithms in steps.

    Copyright:

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

    Assignment 4 (Aradhy Ranade)

    Uploaded by

    Aradhy
    The document discusses different types of graphs and graph algorithms. It defines directed and undirected graphs, connected and unconnected graphs, and adjacent and incident vertices. It also provides examples of an adjacency matrix and adjacency list representation of a graph and explains Prim's and Kruskal's minimum spanning tree algorithms in steps.

    Copyright:

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

    Ans 1)

    a) Directed and undirected Graph


    Undirected graphs have edges that do not have a direction. The edges indicate a two-way
    relationship, in that each edge can be traversed in both directions. This figure shows a simple

    undirected graph with three nodes and three edges.


    Directed graphs have edges with direction. The edges indicate a one-way relationship, in that
    each edge can only be traversed in a single direction. This figure shows a simple directed graph
    with three nodes and two edges.

    b) Connected and unconnected Graph


    A connected graph is a graph in which it's possible to get from every vertex in the graph to every
    other vertex through a series of edges, called a path.
    A graph that is not connected is disconnected. An undirected graph G is said to be
    disconnected if there exist two nodes in G such that no path in G has those nodes as
    endpoints. A graph with just one vertex is connected. An edgeless graph with two or
    more vertices is disconnected.

    c) Adjacent and Incident Vertices


    In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by
    an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all
    vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges
    connecting vertices adjacent to v.

    Two edges are called incident, if they share a vertex. Also, a vertex and an edge are
    called incident, if the vertex is one of the two vertices the edge connects.

    Ans 2) Adjacency metrices


    Austin 0

    Dallas 1

    Denver 2

    Washington 3

    Atlanta 4

    Houston 5

    Chicago 6

    0 1 2 3 4 5 6

    0 0 200 0 0 0 160 0

    1 200 0 780 0 0 0 900

    2 0 0 0 0 140 0 100
    0 0

    3 0 1300 0 0 600 0 0

    4 0 0 0 600 0 800 0

    5 0 0 0 0 800 0 0

    6 0 0 100 0 0 0 0
    0

    Adjency list

    Vertices Adjacent vertices

    Austin Dallas, Houston


    Dallas Autin,Denver

    Denver Arlanta,Chicago

    Washington Dallas, Atlanta

    Atlanta Washington, Houston

    Houston Atlanta

    Chicago Denver

    Ans 3) prims algorithm

    Steps

    (i) A
    4
    (ii). A-----------B

    4. 3
    (iii). A-----------B-----------D

    4. 3. 3
    (iv) A-----------B-----------D-------------C

    4. 3. 3. 3
    (v). A-----------B-----------D-------------C-----------F

    Kruskals method

    Steps

    3
    (i). F--------C
    3. 3
    (ii). F---------C-------------D

    3. 3. 3
    (iii). F---------C-------------D-------------B

    (iv) 3. 3. 3. 4
    F---------C-------------D-------------B-------------A

    You might also like