Skip to main content
Get your Wikispaces Classroom now:
the easiest way to manage your class.
Pages and Files
Trees, mathematical graphs and networks
Graphs - a mathematical mechanism for representing connectivity
Networks - interconnected items and the relationships between them
describes entities and how they are connected. The entities are called
and the connections are called
. They are a very general form of representation, that can be used to describe a wide variety of everyday things (and abstract things). Here are some examples:
By one definition, a
is a graph with non-trivial relationships and features
LIFE SCIENCES - METABOLIC PATHWAYS (See
Here is a visualization of the
Note that to fully represent graphs, we need methods of labeling and weighting both nodes and edges.
Question: How would you represent a social network as a graph?
a) What would be the nodes and what would be the edges?
b) What might you label and weight the edges with?
c) What questions might you want to use the graph to answer?
Facebook Open Graph
You can see several beautiful visualizations of a
social network at this flickr page
Scholarometer, a project here at IU, has a visualization of a
. Nodes represent disciplined, and edges represent related disciplined (if there are enough publications co-authored by researchers in those disciplines, for example)
Representing and processing graphs on computer
To understand graphs and how they can be represented, we will use the
. Important concepts are the
Pajek is a popular package for visualizing graphs, and the
pajek file format
is a popular format for storing graphs.
Check also the
tool from Indiana University
On the (Semantic) Web we can use
ontologies to describe valid relationships and nodes
Once we represent graphs, we can use them to solve problems using
algorithms. Generic kinds of problem include:
Finding the "best" path through a graph or a specific item in a graph (
) - see
Mapping one graph onto another (
Finding one graph inside another (
- see e.g.
Searching through graphs for particular nodes or combinations of nodes (
, and a
puzzle solving applet
). Look at this
for a demonstration on how to perform DFS and BFS on graphs.
Statistics based on node neighborhoods
As an example of Dijkstra's Algorithm we'll look at
a rail example
Some of these problems are generally
intractable or NP-Complete (or NP-Hard)
, meaning we usually have to use heuristics to solve them. For example, the
Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once
For a solution to this, see
Here is an applet
that computes an approximate solution for TSP.
Finding a path means we need a representation of a path too. This can be a
, or a graph representation of the path.
fully connected graph
has n*(n-1) / 2 edges
Special representations for trees
Sometimes when dealing specifically with
simple hierarchical tree structures
, we represent them in a different way based on the application. Technically, a tree is an acyclic graph, i.e. any one node will have a parent and/or children, but no other connections. For example, we may use a
. These can speed up operations such as Dijkstra's algorithm and sorting.
A novel way of visualizing hierarchical tree structures called
was developed by Schneiderman et al.
world as a tree map on this page
(image copied below).
help on how to format text
Turn off "Getting Started"