in Network

Graph Theory – The Basics of Networks

What is a Network?

You can see a network as a graph. You can see a graph as a set of nodes joined by a set of lines or arrows.

Graphs

Graph-based representations

When a problem occurs, it may help you see another point of view using a graph. It may simplify the said problem. In other words: it can provide the appropriate tools for solving the problem.

 

Definition: Graph

G is an ordered graph G=(V, E)

  • V is a set of nodes, points, or vertices (singularity is vertex). It’s a basic element and is drawn as a node or dot.
  • E is a set whose elements are known as edges or lines. It’s a set of two elements and is drawn as a line connecting two vertices, called end vertices or endpoints.

Example:

We will use the picture in paragraph ‘What is a Network’ for this example.

We need to define V, E and the whole graph, G.

 

The answers would be:

V = {1,2,3,4,5,6}

E = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }

G= {{1,2,3,4,5,6}, { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } }

We use subsets to note the answers.

 

Directed Graph

All edges have directions and an edge is an ordered pair of nodes. Below you see 4 names. An arc is the arrow or connection between 1 node to another. A multiple arc means that there are more lines (arcs) going to a single edge or node. A loop means its start and finish is both the same edge. Then you have the node, which is just another name for edge.

Directed Graph

A Simple Graph is a graph without multiple edges or self-loops.

A Weighted Graph is a graph where each edge has an associated weight, usually given by a weight function.

An Empty Graph / Edgeless Graph is a graph without edges.

A Null Graph is a graph with no nodes, and no edges. So basically nothing.

 

A Degree is the number of edges incident on a node. In the above image Node 5 would have degree 3. You have 2 degrees: the In-degree and the Out-degree.

  • In-degree: Number of edges entering
  • Out-degree: Number of edges leaving

When we take the image above we would have the following answers:

  • outdeg(1)=2
  • indeg(1)=0
  • outdeg(2)=2
  • indeg(2)=2
  • outdeg(3)=1
  • indeg(3)=4

You can also say: Degree = indeg + outdeg

Outdeg and indeg are short for Out-degree and In-degree.

 

Walks & Paths

We will use the image taken from the first paragraph again to give some examples about the following items:

Graphs

A Walk is any route through the graph. A Closed Walk is any route through the graph that begins and ends at the same node. A Path is a walk in which all the edges and all the nodes are different. It does not have to pass through all nodes or edges. An example would be walking from 6,5,4,3,2,1. The path length in this example is 4.

A Cycle is a closed walk in which all the edges are different. An example would be going to 1,2,5,1 which is a 3-cycle or 2,3,4,5,2 which is a 4-cycle.

 

Eulerian Graph

A Eulerian Graph is a closed walk in which each edge is passed exactly once, so each edge is passed and no edge is passed more than once. This cycle only exists only if there are no odd (1,3,5,7) nodes. If there are two odd nodes, you can still make a Eulerian path. Passing each edge but not ending in the same place you began.

Eulerian Graph

Example: 1,2,3,5,4,2,6,5,1

 

Hamiltonian Graph

A Hamiltonian Graph has a closed walk in which each node is passed exactly once. The Hamiltonian Graph may pass the same edge multiple times or may skip edges.

Hamiltonian Graph

Example: 1,2,3,6,5,4,1

 

Now you know the basics of the graphs you can either check out my TCP & UDP or Routing Algorithm summaries. The basics of the discussed topic helps you to better understand the said summaries.

Related Posts