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

## 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 **g**raph **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**e**dges 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.

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:

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.

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

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