# D1 graph theory

definitions of terms

- 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.

edge, link, arc

Relationships represented in a graph. These are always rendered as straight or curved lines. The

term "arc" may be misleading.

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.

adjacent

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

## Comments

No comments have yet been made