The next big step, graphs, can represent more then 3 dimensions. Graphs are used to represent many data structures ranging from airline routes to program code.
Illustrate: airlines and branching in programs
Types of graphs:
Hierarchical or dependence graphs
Maps, schematic or geographical graphs
Trees are graphs
A graph consists of:
A set, V, of vertices (nodes)
A collection, E, of pairs of vertices from V called edges (arcs)
Edges, also called arcs, are represented by (u, v) and are either:
Directed if the pairs are ordered (u, v)
u the origin
v
the destination
Undirected if the pairs are unordered
Then a graph can be:
Directed graph (di-graph) if all the edges are directed
Undirected graph (graph) if all the edges are undirected
Mixed graph if edges are both directed or undirected
Illustrate terms on graphs
End-vertices of an edge are the endpoints of the edge.
Two vertices are adjacent if they are endpoints of the same edge.
An edge is incident on a vertex if the vertex is an endpoint of the edge.
Outgoing edges of a vertex are directed edges that the
vertex is the origin.
Incoming edges of a vertex are
directed edges that the vertex is the destination.
Degree of a vertex, v, denoted deg(v)
is the number of incident edges.
Out-degree, outdeg(v),
is the number of outgoing edges.
In-degree, indeg(v),
is the number of incoming edges.
Parallel edges or multiple edges are edges of the
same type and end-vertices
Self-loop is an edge
with the end vertices the same vertex
Simple graphs have
no parallel edges or self-loops
Illustrate properties on graphs
If graph, G, has m edges then Σv∈G deg(v) = 2m
If a di-graph, G, has m edges then Σv∈G
indeg(v) = m = Σv∈G
outdeg(v)
If a simple graph, G, has m edges and n vertices:
If G is also directed then m ≤ n(n-1)
If G is also undirected then m ≤ n(n-1)/2
So a simple graph with n vertices has O(n2) edges at most
Path is a sequence of alternating vetches and edges such
that each successive vertex is connected by the edge.
Frequently only the vertices are listed especially if there are no
parallel edges.
Cycle is a path that starts and end at the
same vertex.
Simple path is a path with distinct vertices.
Directed path is a path of only directed edges
Directed
cycle is a cycle of only directed edges.
Sub-graph is a subset of vertices and edges.
Spanning
sub-graph contains all the vertices.
Connected graph has all pairs of vertices connected by at
least one path.
Connected component is the maximal
connected sub-graph of a unconnected graph.
Forest is a
graph without cycles.
Tree is a connected forest (previous
type of trees are called rooted trees, these are free trees)
Spanning tree is a spanning subgraph that is also a tree.
Illustrate new graphs terminology
If G is an undirected graph with n vertices and m edges:
If G is connected then m ≥ n - 1
If G is a tree then m = n - 1
If G is a forest then m ≤ n - 1
Illustrate on all graph example