Graph Theory

Graph Theory
Published on 24 March, 2014
Graph theory is studying the connections/relation between entities to produce a model. A
basic graph contains vertices/nodes and edges that show the relation between them. they can
be used to visualise how a network (roads, cables, rooms/doors) is connected. Each graph
contains two finite sets of vertices and edges. Each edge contains a set of one or two vertices
which are its endpoints.
Definitions:
 Vertex – A node/entity.
 Edges – The connections between vertices.
 Proper Edge – An edge that connects two distinct vertices.
 Self Loop – An edge that connects a vertex to itself.
 Directed Edge – An edge that can only go in one direction.
 Arc – A directed edge.
 Head – The vertex that a directed edge is connected to.
 Tail – The vertex that a directed edge is connected from.
 Oppositely Directed Edges – Two directed edges that connect the same vertices, but
in opposing directions.
 Multi Edge – Set of two or more edges that have the same endpoints.
 Edge Multiplicity – The total number of edges within a multi edge set.
 Multi Arc – Set of two or more arcs that have the same head and tail.
 Arc Multiplicity – The total number of arcs within a multi arc set.
 Adjacent Vertices – Two vertices that are connected by an edge.
 Neighbor – A vertex that is connected to another vertex is said to be a neighbor of it.
 Degree – The total of proper edges, plus twice the number of self loops on a vertex.
 Valence – The degree of a vertex. [Often seen in chemistry for bond connections]
 Open Neighborhood – All of the vertices connected to a vertex. N(v). The result is a
subset of the graph. [Does not include the input vertex]
 Closed Neighborhood – Is the same as an open neighborhood but includes the input
vertex in the resulting set.
 Simple Graph – A graph that has no self loops or multi edges.
 Loopless Graph – A simple graph but can have multi edges.
 General Graph – A simple graph but can have multi edges and self loops.
 Null Graph – A graph that contains no vertices or edges.
 Trivial Graph – A graph that contains just one vertex, and no edges.
 Directed Graph – A graph where the each edge has a direction.
 Digraph – A directed graph.
 Simple Digraph – A digraph that has no self loops or multi arcs.
 Network – A graph that has weighted arcs.
 Mixed Graph – A Graph that has both directed and undirected edges.
 Underlying Graph – A directed or mixed graph, where the direction of an arc is
removed (but the edge is still kept).
 Isomorphic Graph – Two graphs that express the same data; even if they visually
look different.

 Adjacency Table – A matrix with a row for each vertex containing the list of
neighbors for that vertex.
Examples:
Here are a few examples of different kinds of graphs with labels of certain properties.
The above graph is an example of a simple graph with 5 Vertices, and 7 Edges.
The above graph is an example of a general graph with 5 Vertices, multiple Edges between
Vertices [B,E] and [D,C], and depending on the definition there are 10 or 11 tot edges in the
graph as Vertex[A] has a Self Loop.
Filed in Uncategorized | No replies