CPSC 2120 - DAY 14
JUNE 3, 2016

================================================================================

GRAPHS
------

Traveling Salesman problem - he must travel to every city once and return home

A generic storage structure, no associated methods

NOT an ADT

REPRESENTING GRAPHS
-------------------

A generalization of trees
	-Nodes or verticies
	-Edges or arcs
Two kinds of graphs
	-Directed
	-Undirected

Directed Graphs - edges are arrows.  Show the flow from one node to the other

Undirected Graph - edges are lines, show relationship between two lines

(a) -> (b)  b is adjacent to a, NOT a is adjacent to b

A is a predecessor to node B
B is the successor of node A

Source of the edge is node A, the target is node B

Path - a sequence of verticies w_1, w_2, ... such that each vertex is unique
except that the path may start and end on the same vertex

length - is the number of edges along the path

Acyclic path - a path where each vertex is unique

Cyclic path - a path such that there are at least two verticies on the path

DAG - directed graph that has no cyclic paths

Complete graph - An undirected graph that has an edge between every pair of 
verticies.

Note - A directed graph can also be a complete graph; in that case, there
must be an edge from every vertex to every other vertex.

Undirected graph is connected if a path exists from every vertex to every other
vertex

A directed graph is strongly connected if a path exists from every vertex to
every other vertex

A directed graph is weakly connected if a path exists from every vertex to
every other vertex, disregarding the direction of the edge

WEIGHTED GRAPH
--------------

If a number is attatched to an edge, it has weight

Topological sort is a linear ordering of the verticies of a DAG in which
all successors of any given vertex appear in the sequence after that vertex

in-degree - number of lines going in a node
out-degree - number of lines going out of a node

To sort topolocically, consider the in-degrees

DAG must have at least one vertex with an in-degree of zero.

Adjacency Matrix - 

  A B C D E F <- DESTINATION
A   7
B         5
C 6 3   4   4
D   5
E     2 1
F         3

^
|
SOURCE

Symmetric matrix - if a diagonal is drawn and the numbers match on each side,
		then the graph is undirected

Look at the number of non-zero nodes in each column to determine adjacency