Scribd Logo
Upload

Welcome to Scribd!

  • 365 views

    Graph Theory Final

    Uploaded by

    Jit Saha
    The document discusses graph theory and its applications. It begins with a brief history of graph theory and introduces basic concepts like vertices, edges, order and size. It then outlines several applications of graph theory in computer science, chemistry, operations research and biological science. In computer science, graphs are used in data structures, algorithms, operating systems, databases, compiler design, networking and security. In operations research, graphs model problems in linear programming, project planning and game theory. Biological applications include modeling DNA sequencing and the spread of disease. The document concludes with references for further reading.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Graph Theory Final

    Uploaded by

    Jit Saha
    365 views24 pages
    The document discusses graph theory and its applications. It begins with a brief history of graph theory and introduces basic concepts like vertices, edges, order and size. It then outlines several applications of graph theory in computer science, chemistry, operations research and biological science. In computer science, graphs are used in data structures, algorithms, operating systems, databases, compiler design, networking and security. In operations research, graphs model problems in linear programming, project planning and game theory. Biological applications include modeling DNA sequencing and the spread of disease. The document concludes with references for further reading.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses graph theory and its applications. It begins with a brief history of graph theory and introduces basic concepts like vertices, edges, order and size. It then outlines several applications of graph theory in computer science, chemistry, operations research and biological science. In computer science, graphs are used in data structures, algorithms, operating systems, databases, compiler design, networking and security. In operations research, graphs model problems in linear programming, project planning and game theory. Biological applications include modeling DNA sequencing and the spread of disease. The document concludes with references for further reading.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    365 views24 pages

    Graph Theory Final

    Uploaded by

    Jit Saha
    The document discusses graph theory and its applications. It begins with a brief history of graph theory and introduces basic concepts like vertices, edges, order and size. It then outlines several applications of graph theory in computer science, chemistry, operations research and biological science. In computer science, graphs are used in data structures, algorithms, operating systems, databases, compiler design, networking and security. In operations research, graphs model problems in linear programming, project planning and game theory. Biological applications include modeling DNA sequencing and the spread of disease. The document concludes with references for further reading.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 24

    Graph Theory & its application

    Presented by Jit Saha M.Tech CSE 1st year

    03/05/12

    jit saha-KGEC

    Content
    1. 2. 3. 4. History of graph theory Elementary concepts Applications Reference

    03/05/12

    jit saha-KGEC

    1.History of graph theory


    Leonhard Euler's paper on Seven Bridges of Knigsberg , published in 1736.

    walk about the city so ,cross each bridge once & return to the starting point.
    Content
    03/05/12 jit saha-KGEC 3

    1.History of graph theory-contd


    Cycles in Polyhedra

    Content
    03/05/12 jit saha-KGEC 4

    1.History of graph theory-contd


    Four Colors of Maps

    Content
    03/05/12 jit saha-KGEC 5

    2.Elementary concepts
    G(V,E) ,two sets of objects
    Vertices (or nodes) ,set V Edges, set E

    Represented with circles joined by lines |V|=order of graph |E|=size of graph

    For the above simple directed graph, V={A,B,C,D} E={AB,BD,CD,AC,AD,BC} |V|=4 |E|=6 Content

    03/05/12

    jit saha-KGEC

    3.Applications
    I. Computer Science II. Chemistry III. Operation Research IV. Biological science V. Other application

    Content
    03/05/12 jit saha-KGEC 7

    I. Computer Science
    Data structure & Algorithm design Operating system DBMS Compiler design Computer networking & network security
    Content

    Application
    03/05/12 jit saha-KGEC 8

    Data structure & Algorithm design


    Serve as data structure Foundation of different algorithm Performance measurement
    Time complexity Space complexity

    Content

    Application
    03/05/12 jit saha-KGEC 9

    Operating system
    Modeling operating system Defining file structure Deadlock handling Defining storage structure Process scheduling
    Content Application
    03/05/12 jit saha-KGEC 10

    operating system-contd

    Content Application
    03/05/12 jit saha-KGEC 11

    DBMS
    Defining relation model ER diagram designing SQL Query optimization Transaction processing
    Precedence graph

    Content
    03/05/12 jit saha-KGEC

    Application
    12

    Compiler design
    Syntax tree construction Semantic checking Code optimization
    By DAG

    Graph coloring in register optimization


    Content Application
    03/05/12 jit saha-KGEC 13

    Compiler design-contd
    d=a+b f=b/c g=a+b f=c+d d=f+c
    DAG representation

    Graph coloring in register allocation


    Content

    Application
    03/05/12 jit saha-KGEC 14

    computer networking & network securuty


    Defining n/w topology path costs computation
    Routing protocols use shortest path algorithms

    In multicast routing protocol


    Content

    Application
    03/05/12 jit saha-KGEC 15

    computer networking & network securutycontd


    simulate propagation of worms
    vertices are routing servers edges are the links Basec on minimum vertex cover property

    finding the worm propagation

    vertex Set g={2,4,5} covers all the vertices in G Content

    Application
    03/05/12 jit saha-KGEC 16

    Other Computer Science application


    Search engine optimization Parallel algorithm solving software Engineering FSM model Computer architecture
    content

    application
    03/05/12 jit saha-KGEC 17

    II. Chemistry
    Structural representation of molecule Enumeration Chemical Isomers acyclic compounds are trees

    Content application
    03/05/12 jit saha-KGEC 18

    III. Operation research


    Solving LPP by graphical method Estimating project activity
    PERT & CPM

    In Game Theory
    Using tree

    content application
    03/05/12 jit saha-KGEC 19

    III. Operation research-contd

    content Game tree structure


    03/05/12 jit saha-KGEC

    Pert &CPM

    application
    20

    IV. Biological Science


    statistical theory of biological networks In DNA Sequencing
    ATC TCG CAT GCA GGC GGC AGG GAA CGA GAC

    Example -ATCGACTATAAGGC ATCGAA


    ACT
    CTA

    TAT

    ATA TAA AAG

    content

    application
    03/05/12 jit saha-KGEC 21

    IV. Biological Science-contd


    Spread and Control of Disease through Social Networks
    Social Network = Graph Vertices = People Edges = contact
    content

    application
    03/05/12 jit saha-KGEC 22

    V. Other application
    Utilities problem Electrical network problem Bus-trail network Pedigree(family tree) Telephone network systems
    content

    application
    03/05/12 jit saha-KGEC 23

    4. Reference
    Books
    Graph Theory with Applications to Engineering and Computer Science by Narsingh Deo Discrete Mathematics and Its Applications by Kenneth H. Rose

    URL

    http://en.wikipedia.org/wiki/Graph_theory http://mathworld.wolfram.com/GraphTheory.html http://www.britannica.com/EBchecked/topic/242012/graph-theory

    03/05/12

    jit saha-KGEC

    24

    You might also like