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

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.

Code, Data Modeling, Social Interaction are mostly graphs

3 - Type

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

4 - Example

London Tube Map 1908 Lond Tube Map 1933

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

5.1 - Grow Algorithm

initialize S = 0;
while S is not a dominating set,
add a node to S.

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

6 - Path

6.1 - Definition

A sequence of edges

$[\{x_1, x_2\}, \{x_2, x_3\}, \{x_3, x_4\}, \dots , \{x_{k_1}, x_k\}]$

is called a

$x_1-to-x_k$

path.

• one goes through “Wriston Quad” ,
• one goes through “Keeney Quad”

6.2 - Cycle

A x-to-x path is called a cycle

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

6.4 - Forest

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

7 - Problem

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

7.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
add e to S.

7.1.2 - Shrink

def Shrink(G)
S = {all edges} consider the edges in order, from highest-weight to lowest-weight # Decreasing order: 9, 8, 7, 6, 5, 4, 3, 2.
for each edge e:
if every pair of nodes are connected via S -{e}:
remove e from S.