Lecture Notes for CS 512, Algorithm Design

Graphs - 19 January 2000

These are provisional lecture notes, expect changes.

  1. Graphs

    1. What is a graph?

      1. a set of nodes or vertices

      2. a set of edges or arcs between nodes

      3. directed or undirected edges (graphs)

      4. vertices - in, out degree;

      5. edges - adjacency, head, tail, incident from, incident to, leaves, enters, neighbor, weight

      6. paths - length, reachable, simple, subpath, cycle, acyclic

      7. connected, strongly connected

      8. subgraph, induced graph, complete graph, forrest, tree, dag

    2. Widely used as models - nodes represent things, edges represent relations between things; road maps, work-flow diagrams

      1. a huge body of knowledge dealing with graphs

  2. graph representations

    1. adjacency list

    2. adjancy matrix

  3. graph algorithms

    1. given a graph, find a subgraph - tsp, shortest path

    2. given a bunch of nodes and a relation for arcs, draw a graph satisfying some properties - resource allocation, scheduling

This page last modified on 31 January 2000.