Lecture 9

In social networks, such as Facebook, graphsare used to represent relationships.

Graphs
vertex-set V(G) = {u, v, w, z}
edge-set E(G) = {e1, e2, e3, e4}
Edge / e1 / e2 / e3 / e4
Endpoints / {u, v} / {u, w} / {v, w} / {w, z}
Incidence matrix
G = {V(G), E(G)} = {{u, v, w, z}, {e1, e2, e3, e4}} /

Representing graphs

The adjacency matrix:

a / b / c / d / e / f / g
a / 0 / 0 / 1 / 1 / 0 / 1 / 0
b / 0 / 0 / 0 / 1 / 1 / 0 / 0
c / 1 / 0 / 0 / 0 / 0 / 1 / 0
d / 1 / 1 / 0 / 0 / 1 / 1 / 0
e / 0 / 1 / 0 / 1 / 0 / 0 / 0
f / 1 / 0 / 1 / 1 / 0 / 0 / 0
g / 0 / 0 / 0 / 0 / 0 / 0 / 0

The incident matrix:

ac / ad / af / bd / be / cf / de / df
a / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 0
b / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0
c / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0
d / 0 / 1 / 0 / 1 / 0 / 0 / 1 / 1
e / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 0
f / 0 / 0 / 1 / 0 / 0 / 1 / 0 / 1
g / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0

the adjacency list.

AI

Shortest path
  • Start/ Source (S)
  • Goal (G)
/

Eulerian Graphs
A connected graph G is Eulerian if there is a closed path which includes every edge of G; such path is called an Eulerian path.
THEOREM: Eulerian
Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree. /

Königsberg bridges problem

The four parts (A, B, C and D) of the city Königsbergwere interconnected by seven bridges (p, q, r, s, t, u and v) as shown in the following diagram. Is it possible to find a route crossing each bridge exactly once ?

/ Königsberg graph