Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    08 Graphs

    Uploaded by

    Dave Jedidiah Tibaldo
    This document defines basic concepts related to graphs, including directed and undirected graphs, vertices, edges, incidence, degree, paths, cycles, connected graphs, graph coloring, and chromatic number. It also introduces algorithms for finding shortest paths like Dijkstra's algorithm and discusses concepts like planar graphs and the four color theorem.

    Copyright:

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

    08 Graphs

    Uploaded by

    Dave Jedidiah Tibaldo
    32 views20 pages
    This document defines basic concepts related to graphs, including directed and undirected graphs, vertices, edges, incidence, degree, paths, cycles, connected graphs, graph coloring, and chromatic number. It also introduces algorithms for finding shortest paths like Dijkstra's algorithm and discusses concepts like planar graphs and the four color theorem.

    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?

    This document defines basic concepts related to graphs, including directed and undirected graphs, vertices, edges, incidence, degree, paths, cycles, connected graphs, graph coloring, and chromatic number. It also introduces algorithms for finding shortest paths like Dijkstra's algorithm and discusses concepts like planar graphs and the four color theorem.

    Copyright:

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

    08 Graphs

    Uploaded by

    Dave Jedidiah Tibaldo
    This document defines basic concepts related to graphs, including directed and undirected graphs, vertices, edges, incidence, degree, paths, cycles, connected graphs, graph coloring, and chromatic number. It also introduces algorithms for finding shortest paths like Dijkstra's algorithm and discusses concepts like planar graphs and the four color theorem.

    Copyright:

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

    GRAPHS

    BASIC CONCEPTS

    Definition of graph

    Undirected graph consists of a set V of vertices (or nodes) and a set E of edges (or arcs) such that each edge e E is associated with an unordered pair of vertices

    An edge e = (v, w) = (w, v) denotes an edge between v and w

    Directed graph consists of a set V of vertices (or nodes) and a set E of edges (or arcs) such that each edge e E is associated with an ordered pair of vertices

    An edge e = (v, w) denotes an edge from v to w

    BASIC CONCEPTS

    Incidence

    an edge e = (v, w) is incident on the vertices v and w, and v and w are incident on e; v and w are adjacent vertices
    an edge that is incident on a single vertex a vertex that is not incident on any edge distinct edges that are incident on the same pair of vertices

    Loop

    Isolated vertex

    Parallel edges

    BASIC CONCEPTS

    Degree of a vertex

    the number of edges incident on the vertex a loop on the vertex adds 2 to the degree of v contains neither parallel edges nor loops
    simple graph where there is an edge between every pair of distinct vertices denote Kn as a complete graph on n vertices

    Simple graph

    Complete graph

    BASIC CONCEPTS
    a b c f e a b c

    d
    g Undirected graph with a loop and parallel edges

    d Directed graph

    BASIC CONCEPTS
    a b c b a c

    d Simple graph

    e Complete graph: K5

    PATHS and CYCLES

    Path

    a path from a vertex v0 to a vertex vn (of length n) is an alternating sequence of n + 1 vertices and n edges starting from v0 and ending with vn.
    (v0, e1, v1, e2, v2, . . . , vn-1, en, vn)

    has no repeated edges but may have repeated vertices path with no repeated vertices graph with numbers on the edges the length of a path in the graph is the sum of the weights of the edges in the path

    Simple path

    Weighted graph

    PATHS and CYCLES

    Connected graph

    given any pair of vertices v and w in the graph, there is a path from v to w path of nonzero length from a vertex v to v has no repeated edges but may have repeated vertices cycle with no repeated vertices (except for the initial vertex cycle that includes all edges and all vertices in a graph

    Cycle (Circuit)

    Simple cycle

    Euler cycle

    PATHS AND CYCLES


    A

    SEVEN BRIDGES OF KNIGSBERG:


    Is there a way to go through the city such that each bridge is crossed exactly once?

    PATHS AND CYCLES

    Theorem

    The sum of the degrees of all the vertices in a graph with m edges = 2m. Corollary

    Any graph contains an even number of vertices of odd degree.

    Theorem

    A graph G has an Euler cycle iff G is connected and every vertex has an even degree. A connected graph has an Euler path (but not an Euler cycle) iff it has exactly 2 vertices of odd degree

    Theorem

    PATHS AND CYCLES

    Hamiltonian cycle

    cycle that contains each vertex in the graph exactly once If a graph G is connected, simple, has n 3 vertices and v deg(v) n/2, then G has a Hamiltonian circuit. Given a weighted graph G, find a minimum length Hamiltonian cycle. Euler cycle: O(n) algorithms exist (n-edge graph) Hamiltonian cycle: worst case algorithms require factorial or exponential time

    Travelling salesman problem

    Algorithm complexity

    PATHS AND CYCLES


    a b c f f d g h i g e c a d b e

    PATHS AND CYCLES

    PATHS AND CYCLES

    PATHS AND CYCLES

    Shortest path
    path having a minimum length between two vertices in a weighted graph

    Dijkstras algorithm

    determines the shortest path from vertex a to z w(i, j) is the weight of edge (i, j) L(x) is the label of a vertex x at termination, L(z) is the minimum length of the path from a to z

    PATHS AND CYCLES

    Dijkstras algorithm
    T = set of all vertices L(a) = 0 for all vertices x a L(x) = while z T choose v T with minimum L(v) T = T v for each x T adjacent to v L(x) = min( L(x), L(v) + w(v, x) )

    PATHS AND CYCLES


    Find the shortest path from a to z
    b
    2

    c
    2

    z
    2

    T = { a, b, c, d, e, z } T = { b, c, d, e, z } T = { b, c, e, z } T = { c, e, z } T = { c, z } T={c} L(a) = 0 L(b) = L(c) = L(d) = L(e) = L(z) =

    1
    d e
    1

    Answer: a d e z

    2 (a) 5 (b) 1 (a) 2 (d) 4 (e)

    PATHS AND CYCLES


    Find the shortest path from a to h T = { a, b, c, d, e, f , g, h }
    b
    2 2

    2
    4

    c
    3 1

    e
    7 6

    T = { b, c, d, e, f, g, h } T = { b, c, d, e, g, h } T = { c, d, e, g, h } T = { c, e, g, h } T = { e, g, h } T = { e, g }

    Answer: a b c h

    L(a) = 0 L(b) = 2(a) L(c) = 4(b) L(d) = 4(f)

    L(e) = L(f) = L(g) = L(h) =

    6(b) 1(a) 6(f) 5(c)

    GRAPH COLORING

    Graph coloring
    Let C = { c1, c2, . . . , cn } be a set of n colors. A coloring of the simple graph G using n colors is a function f: V C. For each vertex v, f(v) is the color of v. A coloring is proper if any two adjacent vertices have different colors. Chromatic number of a graph G

    smallest number of colors needed to produce a proper coloring of G Every planar graph is 4-colorable.

    Four-color Theorem

    GRAPH COLORING
    b 2 1 a e g
    2 3

    c 1
    2

    chromatic color : 3
    graph representation of a map

    You might also like