CmSc 250 Intro to Algorithms

Graph Algorithms - Basic Concepts
  1. Basic graph concepts
  2. Graph representation

Learning Goals
Exam-like questions

  1. Basic graph concepts

    2. A graph is a mathematical object that is used to model different situations – objects and processes:

    Linked list
    Tree (special type of graph
    Flowchart of a program
    Structure chart of a program
    Finite state automata
    City map
    Electric circuits
    Course curriculum

    1. Definition

      2. A graph is a collection (nonempty set) of vertices and edges

      Vertices: can have names and properties
      Edges: connect two vertices, can be labeled, can be directed

      Adjacent vertices: if there is an edge between them.

      Example:

      Vertices: A,B,C,D
      Edges:AB, AC, BC, CD

      Graph1:

      Same graph given in another way:

    2. Directed graphs and undirected graphs

      There are two basic types of graphs - directed and undirected.

      In undirected graphs the edges are symmetrical, e.g. if A and B are vertices,
      A B and B A are one and the same edge.
      Graph1 above is undirected.

      In directed graphs the edges are oriented, they have a beginning and an end.
      Thus A B and B A are different edges.
      Sometimes the edges of a directed graph are called arcs.

      Examples of directed graphs

      Graph2:

      Graph3:

      Graph2 and Graph3 are different graphs

      Some definitions of basic graph concepts differ slightly depending on whether we talk about directed or undirected graphs.

    3. Paths

      4. A path is a list of vertices in which successive vertices are connected by edges

      Examples

      Some paths in Graph1 :

      A B C D
      A C B A C D
      A B
      D C B
      C B A

      Some paths in Graph2:

      D A B
      A D A C

       Note that D A B is a path in Graph3, however A D A C is not a path in Graph3 because A C is not an edge (the edge is C A).

      Note: In different textbooks you may find different definitions for a path in a graph. Apart from the usual confusion, there is nothing wrong in this as long as the definitions are followed throughout the presented theory.

    4. Simple path No vertex is repeated.

      5. Examples:

      In Graph1, D C B A is a simple path, while D C B A C is not a simple path

      In Graph2, D A B is a simple path, while D A D B is not a simple path

    5. Cycles

       A cycle is a simple path with distinct edges,
      where the first vertex is equal to the last.

      6. Examples:

      Cycles in Graph1: C A B C, C B A C, A B C A, A C B A, B A C B, B C A B
      A B A is not a cycle, because the edge A B is the same as B A

      Cycles in Graph3: A D A, D A B D

      A graph without cycles is called acyclic graph

    6. Loop

      7. An edge that connects the vertex with itself

    7. Connected graphs

      8. Connected graph: There is a path between each two vertices

      Graph1, Graph2 and Graph3 are connected graphs.

      Disconnected graph: There are at least two vertices not connected by a path.

      Examples of disconnected graphs:

      Graph4

       

      Graph5

       

      Vertices:

      A,B,C,D

      Vertices:

      A,B,C,D

      Edges:

      AB, CD

      Edges:

      AB, AC

    8. Trees

      9. A tree is an undirected graph with no cycles and a vertex chosen
      to be the root of the tree.

      Note: in a tree, when we choose a root we impose an orientation.
      Given an acyclic graph, we may choose any node to be the root of a tree.

      Example

      Acyclic graph:

      If we choose vertex a to be the root, then we get the following tree:

      If we choose c to be the root, then the tree will be:

      Note also, that the graph does not specify the order of the children of a given node.

    9. A spanning tree of a graph

      10. A spanning tree of an undirected graph is a subgraph
      that contains all the vertices, and no cycles.
      If we add any edge to the spanning tree, it forms a cycle,
      and the tree becomes a graph.

      It is possible to define a spanning tree for directed graphs,
      however the definition is rather complicated and will not be discussed here.

      Example:

      Spanning trees for Graph1:

      A tree with N vertices has N-1 edges.
      A graph with less than N-1 edges is not connected.

    10. Complete graphs

      11. Graphs with all edges present – each vertex is connected to all other vertices,
      are called complete graphs.

      Example:

      Dense graphs: relatively few of the possible edges are missing
      Sparse graphs: relatively few of the possible edges are present

    11. Weighted graphs

      Weights are assigned to each edge (e.g. distances in a road map)

    12. Networks - directed weighted graphs

      13. Note: Some textbooks define networks to be undirected weighted graphs as well.

      Examples:

  2. Graph representation

    1. Adjacency matrix

      2. Vertices: A,B,C,D
      Edges: AB, AC, BD, CD

      

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0
      Note:
      • Depending on the application sometimes the diagonal is set to 1
      • For not directed graphs the matrix is symmetrical.
        Depending on the application only half of the matrix may be used.

    2. Adjacency list structure
      3.

      Each vertex is associated with a list, that holds all adjacent vertices.

      A: B, C
      B: A, D
      C: A, D
      D: B, C

      Other information, as weights, labels, names, can be represented using auxiliary arrays.

Learning Goals

  • Know the basic graph concepts (undirected and directed graphs, pats, simple paths, cycles, connected and disconected graphs, complete graphs, weighted graphs, networks.)
  • Know how graphs are represented by a matrix and by adjacency lists

Exam-like questions

  1. Given an undirected graph, described with the set of vertices and the set of edges,
    • Draw the picture of the graph
    • Give an example of a path, a simple path, a cycle
    • Determine whether the graph is connected or disconnected
    • Give the matrix representation of the graph
    • Give the adjacency lists reprsentation of the graph

  2. Given a directed graph, described with the set of vertices and the set of edges,
    • Draw the picture of the graph
    • Give an example of a path, a simple path, a cycle
    • Determine whether the graph is connected or disconnected
    • Give the matrix representation of the graph
    • Give the adjacency lists reprsentation of the graph
Back to Contents page
Created by Lydia Sinapova