# D1 graph theory

definitions of terms

HideShow resource information
• Created by: Nicola
• Created on: 24-06-10 01:37

First 498 words of the document:

Graph Theory:
graph, network
An abstraction of relationships among objects. Graphs consist exclusively of nodes and edges.
diagram, drawing
A visible rendering of the abstract concept of a graph.
point, node, vertex
Objects ("things") represented in a graph. These are almost always rendered as round dots.
Relationships represented in a graph. These are always rendered as straight or curved lines. The
unidentified, unlabeled
Nodes or edges which are not considered as individuals. Only the way in which they connect to
the rest of the graph characterize unidentified nodes and edges.
undirected
A graph that represents a symmetric, transitive relationship between nodes. Its edges are
rendered as plain lines or arcs.
directed, digraph
A graph that represents an asymmetric, nontransitive relationship between nodes. Its edges are
rendered with an arrowhead at one end of a line or arc.
unweighted
A graph is unweighted if all the relationships symbolized by edges are considered equivalent.
Such edges are rendered as plain lines or arcs.
Weighted, network
Weighted edges symbolize relationships between nodes which are considered to have some
value, for instance, distance or lag time. Such edges are usually annotated by a number or
letter placed beside the edge. A weighted graph is a network.
Two edges are adjacent if they have a node in common two nodes are adjacent if they have an
edge in common. Adjacency/ incidence matrix list the number of edges between all vertices.
regular
A graph is regular if every node has the same degree.
Degree, order
The number of edges connected to a vertex
complete
A graph is complete if every node is linked to every other node. With n(n1)/2 edges. For a
complete digraph, this means one link in either direction.
route
A sequence of edges and nodes from one node to another. Any given edge or node might be
used more than once.
path
A route that does not pass any edge more than once. If the path does not pass any node more
than once, it is a simple path. A simple graph has no loops or multiple edges connecting 2
vertices
connected
If some route exists from every node to every other, the graph is connected. Note that some
graphs are not connected. A diagram of an unconnected graph may look like two or more
unrelated diagrams, but all the nodes and edges shown are considered as one graph.
loop, cycle
A path which ends at the node where it began.
tree
A connected graph with no loops. Spanning tree connects all vertices. Minimum spanning tree
connects all vertices with min. Length.
Eulerian path

## Other pages in this set

### Page 2

Here's a taster:

A path which passes through every edge (once and only once). If the starting and ending nodes
are the same, it is an Euler cycle or an Euler circuit. If the starting and ending nodes are
different, it is an Euler trail. An Euleurian graph has no odd vertices (traversable)
Hamiltonian path
A path which passes through every node once and only once. If the starting and ending nodes