© Copyright 2003 Herbert J. Bernstein

A **tree** is a **graph**. A **graph** is a collection of
**nodes**
connected to
one another by **edges**. If the edges have a direction, the graph is
called a **directed graph**. If the edges do not have a direction,
the graph is called an **undirected graph**. A path in a graph
is
a sequence of edges obeying the direction rules of the graph such
that the end node of each edge in the path (except for the last
edge in the path) is the start node of the next edge in the path.
A path is a circuit if the end node of the last edge of the path
is the start node of the first edge of the path. A graph is
called **connected** if there is a path from every node to every other
node.

One or more values (attribute-values) may be associated with each node of a graph.

One or more values (attribute-values) may be associated with each edge of a graph.

- A graph
*G*is:- A set of
**nodes***N*(also called**vertices**or**points**) - A set of
**edges***E*consisting of ordered pairs of nodes ( n_{1}, n_{2}) (also called**arcs****lines**).n

_{1}--------> n_{2}

- A set of
**Dual**of a graph exchanges nodes and edges- Operations
- Construct an empty graph or a graph from a list of nodes and a list of edges
- Count the nodes in a graph
- Count the edges in a graph
- Add a node to a graph
- Add an edge between two nodes
- Remove an edge from a graph
- Remove a node and all associated edges from a graph
- Link one graph to another at a common node
- Link one graph to another by an edge
- Remove a subgraph from a graph
- Associate a value or mark with a node
- Associate a value or mark wirh an edge
- Find a (shortest) path from a given node to another given node (length defined by number of edges or by sums of some non-negative edge values).
- Find a circuit from a node to itself
- Find the diameter of a graph (the maximum of all shortest paths)
- Find a cut between two nodes (a set of edges that will disconnect those nodes)
- Find a minimal cut between two nodes
- Find the capacity of a path (the mimimum value of a "capacity" value associated with each edge)
- Find the maximal flow between two nodes.

- Representations
- Adjacency Matrix
- Matrix of Booleans
- Each row and each olumn represents a node
- A true entry represents and edge from the row node to the column node
- Does not permit more than one edge between two nodes
- May be extended to provide values for edges

- Array of Adjacency Lists
- One entry in the array for each node
- Each entry is a list of nodes to which this node is connected

- List of Adjaceny Lists
- Dual-based versions of these representations

- Adjacency Matrix
- Shortest Path Algorithms
- Dijkstra's algorithm
- Shortest paths from a given node to all other nodes
- Greedy algorithm (add as many nodes as possible each time)
- Maintain a set
*X*of nodes for which the shortest path is known, and mark each member with the length of the shortest path from the starting node. - Start with the single starting node in set
*X* - Examine each of the nodes with edges to nodes in
*X*and compare the path lengths. - Add to
*X*those nodes for which the new path length is minimal. - Running time depends on the representation: O(card(N)
^{2}) for an adjacency matrix, O(card(E)log(card(N)) for an array of adjancency lists

- Dijkstra's algorithm

- A
**tree**is a directed, connected graph with only one path from any given node to any other node. - A
**rooted tree**is a tree with one distingushed node (the root) from which there is a path to every other node

root node /|\ / | \ / | \ / | \ a b c /\ | /|\ d e f g h i / \ \ \ \ \

In a **binary tree** each node as at most two children, and each
child has an attribute ("side") with the value "left" or "right".

A **trie** (from re**trie**val) is a tree structure to handle
searchable lists of character strings. The tree branches where
words with common roots differ:

root / a / \ l s / / \ l k s / \ \ \ . o . i \ \ w g \ \ . n \ .

A balanced tree has paths from the root to the leaf nodes of similar lengths. A 2-3 tree has interior nodes with 2 or 3 children each and every path from the root to a leaf is the same length.

For more on trees, see: