CS2040s: Introduction To Graphs

Graphs

Graphs are a couple denoted by G={V,E} (a tuple of two sets)

where V is the set of vertices and E is set of Edges

Vertices is the nodes

Edges are the path connected the nodes

Simple graphs

=> A node cannot have edges pointing at itself 

=> only one edge per pair of nodes.

Connected Graphs

=> Every node is connected by a path

Clique

=> A complete graph
=> Fully connected
=> Every node is connected to every other node
=> Every node is only 1 hope from other node
=>Dia : 1

=> All pairs connected by edges

Diameter

=> The maximum distance between two (different) nodes
=> Distance is the shortest path

Check for every two nodes, whats the shortest path of these two nodes
 Choose the longest (short path) out of all the pair of nodes

Star

=> One central node

=> All edges connect to the center to the other nodes

=> Diameter is 2 always

Degree

=> Number of edges incident upon a node

=> Loops are counted twice

Line

=> Diameter is n-1

=> max degree : 2

Circle

=> Diameter is n/2

=> Max Degree: 2

Representing a Graph

Adjacency List

For each node, there is a linked list that store what each node is connected to

Memory usage (Space):
array of size |v|, linked list of size |E|

Total O(V+E)

For a cycle: O(V)

For clique: O(v^2)

Adjacency Matrix

Just like a multiplication table, if it connects its denoted by a 1 and 0 if its not connected

A[v][w] = 1 means that (v,w) is an element of graph E

A^2 = length 2 path

To find out if c and d are 2 hop neighbours just take B=A^2

B[c,d] = 1 if it exist

if we want length 3 path just take A^3

Memory usage(Space):

array of size |v| x |V|

Total: O(V^2)

For a cycle: O(V^2)

For Clique: O(V^2)

But if a graph is dense (A lot of value) , use a adjacency matrix otherwise use an adjacency list

Query

To check for connection, its easier to use Adjacency Matrix.

To check for friend Enumeration (List of friends/connection), its easier to use adjacency list

Trade-offs

Adjacency Matrix:

- Fast query => are v and w neighbours?

- Slow query => find me any neighbour of v

- Slow query => list all neighbour

Adjacency List

- Fast Query=> Find me any neighbour

- Fast Query=> list all neighbour

- Slower Query => Are v and w neighbours (friends)?

Directed Graphs

When the edges have a certain direction

(v,w) means an edge pointing from v-> w

Order Matters

Degree of nodes:

In- Degree=> Incoming edges

Out-degree => Outgoing edges

We can represent Directed Graph using Adjacency list and matrix

Directed Adjacency List

Only store the outgoing edges in the list

Directed Adjacency Matrix

Only store if  A[v][w] = 1 iff v is connected to w for outgoing edges

where A[row][col]

Text Generation (Extra)

All nodes are Kgrams where kgrams is a contiguous sequence of k items

e.g syllables, letters ,words

Edges = one kgram follows another