# Graph (Network - Nodes and edges)

A graph is a set of vertices connected by edges. See Graph - (Property Graph) Model

Data representation that naturally captures complex relationships is a graph (or network).

Except of the special graph that a tree is, the data structure of a graph is non-hierarchical.

Points are called nodes, links are called edges. A link can only connect two nodes (only binary relationship ?)

Each edge has two endpoints, the nodes it connects. The endpoints of an edge are neighbors.

## 3 - Application

Are mostly graphs:

• Social Interaction
• a workflow editor,
• an organisational chart,
• a business process modelling tool (a UML tool)
• an electronic circuit diagrammer,
• network/telecoms visualisation

## 4 - Type

• Graph - Acyclic - graphs that do/don't allow self-loops.
• graphs whose nodes/edges are insertion-ordered, sorted, or unordered

## 5 - Example

### 5.1 - Map

London Tube Map 1908 Lond Tube Map 1933

## 6 - Dominating set

A dominating set in a graph is a set S of nodes such that every node is in S or a neighbor of a node in S.

Neither algorithm is guaranteed to find the smallest solution.

### 6.1 - Grow Algorithm

```initialize S = 0;
while S is not a dominating set,

### 6.2 - Shrink Algorithm

```initialize S = all nodes
while there is a node x such that S −{x} is a dominating set,
remove x from S```

## 7 - Path

### 7.2 - Cycle

A x-to-x path is called a cycle

### 7.3 - Spanning

A set S of edges is spanning for a graph G if, for every edge {x, y} of G, there is an x-to-y path consisting of edges of S.

### 7.4 - Forest

A set of edges of G is a forest if the set includes no cycles.

## 8 - Problem

### 8.1 - Minimum spanning forest

Definition:

Application: Design hot-water delivery network for the university campus:

• Network must achieve same connectivity as input graph.
• An edge represents a possible pipe.
• Weight of edge is cost of installing the pipe.
• Goal: minimize total cost.

#### 8.1.1 - Grow

```def Grow(G)
S := 0;
consider the edges in increasing order # Increasing order: 2, 3, 4, 5, 6, 7, 8, 9.
for each edge e:
if e’s endpoints are not yet connected
```def Shrink(G)