Graph (Network)

1 - About

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.

See also: (Graph|Network) - Database

Code, Data Modeling, Social Interaction are mostly graphs

3 - Example

Tube_map

London Tube Map 1908 Lond Tube Map 1933

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

4.1 - Grow Algorithm

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

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

5 - Path

5.1 - Definition

A sequence of edges <math>[\{x_1, x_2\}, \{x_2, x_3\}, \{x_3, x_4\}, \dots , \{x_{k_1}, x_k\}]</math> is called a <math>x_1-to-x_k</math> path.

Example “Main Quad”-to-”Gregorian Quad” paths in the graph:

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

5.2 - Cycle

A x-to-x path is called a cycle

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

5.4 - Forest

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

6 - Problem

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

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

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

7 - Documentation / Reference

  • Bookmark "Graph (Network)" at del.icio.us
  • Bookmark "Graph (Network)" at Digg
  • Bookmark "Graph (Network)" at Ask
  • Bookmark "Graph (Network)" at Google
  • Bookmark "Graph (Network)" at StumbleUpon
  • Bookmark "Graph (Network)" at Technorati
  • Bookmark "Graph (Network)" at Live Bookmarks
  • Bookmark "Graph (Network)" at Yahoo! Myweb
  • Bookmark "Graph (Network)" at Facebook
  • Bookmark "Graph (Network)" at Yahoo! Bookmarks
  • Bookmark "Graph (Network)" at Twitter
  • Bookmark "Graph (Network)" at myAOL
graph/graph.txt · Last modified: 2017/04/13 13:21 by gerardnico