Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    Introduction To Graph Theory

    Uploaded by

    DNA barath
    This document is a lecture on graph theory and applications given by Dr. Lisna P C from the Department of Mathematics at VIT-AP University on February 3, 2021. It introduces basic concepts in graph theory such as vertices, edges, degrees of vertices, graph coloring, and chromatic number. It also discusses applications of graph coloring in scheduling, register allocation, and map coloring.

    Copyright:

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

    Introduction To Graph Theory

    Uploaded by

    DNA barath
    21 views19 pages
    This document is a lecture on graph theory and applications given by Dr. Lisna P C from the Department of Mathematics at VIT-AP University on February 3, 2021. It introduces basic concepts in graph theory such as vertices, edges, degrees of vertices, graph coloring, and chromatic number. It also discusses applications of graph coloring in scheduling, register allocation, and map coloring.

    Original Title

    Introduction to Graph Theory (2)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is a lecture on graph theory and applications given by Dr. Lisna P C from the Department of Mathematics at VIT-AP University on February 3, 2021. It introduces basic concepts in graph theory such as vertices, edges, degrees of vertices, graph coloring, and chromatic number. It also discusses applications of graph coloring in scheduling, register allocation, and map coloring.

    Copyright:

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

    Introduction To Graph Theory

    Uploaded by

    DNA barath
    This document is a lecture on graph theory and applications given by Dr. Lisna P C from the Department of Mathematics at VIT-AP University on February 3, 2021. It introduces basic concepts in graph theory such as vertices, edges, degrees of vertices, graph coloring, and chromatic number. It also discusses applications of graph coloring in scheduling, register allocation, and map coloring.

    Copyright:

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

    MAT2011 Graph Theory and Applications

    Dr. Lisna P C

    Assistant Professor
    Department of Mathematics
    School of Sciences and Languages
    VIT-AP University

    February 3, 2021

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 1 / 19
    Introduction to Graphs
    A graph G is a finite nonempty set V of objects called vertices
    together with a set E of 2-element subsets of V called edges.
    Vertices are sometimes called points or nodes, while edges are
    sometimes referred to as lines or links.
    Each edge {u, v} of V is commonly denoted by uv or vu.
    If e = uv, then the edge e is said to join u and v.
    The number of vertices in a graph G is the order of G and the
    number of edges is the size of G. We often use n for the order of a
    graph and m for its size.
    To indicate that a graph G has vertex set V and edge set E, we
    sometimes write G = (V, E). To emphasize that V is the vertex set
    of a graph G, we often write V as V(G). For the same reason, we
    also write E as E(G).
    A graph of order 1 is called a trivial graph and so a nontrivial
    graph has two or more vertices. A graph of size 0 is an empty
    graph and so a nonempty graph has one or more edges.
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 2 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 3 / 19
    If uv is an edge of G, then u and v are adjacent vertices. Two
    adjacent vertices are referred to as neighbors of each other.
    The vertex u and the edge uv are said to be incident with each
    other. Similarly, v and uv are incident.
    The degree of a vertex v in a graph G is the number of vertices in
    G that are adjacent to v. Thus the degree of a vertex v is the
    number of the vertices in its neighborhood N (v)
    A vertex of degree 0 is referred to as an isolated vertex and a
    vertex of degree 1 is an end-vertex or a leaf. An edge incident with
    an end-vertex is called a pendant edge.
    The largest degree among the vertices of G is called the maximum
    degree of G is denoted by ∆(G). The minimum degree of G is
    denoted by δ(G).
    If v is a vertex of a graph G of order n, then
    0 ≤ δ(G) ≤ deg(G) ≤ ∆(G) ≤ n − 1

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 4 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 5 / 19
    Introduction to Graph Coloring

    A proper vertex coloring of a graph G is an assignment of colors to


    the vertices of G, one color to each vertex, so that adjacent vertices
    are colored differently. The positive integers (typically 1,2,...,k, for
    some positive integer k) are commonly used for the colors.
    A proper coloring can be considered as a function c : V (G) −→ N
    (where N is the set of positive integers) such that c(u) 6= c(v) if u
    and v are adjacent in G. If each color used is one of k given colors,
    then we refer to the coloring as a k-coloring.
    Suppose that c is a k-coloring of a graph G, where each color is
    one of the integers 1,2,...,k, as mentioned above. If Vi (1 ≤ i ≤ k) is
    the set of vertices in G colored i (where one or more of these sets
    may be empty), then each nonempty set Vi is called a color class
    and the nonempty elements of {V1 , V2 , ..., Vk } produce a partition
    of V(G).

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 6 / 19
    Chromatic number of a graph G

    A graph G is k-colorable if there exists a coloring of G from a set


    of k colors. In other words, G is k-colorable if there exists a
    k-coloring of G. The minimum positive integer k for which G is
    k-colorable is the chromatic number of G and is denoted by χ(G).
    (The symbol χ is the Greek letter chi.)

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 7 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 8 / 19
    For any graph G with n vertices, 1 ≤ χ(G) ≤ n

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 9 / 19
    Some bounds for the chromatic number

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 10 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 11 / 19
    Applications of Coloring

    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 12 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 13 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 14 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 15 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 16 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 17 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 18 / 19
    Dr. Lisna P C (VIT-AP University) MAT2011 Graph Theory and Applications February 3, 2021 19 / 19

    You might also like